③63二叉树遍历和线索二叉树 631二叉树遍历 对所有结点进行访问,且仅被访问一次 LDR、LRD、DLR、DRL、RLD、RD六种次序 先序(根)DLR、中序(根)LDR、后序(根)LRD 例:右图得三种遍历序列 先序遍历: ABDEC A /(ANA 中序遍历: DBEAC 后序遍历: DEBCA B BEC(C C D(D(E形 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 6.3二叉树遍历和线索二叉树 6.3.1二叉树遍历 – 对所有结点进行访问，且仅被访问一次 – LDR、LRD、DLR、DRL、RLD、RDL六种次序 – 先序（根）DLR、中序（根）LDR、后序（根）LRD –例：右图得三种遍历序列 • 先序遍历：ABDEC • 中序遍历：DBEAC • 后序遍历：DEBCA A B C D E A B D E C D B E A C D E B C A
③遍历的递归实现 先序遍历二叉树的定义: 若二叉树为空,则空操作;否则 (1)访问根结点; (2)先序遍历左子树 (3)先序遍历右子树 void PreOrder(bitree Tt if(!T)return visite(T->data ∥访问根结点 PreOrder(T-> Schild),∥先序遍历左子树 PreOrder(T-> schild);∥先序遍历右子树 )//PreOrder pboustc. edu. cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 遍历的递归实现 先序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (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 Ti if(!T)return InOrder(T> Child);∥中序遍历左子树 visite(t->data) ∥访问根结点 InOrder(T> Achild),∥中序遍历右子树 3/InOrder pboustc. edu. cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 中序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 void InOrder (BiTree T){ if(!T) return; InOrder (T->lchild); //中序遍历左子树 visite(T->data); //访问根结点 InOrder (T->rchild); //中序遍历右子树 }//InOrder
后序遍历二叉树的定义: 若二叉树为空,则空操作;否则 (1)后序遍历左子树; (2)后序遍历右子树; (3)访问根结点。 void PostOrder(bitree t)i if(!T)return PostOrder(T-> lchild;,∥序遍历左子树 PostOrder(T> achild),∥后序遍历右子树 visite(t->data) ∥访问根结点 3/InOrder pboustc. edu. cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 后序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 void PostOrder (BiTree T){ if(!T) return; PostOrder (T->lchild); //后序遍历左子树 PostOrder (T->rchild); //后序遍历右子树 visite(T->data); //访问根结点 }//InOrder
扩展二叉树 先序扩展序列: 包络线经过 ABD##E##C井# 每个内部结 中序扩展序列: 点3次 A 内部结点 #D# B#E#A#C# 后续序扩展序列: B C #D井#EB#CA D E 外部结点圈 pboustc. edu. cn 15 中国科学技术大学
ypb@ustc.edu.cn 15 中国科学技术大学 扩展二叉树 A B C D E # # # # # # 先序扩展序列： ABD##E##C## 中序扩展序列： #D#B#E#A#C# 后续序扩展序列： ##D##EB##CA 包络线经过 每个内部结 点3次 外部结点 内部结点