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