6.3二叉树遍历和线索二叉树6.3.1二叉树遍历一对所有结点进行访问，且仅被访问一次一 LDR、LRD、DLR、DRL、 RLD、RDL六种次序一先序（根）DLR、中序（根）LDR、后序（根）LRD一例：右图得三种遍历序列·先序遍历：ABDECAAN·中序遍历：DBEACAB·后序遍历：DEBCACcBCBCBDDEDEEED11中国科学技术大学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);//PreOrder12中国科学技术大学ypb@ustc.edu.cn
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 T)if(!T) return;/中序遍历左子树InOrder (T->lchild);/访问根结点visite(T->data);/中序遍历右子树InOrder (T->rchild);//InOrder13中国科学技术大学ypb@ustc.edu.cn
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);//InOrder14中国科学技术大学ypb@ustc.edu.cn
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#后续序扩展序列：CB##D##EB##CAV##ED####外部结点15中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 15 中国科学技术大学 扩展二叉树 A B C D E # # # # # # 先序扩展序列： ABD##E##C## 中序扩展序列： #D#B#E#A#C# 后续序扩展序列： ##D##EB##CA 包络线经过 每个内部结 点3次 外部结点 内部结点