6.3二叉树遍历和线索二叉树 6.3.1二叉树遍历 - 对所有结点进行访问，且仅被访问一次 LDR、LRD、DLR、DRL、RLD、RDL六种次序 -先序（根）DLR、中序（根）LDR、后序（根）LRD -例：右图得三种遍历序列 ·先序遍历：ABDEC ·中序遍历：DBEAC ·后序遍历：DEBCA ypb@ustc.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 T){ if(!T)return; visite(T->data); /访问根结点 PreOrder(T->lchild); ∥先序遍历左子树 PreOrder(T->rchild); ∥先序遍历右子树 //PreOrder ypb@ustc.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
S) 中序遍历二叉树的定义： 若二叉树为空，则空操作；否则 (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。 void InOrder(BiTree T){ if(!T)return; InOrder(T->lchild); ∥中序遍历左子树 visite(T->data); /访问根结点 InOrder (T->rchild); 中序遍历右子树 //InOrder ypb@ustc.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){ if(!T)return; PostOrder(T->lchild); /后序遍历左子树 PostOrder(T->rchild); ∥后序遍历右子树 visite(T->data); /访问根结点 //InOrder ypb@ustc.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次 内部结点 #D#B#E#A#C# 后续序扩展序列： ##D##EB##CA 外部结点 ypb@ustc.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次 外部结点 内部结点