例7判断一棵二叉树是否为完全二叉树(1) 例7判断一棵二叉树是否为完全二叉树(2) 【思略】 whe(:Que▣eEmp的Q){∥队不为空，则尚有来访问其孩于的的点 p-DeOueue(O): 由光全二叉树的定义，对全二叉树按层次速历应浦足： bFlag --FALSE) 1)若某结点没有左孩子则它一定无右孩子； “前驱结点峡左改子，则若该岫点有改子，则此树率亮全二又树 2)若某结点缺孩子，则其后鳗无孩子， if p->lchild:-NULL p>rchild!-NULL)return FALSE: 利用层次遍历，需要附加一个标志量bFe反映是否已扫描过的结点均有 lelse if p->lchild--NULL) 左右毯子，在事一文通到孩子的结点时，可将为FS正，此时存在 :第一次通到结点缺左孩子 以下两种情况： bFlag -FALSE; 若它滴足1)，需要缝峡扫描后壁结点，以判断是否满足2)， Ⅱ若有右孩子，不调足1)，则排亮全二又树 若不满足1)，则说明不是光全二叉树， if p->rchild !-NULL return FALSE; 【算法】 lelse if p->lchild !NULL) 业若有左娄子，刚入队 BOOL: EnQueue(Q,p>lchild片 #define FALSE 0 一次省左子，峡右孩于 BOOL JudgeCBT(BiTree T) bFlag FALSE: else EnQueue(Q,p>rchild): InitQueue (Q): bFlag=TRUE; if (T!=NULL) EnQueue(Q,T): return TRUE:∥T为空，也是先全二叉树 55/1Ue 回 图 6.3-层次遍历算法及其应用 6.3-二叉树的创建方法 ,灵活运用：问题的延伸与解决 ·二叉树（链式存储）的创建方法 ·找出距结点x量近的叶子子孙 输入序列与二叉树的映射关系： ,求距结点x最近的叶子子孙到x的距高 如何获得距离信息？ ,完全二叉树的顺序映射 。方法1：扩晨队列元素的类型，增加距高城 通过补皮站点，将一般的二叉树转变成完全二叉 。方法2：交普使用两个队列，以获得结点的层次 树，再对域完全二叉树的结点按自上而下、自左 ,方法3：在每一层末尾增加一个虚结点， 至右进行精入， 统计距结点x最近的叶子子孙的数目 ,二叉树的先序请历 。输出距结点x最近的所有叶子子孙 通过补虚结点，使二叉树中各实际站点均具有左 ,输出距结点x最近的叶子子孙到x的略径 右孩子，再对该二又树状先序遍历进行输入， 。出队时不则除元素，元素类型中增加结点的双亲在队 ,二叉树的两种遭历序列：先序+中序，后序+中序 列中的位置1 58/106 图 6.3线索二叉树 6.3-线索二叉树类型定义 。线索二叉树 -二叉树的结构扩展 。候案链表：包含战家的链表 ·二又树的遗历：非线性结构的线性化 /Link==0:指t,Thread==l:城常 typedef enum Link,Thread)PointerTag 。问题：在二叉树的能式存储中，如何快速找到某站点 typedef struct BiThrNode( 在某一序列（先序/后序/中序）中的直接前驱本直接后 ElemType data; 婊？ /川左右孩子湘针转家 ·为每一结点增加fwd和bkwd指针域 struct BiThrNode *Ichild,*rchild; —降低存储密度 /川左右标速 PointerTag Itag,rtag; ,利用二叉链中的空链域(n个结点有+1个空链域) >BiThrNode,*BiThrTree; 标识链城的含义：葉子？线素（指向结底前驱和 ,能案二叉树：加上线球的二叉树 后继的指针)？ 。线康化：对二叉树以某种次序速历使其变为线寒二叉树的过程. 59/106 图 60/106 图55/106 【思路】 ™由完全二叉树的定义，对完全二叉树按层次遍历应满足： ™ 1）若某结点没有左孩子，则它一定无右孩子； ™ 2）若某结点缺孩子，则其后继必无孩子。 ™ 利用层次遍历，需要附加一个标志量bFlag反映是否已扫描过的结点均有 左右孩子。在第一次遇到缺孩子的结点时，可将bFlag置为FALSE；此时存在 以下两种情况： ™ ·若它满足1），需要继续扫描后继结点，以判断是否满足2）； ™ ·若不满足1），则说明不是完全二叉树。 【算法】 ™typedef char BOOL; ™#define TRUE 1 ™#define FALSE 0 ™BOOL JudgeCBT(BiTree T) ™{ ™ InitQueue (Q); bFlag = TRUE; ™ if ( T != NULL ){ ™ EnQueue(Q, T); 例7 判断一棵二叉树是否为完全二叉树(1) 56/106 while ( !QueueEmpty(Q) ){ // 队不为空，则尚有未访问其孩子的结点 p = DeQueue(Q); if ( bFlag == FALSE ) { // 前驱结点缺左孩子，则若该结点有孩子，则此树非完全二叉树 if ( p->lchild!=NULL || p->rchild!=NULL ) return FALSE; }else if ( p->lchild == NULL ) { // 第一次遇到结点缺左孩子 bFlag = FALSE; // 若有右孩子，不满足1），则非完全二叉树 if ( p->rchild != NULL ) return FALSE; }else if ( p->lchild != NULL ) { // 若有左孩子，则入队 EnQueue(Q, p->lchild ); if ( p->rchild == NULL ) // 第一次遇到结点有左孩子，缺右孩子 bFlag = FALSE; else EnQueue(Q, p->rchild ); } } } return TRUE; // T为空，也是完全二叉树 } 例7 判断一棵二叉树是否为完全二叉树(2) 57/106 6.3 –层次遍历算法及其应用 „ 灵活运用:问题的延伸与解决 „ 找出距结点 x 最近的叶子子孙 „ 求距结点 x 最近的叶子子孙到 x 的距离 如何获得距离信息? „ 方法1:扩展队列元素的类型,增加距离域 „ 方法2:交替使用两个队列,以获得结点的层次 „ 方法3:在每一层末尾增加一个虚结点,… „ 统计距结点 x 最近的叶子子孙的数目 „ 输出距结点 x 最近的所有叶子子孙 „ 输出距结点 x 最近的叶子子孙到 x 的路径 „ 出队时不删除元素,元素类型中增加结点的双亲在队 列中的位置域 58/106 6.3 –二叉树的创建方法 „ 二叉树(链式存储)的创建方法 输入序列与二叉树的映射关系： „ 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉 树，再对该完全二叉树的结点按自上而下、自左 至右进行输入。 „ 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左 右孩子，再对该二叉树按先序遍历进行输入。 „ 二叉树的两种遍历序列：先序+中序，后序+中序 59/106 6.3 –线索二叉树 „ 线索二叉树——二叉树的结构扩展 „ 二叉树的遍历：非线性结构的线性化 „ 问题：在二叉树的链式存储中，如何快速找到某结点 在某一序列(先序/后序/中序)中的直接前驱和直接后 继？ „ 为每一结点增加fwd和bkwd指针域 ——降低存储密度 „ 利用二叉链中的空链域(n个结点有n+1个空链域) ——标识链域的含义: 孩子？线索(指向结点前驱和 后继的指针)？ 60/106 6.3 –线索二叉树类型定义 „ 线索链表: 包含线索的链表 // Link== 0 :指针,Thread==1: 线索 typedef enum { Link, Thread} PointerTag; typedef struct BiThrNode{ ElemType data; // 左右孩子指针/线索 struct BiThrNode *lchild, *rchild; // 左右标志 PointerTag ltag, rtag; }BiThrNode, *BiThrTree; „ 线索二叉树: 加上线索的二叉树 „ 线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程