序列确定二叉树 一个先/中/后序序列能否确定一个二叉树？ ● 一个先序扩展序列能否确定一个二叉树？ ● 一个后序扩展序列能否确定一个二叉树？ 一个中序扩展序列能否确定一个二叉树？ 一个先序和中序序列能否唯一确定一个二叉树？ 一个中序和后序序列能否确定一个二叉树？ 一个先序和后序能序列能否确定一个二叉树？ 例： - 已知先序扩展序列：AB#DF#C#E# 已知后序扩展序列：#D#G#EB##H#FCA - 已知先序：ABCDEFGHIJ中序：BCDAFEHJIG 已知中序：BFDAEGC后序：FDBGECA ypb@ustc.edu.cn 16 中国科学技术大学
ypb@ustc.edu.cn 16 中国科学技术大学 序列确定二叉树 • 一个先/中/后序序列能否确定一个二叉树？ • 一个先序扩展序列能否确定一个二叉树？ • 一个后序扩展序列能否确定一个二叉树？ • 一个中序扩展序列能否确定一个二叉树？ • 一个先序和中序序列能否唯一确定一个二叉树？ • 一个中序和后序序列能否确定一个二叉树？ • 一个先序和后序能序列能否确定一个二叉树？ • 例： – 已知先序扩展序列：AB#DF###C#E## – 已知后序扩展序列：##D##G#EB###H#FCA – 已知先序:ABCDEFGHIJ 中序:BCDAFEHJIG – 已知中序:BFDAEGC 后序:FDBGECA
S 遍历算法的描述 算法递归实现 void preorder(BiTree T,void (visit)(BiTree)) 算法非递归实现 typedef enum {Travel=1,Visit-0)TaskType; typedef struct{ BiTree ptr, TaskType task; SElemType; void InOrder iter(BiTree BT,void (visit)(BiTree) 用栈实现遍历 非递归循环实现 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 17 中国科学技术大学 • 算法 递归实现 void preorder(BiTree T,void (* visit)(BiTree)) • 算法 非递归实现 typedef enum {Travel=1,Visit=0} TaskType; typedef struct { BiTree ptr; TaskType task; }SElemType; void InOrder_iter (BiTree BT,void (* visit)(BiTree)) 用栈实现遍历 非递归循环实现 遍历算法的描述
层次遍历* void LayerTraversal (BiTree T){I/按层序遍历二叉树T InitQueue(Q); /初始化一个空队列 if(T)EnQueue(Q,T); 非空根指针入队 while(IQueueEmpty(Q)){ DeQueue(Q,p); 队头出队 visite(p->data); /访问出队的结点*p ifp->-lchild)EnQueue(Q,p->Ichild);/*p左孩子入队 ifp->rchild)EnQueue(Q,p->rchild);∥*p右孩子入队 }LayerTraversal ypb@ustc.edu.cn 18 中国科学技术大学
ypb@ustc.edu.cn 18 中国科学技术大学 层次遍历* void LayerTraversal（BiTree T）{//按层序遍历二叉树T InitQueue(Q); //初始化一个空队列 if(T) EnQueue(Q,T); //非空根指针入队 while(!QueueEmpty(Q)){ DeQueue(Q,p); //队头出队 visite(p->data); //访问出队的结点*p if(p->lchild) EnQueue(Q, p->lchild); //*p左孩子入队 if(p->rchild) EnQueue(Q, p->rchild); //*p右孩子入队 } }LayerTraversal
S 二叉树和表达式 表达式a+b*(c-d)-e/f(二叉树表示) 。 中序遍历 a+b*c-d-e/f (中缀，丢失计算优先级) ·先序遍历 -+a*b-cd/ef (前缀波兰式) 后序遍历 a -abcd-*+ef-(后缀/逆波兰式) ypb@ustc.edu.cn 19 中国科学技术大学
ypb@ustc.edu.cn 19 中国科学技术大学 二叉树和表达式 • 表达式a+b*(c-d)-e/f（二叉树表示） • 中序遍历 – a+b*c-d-e/f (中缀，丢失计算优先级) • 先序遍历 – -+a*b-cd/ef (前缀/波兰式) • 后序遍历 – abcd-*+ef/- (后缀/逆波兰式) - + / a * - c d b e f
二叉树遍历应用举例 例建立二叉树的存储结构（先序扩展二叉树序列） void CreateBiTree(BiTree&T）递归先序 cin>>ch: if ch==#)T=NULL; else T-new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); ypb@ustc.edu.cn 20 中国科学技术大学
ypb@ustc.edu.cn 20 中国科学技术大学 • 例 建立二叉树的存储结构(先序扩展二叉树序列) void CreateBiTree(BiTree &T) 递归 先序 { cin>>ch; if（ch==‘#’)T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } 二叉树遍历应用举例