③序列确定二叉树 个先/中/后序序列能否确定一个二叉树? 个先序扩展序列能否确定一个二又树? 个后序扩展序列能否确定一个二叉树? 个中序扩展序列能否确定一个二叉树? 一个先序和中序序列能否唯一确定一个二叉树? 个中序和后序序列能否确定一个二叉树? 一个先序和后序能序列能否确定一个二叉树? 例 已知先序扩展序列:AB#DF##C# 已知后序扩展序列:##D##G#B##H#FCA 已知先序 ABCDEFGH中序 BCDAFEHJIG 巳知中序 BFDAEGO后序 FDBGECA pboustc. edu. cn 16 中国科学技术大学
ypb@ustc.edu.cn 16 中国科学技术大学 序列确定二叉树 • 一个先/中/后序序列能否确定一个二叉树？ • 一个先序扩展序列能否确定一个二叉树？ • 一个后序扩展序列能否确定一个二叉树？ • 一个中序扩展序列能否确定一个二叉树？ • 一个先序和中序序列能否唯一确定一个二叉树？ • 一个中序和后序序列能否确定一个二叉树？ • 一个先序和后序能序列能否确定一个二叉树？ • 例： – 已知先序扩展序列：AB#DF###C#E## – 已知后序扩展序列：##D##G#EB###H#FCA – 已知先序:ABCDEFGHIJ 中序:BCDAFEHJIG – 已知中序:BFDAEGC 后序:FDBGECA
③遍历算法的描述 算法递归实现 void preorder(bitree T, void visit)( BiTree)) 算法非递归实现 typedef enum Travel=1, visit=0) Task Type typedef struct i BiTree ptr Task Type task i SElem Type void InOrder iter(BiTree bt, void( visit )(BiTree 用栈实现遍历 非递归循环实现 pboustc. edu. cn 17 中国科学技术大学
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 Layer Traversal( BiTree t){/按层序遍历二叉树T InitQueue(Q) 初始化一个空队列 if(r) En Queue(Q,T) ∥排空根指针入队 while(!Queueempty(oi DeQueue(Q, p) /队头出队 visite(p->data) 访问出队的结点* fp-> Child) EnQueue(Qp> Lchild),/,p左孩子入队 fp-> rchild) EnQueue(Qp> achild),/*p右孩子入队 Layer Traversal pboustc. 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
③二叉树和表达式 表达式ab(cd)ef(二叉树表示) ·中序遍历 a+b*c-def(中缀,丟失计算优先级) 先序遍历 +a*b-cdef(前缀波兰式) ·后序遍历 abcd-*+ef-(后缀逆波兰式 d pboustc. 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 Create BiTree(Bitree &T)递归先序 cIr if(ch=‘#) T=NULL else T=new binode T->data=ch Create BiTree(T->lchild) Create BiTree(T->rchild) pboustc. 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); } } 二叉树遍历应用举例