第11讲 树和二叉树(二)

复习 在二叉树的第 i 层上至多有多少个结点。(i≥1) 深度为 k 的二叉树上至多含多少个结点（k≥1）

教学目标 掌握二叉树的先序、中序、后序遍历算法 掌握二叉树的建立算法 3/ 计算机科学与技术系 信息与教育技术中心

问题的提出 定义：顺着某一条搜索路径访问二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 作用： 遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。

问题的提出 线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。 二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。

二叉树的遍历 方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点 D L R LDR、LRD、DLR RDL、RLD、DRL

先序遍历: 先序遍历序列：A B D C D L R D L R A D L R A D B C B > D L R C >

中序遍历: 中序遍历序列：B D A C L D R L D R A L D R A D B C > L D R B > C

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B D > B > > C

- + a * b - c d / e f a + b * c - d - e / f a b c d - * + e f / - - + 先序遍历： a + b * c - d - e / f 中序遍历： a b c d - * + e f / - 后序遍历： 层次遍历： - + / a * e f b - c d

例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。

中序遍历：B D C E A F H G 后序遍历：D E C B H G F A

先序遍历 void preorder(bitree *bt) { if(bt!=NULL) 结点类型： typedef struct BiTNode{ 　TElemType data; 　struct BiTNode *lchild; 　struct BiTNode *rchild; } bitree; void preorder(bitree *bt) { if(bt!=NULL) { printf("%d ",bt->data); preorder(bt->lchild); preorder(bt->rchild); }

void preorder(bitree *bt) { if(bt!=NULL) { printf("%d\n",bt->data); preorder(bt->lchild); preorder(bt->rchild); } T A printf(A); pre(T L); A pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); B C T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 pre( T ) 返回 pre(T R); 返回 返回 先序序列：A B D C pre(T R); 返回

中序遍历 void inorder(bitree *bt) { if(bt!=NULL) { inorder(bt->lchild); printf("%d ",bt->data); inorder(bt->rchild); }

后序遍历 void postorder(bitree *bt) { if(bt!=NULL) { postorder(bt->lchild); postorder(bt->rchild); printf("%d ",bt->data); }

中序非递归算法 A B C D E F G P i P->A (1) A B C D E F G P i P->A P->B (2) A B C D E F G P i P->A P->B P->C (3) P=NULL A B C D E F G i P->A P->B 访问：C (4)

P A B C D E F G i P->A 访问：C B (5) A B C D E F G i P->A P->D 访问：C B P (6) A B C D E F G i P->A P->D P->E 访问：C B P (7) A B C D E F G i P->A P->D 访问：C B E P (8)

A B C D E F G i P->A P->D P->G 访问：C B E P=NULL (9) A B C D E F G i P->A P->D 访问：C B E G P (10) A B C D E F G i P->A P->F 访问：C B E G D P (12) A B C D E F G i P->A 访问：C B E G D P (11)

A B C D E F G i 访问：C B E G D F A P (14) A B C D E F G i P->A 访问：C B E G D F P=NULL (13) A B C D E F G i 访问：C B E G D F A P=NULL (15)

a c b e d void inorder(bitree *bt) { int i=0; bitree *P,*s[M]; P=bt; do { while(P!=NULL) { s[i++]=P; P=P->lchild; } if(i>0) { P=s[--i]; printf("%d\t",P->data); P=P->rchild; }while(i>0||P!=NULL); a b c d e

二叉树的构造 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C 0 0 D E 0 G 0 0 F 0 0 0 A B C

二叉树的构造算法 bitree *creatbitree() { bitree *t; char ch; ch = getchar(); if(ch == ‘0’ ) t=NULL; else { t = (bitree *) malloc(sizeof(bitree)); t->data = ch; t->lchild = creatbitree(); t->rchild = creatbitree(); } return t;

作业 （1）根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。 （2）已知一棵 二叉树的先序遍历序列为ABDEHCFGI,中序遍历序列为DHEBFIGCA，试画出该二叉树，并给出该二叉树的前序序列。 （3）编写程序实现统计二叉树中叶子节点的个数。 实验四：二叉树的操作及应用