6.3-遍历二叉树(4) 6.3-基于先中后序遍历算法的应用 ·先序速历 ,基于先/中/后序遍历的算法应用 Status PreOrderTraverse(BiTree T, Status (*Visit )(ElemType e)X ,基于先庄遭历的二又攒（二又链）的创建 if(TI=NULLX ,统计二叉榭中叶子结点的数目 if(Visit(T->data） ,整放二叉榭的所有结点空间 if PreOrderTraverse(T>lchild,Visit ) ,副除并程放二叉树中以元靠值为x的结点作为根的 if PreOrderTraverse(T->rchild,Visit)) 各子城 return OK; 银设二叉树中结点数为山高度为山 return ERROR: ,求位于二叉抛先庄序列中第k个位置的结点的值 则Ta,h=Om,sn,h)=Ob) Log:nJ+15h <n 分析问题本身的特征，选择合道的遍历次序！ else return OK; 应用递归编写算法，简洁！ 25/106 回 注意：递归站来泰洗%用遂归调用的站果 图 例1基于先序遍历的二叉树（二叉链）的创建 例1基于先序遵历的二叉树（二叉链）的创建 【本例梅证】。 如何基于二又相的先序、中序、后序遍历的速归算法进行问超解？， Status CreateBiTree(BiTree &T){ 【思路】， 按先序次序输入二叉树中结点的值（一个字特） 先序满历hO1dav 的建CreateBfTr 川空格字特表示空树，构造二叉链表表示的二叉树T 入 二叉体表示的二叉树的头指什T了带痘话点的先开序列山 scanf(&ch); 前人的表成方式 数 由输人设盆输人脚( if ch==)T=NULL: 时蓝占的有6害里 二义表示的三树的针T else 希出的表现方式 由出备希出 if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) 2国（日南）的 T-NUIL 小一ND DATA(表示虚结点的值 桑件及处理， exit(OVERFLOW); 直模求附 T-NULL T->data=ch; 根点的可问 CreateBiTree(T->lchild): Visit(T-data 于网”直墙束霸 T-dats =ch CreateBiTree(T->rchild); 年道 使用谜调用的解 return OK: )/CreateBiTree 使用速阳调用的解) PreOrder Tranerse(T-reuld CreateBiTree(T-tell) 27/106 28/106 图 例2统计二叉树中叶子结点的数目(1) 例2统计二叉树中叶子结点的数目(2) 【本例特征】 【算法1全局的计数悬】 如何通过全局变量、变参、返回值三种渠道返回处理结果？ ∥n为叶子结点的计数器 【思路】 int n=0; void leaf(BiTree T) 在遗历二叉树时，对一些特殊的结点（无左右孩子）进行计 敷。可以将遗历算法的结点访问操作修政为对特殊结点的判定和 ∥利用二叉树的先序速历 计数过程，需要注意的是计数器的处理方式。 if (T!-NULL) 可以有以下几种计数处理： ∥访问结点>叶子的判定和计数 ·用遭历函数的返回值传出求得的叶子结点的数目： if(T->lchild=-NULL &T->rchild=-NULL )n++; leaf(T->lchild); ·为遭历函数增加一个引用参数，用来传出指定二叉树的叶子 leaf(T->rchild): 结点数目。 ·引入全局的计数器，初始为0： ∥调用结束，即可由获得二叉树T的叶子结点数目 此处，遵历次序的选择对本算法没有太大影响。 需注意每次调用前须执行-0： 29/106 图 30/106 回25/106 6.3 -遍历二叉树(4) „ 先序遍历 Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ){ if ( T != NULL ){ if ( Visit(T->data) ) if ( PreOrderTraverse( T->lchild, Visit ) ) if ( PreOrderTraverse( T->rchild, Visit ) ) return OK; return ERROR; } else return OK; } 假设二叉树中结点数为n,高度为h, 则T(n,h)=O(n), S(n,h) = O(h) log2n + 1≤h ≤n 26/106 6.3 -基于先/中/后序遍历算法的应用 „ 基于先/中/后序遍历的算法应用 „ 基于先序遍历的二叉树(二叉链)的创建 „ 统计二叉树中叶子结点的数目 „ 释放二叉树的所有结点空间 „ 删除并释放二叉树中以元素值为x的结点作为根的 各子树 „ 求位于二叉树先序序列中第k个位置的结点的值 分析问题本身的特征，选择合适的遍历次序！ 应用递归编写算法，简洁！ 注意：递归结束条件，用递归调用的结果 27/106 例1 基于先序遍历的二叉树(二叉链)的创建 28/106 例1 基于先序遍历的二叉树(二叉链)的创建 Status CreateBiTree(BiTree &T) { //按先序次序输入二叉树中结点的值(一个字符) //空格字符表示空树,构造二叉链表表示的二叉树T scanf(&ch); if ( ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } // CreateBiTree 29/106 例2 统计二叉树中叶子结点的数目(1) 【本例特征】 ™ 如何通过全局变量、变参、返回值三种渠道返回处理结果？ 【思路】 在遍历二叉树时，对一些特殊的结点(无左右孩子)进行计 数。可以将遍历算法的结点访问操作修改为对特殊结点的判定和 计数过程，需要注意的是计数器的处理方式。 可以有以下几种计数处理： ™·用遍历函数的返回值传出求得的叶子结点的数目； ™·为遍历函数增加一个引用参数，用来传出指定二叉树的叶子 结点数目。 ™·引入全局的计数器，初始为0； ™此处，遍历次序的选择对本算法没有太大影响。 30/106 例2 统计二叉树中叶子结点的数目(2) 【算法1 全局的计数器】 ™// n为叶子结点的计数器 ™int n=0; ™void leaf(BiTree T) ™{ ™// 利用二叉树的先序遍历 ™if (T != NULL ){ ™// 访问结点->叶子的判定和计数 ™if( T->lchild==NULL && T->rchild==NULL ) n++; ™leaf(T->lchild); ™leaf(T->rchild); ™} ™}// 调用结束，即可由n获得二叉树T的叶子结点数目 ™需注意每次调用前须执行n=0;