序列确定二叉树一个先/中/后序序列能否确定一个二叉树？一个先序扩展序列能否确定一个二叉树?一个后序扩展序列能否确定一个二叉树?一个中序扩展序列能否确定一个二叉树?一个先序和中序序列能否唯一确定一个二叉树?一个中序和后序序列能否确定一个二叉树？一个先序和后序能序列能否确定一个二叉树?例：一已知先序扩展序列：AB#DF###C#E##已知后序扩展序列：##D##G#EB###H#FCA一已知先序:ABCDEFGHIJ中序:BCDAFEHJIG一已知中序:BFDAEGC后序:FDBGECA16中国科学技术大学ypb@ustc.edu.cn
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) TaskType;typedef struct (BiTreeptr,TaskTypetask,SElemType;void InOrder iter (BiTree BT,void (* visit)(BiTree)用栈实现遍历非递归循环实现17中国科学技术大学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)) 用栈实现遍历 非递归循环实现 遍历算法的描述
层次遍历voidLayerTraversal（BiTreeT）//按层序遍历二叉树T//初始化一个空队列InitQueue(Q);/非空根指针入队if(T) EnQueue(Q,T):while(!QueueEmpty(Q))//队头出队DeQueue(Q,p);/访问出队的结点*pvisite(p->data);if(p->lchild) EnQueue(Q, p->lchild); //*p左孩子入队if(p->rchild)EnQueue(Q,p->rchild);//*p右孩子入队1qLayerTraversal18中国科学技术大学ypb@ustc.edu.cn
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
二叉树和表达式表达式a+b*(c-d)-e/f（二叉树表示）、中序遍历一a+b*c-d-e/f（中缀，丢失计算优先级先序遍历(前缀/波兰式) -+a*b-cd/eff后序遍历一abcd-*+ef/-（后缀/逆波兰式）b19中国科学技术大学ypb@ustc.edu.cn
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
二叉树遍历应用举例例建立二叉树的存储结构(先序扩展二叉树序列voidCreateBiTree(BiTree&T)递归先序1cin>>ch;if （ ch==‘#")T-NULL;else(T=new BiTNode;T->data=ch;CreateBiTree(T->lchild):CreateBiTree(T->rchild):20中国科学技术大学ypb@ustc.edu.cn
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); } } 二叉树遍历应用举例