遍历的递归实现 先序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。 void PreOrder(BiTree T) if(!T)return; visite(T->data); /访问根结点 PreOrder(T->lchild); ∥先序遍历左子树 PreOrder(T->rchild); 先序遍历右子树 //PreOrder ypb@ustc.edu.cn 16 中国科学技术大学
ypb@ustc.edu.cn 16 中国科学技术大学 遍历的递归实现 先序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。 void PreOrder(BiTree T){ if(!T) return; visite(T->data); //访问根结点 PreOrder(T->lchild); //先序遍历左子树 PreOrder(T->rchild); //先序遍历右子树 }//PreOrder
中序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。 void InOrder(BiTree T){ if(!T)return; InOrder (T->lchild); /中序遍历左子树 visite(T->data); /访问根结点 InOrder (T->rchild): ∥中序遍历右子树 //InOrder ypb@ustc.edu.cn 17 中国科学技术大学
ypb@ustc.edu.cn 17 中国科学技术大学 中序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 void InOrder (BiTree T){ if(!T) return; InOrder (T->lchild); //中序遍历左子树 visite(T->data); //访问根结点 InOrder (T->rchild); //中序遍历右子树 }//InOrder
S 后序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。 void PostOrder (BiTree T){ if(!T)return; PostOrder(T->lchild): /后序遍历左子树 PostOrder (T->rchild); ∥后序遍历右子树 visite(T->data); /访问根结点 //InOrder ypb@ustc.edu.cn 18 中国科学技术大学
ypb@ustc.edu.cn 18 中国科学技术大学 后序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 void PostOrder (BiTree T){ if(!T) return; PostOrder (T->lchild); //后序遍历左子树 PostOrder (T->rchild); //后序遍历右子树 visite(T->data); //访问根结点 }//InOrder
扩展二叉树 先序扩展序列： 包络线经过 ABD#E##C## 每个内部结 中序扩展序列： 点3次 内部结点 #D#B#E#A#C# 后续序扩展序列： B ##D##EB##CA 外部结点 ypb@ustc.edu.cn 19 中国科学技术大学
ypb@ustc.edu.cn 19 中国科学技术大学 扩展二叉树 A B C D E # # # # # # 先序扩展序列： ABD##E##C## 中序扩展序列： #D#B#E#A#C# 后续序扩展序列： ##D##EB##CA 包络线经过 每个内部结 点3次 外部结点 内部结点
遍历序列确定二叉树* 一个单独的先/中/后序序列能否确定一个二叉树？ 一个先序扩展序列能否确定一个二叉树？ ● 一个后序扩展序列能否确定一个二叉树？ 9 o 一个中序扩展序列能否确定一个二叉树？ ● 一个先序和中序序列能否唯一确定一个二叉树？ 一个中序和后序序列能否确定一个二叉树？ 一个先序和后序能序列能否确定一个二叉树？ 例： 一已知先序扩展序列：AB#DF##C#E# - 已知后序扩展序列：#D#G#EB#H#FCA 已知先序：ABCDEFGHIJ中序：BCDAFEHJIG 已知中序：BFDAEGC后序：FDBGECA ypb@ustc.edu.cn 20 中国科学技术大学
ypb@ustc.edu.cn 20 中国科学技术大学 遍历序列确定二叉树* • 一个单独的先/中/后序序列能否确定一个二叉树？ • 一个先序扩展序列能否确定一个二叉树？ • 一个后序扩展序列能否确定一个二叉树？ • 一个中序扩展序列能否确定一个二叉树？ • 一个先序和中序序列能否唯一确定一个二叉树？ • 一个中序和后序序列能否确定一个二叉树？ • 一个先序和后序能序列能否确定一个二叉树？ • 例： – 已知先序扩展序列：AB#DF###C#E## – 已知后序扩展序列：##D##G#EB###H#FCA – 已知先序:ABCDEFGHIJ 中序:BCDAFEHJIG – 已知中序:BFDAEGC 后序:FDBGECA