3.2 二叉树

　　1．综合应用题题目部分
　　● 习题1：一棵深度为d（根节点层次号为1）的满t叉树具有如下性质：第d层上的节点都是叶子节点，其余各层上的每个节点都有t棵非空子树。如果从根这一层开始按照从左到右的顺序逐层对全部节点编号，且根节点的编号为1，问编号为i的节点有右兄弟的条件是什么？
　　● 习题2：一个深度为h的满m叉树有如下性质：第h层上的节点都是叶节点，其余各层上每个节点有m棵非空子树。求解以下问题：
　　（1）第k层有多少个节点（k≤h）？
　　（2）整棵树有多少个节点？
　　（3）若按层次从上到下，每层从左到右的顺序从1开始对全部节点编号，编号为i的节点的双亲节点的编号是什么？
　　● 习题3：函数void TraversalTree(BTREE *tree)用非递归方法，对以tree为根节点指针的二叉树进行后序遍历。试将该函数填写完整。

　　● 习题4：函数BTREE *SortTreeSearch（BTREE *tree，int d）采用非递归方法，在二叉排序树（二叉查找树）中查找键值为d的节点。若找到，则返回键值所在节点的指针，否则返回NULL。试将以下程序填写完整。

　　● 习题5：任给一个二叉树表示的算术四则运算表达式（存储结构为二叉链表），试编写一个算法，由该二叉树输出该表达式，若原表达式有括号亦应加上。
　　● 习题6：写出在中序线索二叉树中节点*p的右子树中插入一个节点*s的算法。
　　● 习题7：试给出二叉树的自下而上、自右而左的层次遍历算法。
　　2．综合应用题的答案与分析
　　注意：若无明确说明，综合应用题中涉及的二叉树，假定其数据结构均为：

　　涉及的线索二叉树，假定其数据结构均为：

　　习题1分析：
　　设编号为i的节点的双亲编号为k，并设编号为i的节点为双亲的第j个孩子，构造一个以编号为i的节点为最后一个节点的完全t叉树（节点总数为i），则有（k-1）个度为t的节点，一个度为j的节点，其余节点都是叶子节点，所以：i-1=(k-1)×t+j。
　　当编号为i的节点不是双亲的最后一个孩子时（即j<t），有右兄弟，这时由上面的关系可知j=(i-1)%t，所以编号为i的节点有右兄弟的条件是(i-1)%t>j。
　　习题2分析：
　　利用归纳的方法可以很容易地计算出第（1）、（2）两问，第（3）问不易直接求解。
　　答案：
　　（1）设第v层有 个节点（v≤h），则由于第v层的每个节点有m个孩子，所以第 层的节点个数为 。
　　第1层有1个节点，第2层有m个节点，第3层有m2个节点，用数学归纳法易知第k层有mk-1个节点。

　　（3）设编号为i的节点双亲的编号为x，将编号为i的节点视为完全m叉树的最后一个节点，因此，此完全m叉树中至少有x-1个度为m的节点，设x号节点的度为d（1≤d≤m）。其余的节点均为叶子节点，而编号i就是此完全m叉树的总节点数，于是：

　　习题3分析：
　　遍历二叉树如果用递归方式，处理起来非常容易，几条语句就可以解决问题。但要用非递归方式，就比较复杂了。下面以图3-8所示的一棵二叉树为实例来说明此过程。

　　首先遍历根节点左子树，那么89、48、20依次入栈。到节点20时已经没有左子树可访问，就访问其右子树，发现右子树也为NULL，所以退栈打印节点20。然后要遍历栈顶节点48的右子树，遍历完后打印节点56。接下来，48会再次成为栈顶元素，那么此时是不是又要遍历栈顶节点48的右子树呢？显然不需要，因为前面已经遍历过了，所以需要判断一个节点的右子树是否已经遍历过。
　　如果能理解上面的分析，再来看程序就非常简单了。

　　此while循环正是上面分析到的，遍历左子树的代码，它访问二叉树的左分支，把所有访问到的节点全部入栈，一直访问到当前节点为空（即p == NULL时）才退出循环。因此，（1）空应填p = p->left。

　　从下面的if语句注释部分可以看出tag[top]=1是用于标识右子树已经被遍历过，所以（2）空处的判断条件应为tag[top] == 1。

　　这里是上面分析到的，如果栈顶节点的右子树未被遍历过，应遍历右子树，所以应把栈顶元素的右子节点取出，即（3）空应填p = stack[top]->right。
　　习题4分析：
　　本题的考点是二叉排序树。从while(ptr!=NULL && d != ptr->data)可以看出，当ptr == NULL或d == ptr->data时会退出循环。接着后面是返回值语句return，由于题目要求“若找到，则返回键值所在节点的指针，否则返回NULL”，当ptr == NULL退出循环时，ptr = NULL；当d == ptr->data退出循环时，ptr正好指向返回键值所在节点。所以返回ptr可以满足题目要求。因此，（3）空应填ptr，循环体内是进行二叉树的遍历，因为二叉树有如下性质：
　　若它的左子树非空，则左子树上所有节点的值均小于根节点的值；
　　若它的右子树非空，则右子树上所有节点的值均大于根节点的值；
　　左、右子树本身又各是一棵二叉排序树。
　　因此，（1）应填ptr = ptr->left，（2）空应填ptr = ptr->right。
　　习题5分析：
　　二叉表达树的中序遍历序列与表达式中运算符和操作数的顺序相同，只是没有括号，判断运算符的优先级，若子树运算符的优先级小于父节点，则要加括号。

　　习题6分析：
　　假定待插入的节点为*s，中序线索二叉树中的一个节点*p，现要将*s作为*p的右子树插进去，显然此时需要区分如下两种情形。
　　（1）若*p无右子树，此时只要使用*p原有的后继节点（设为*q）成为*s的后继即可。此时只需修改相应指针域与标志域的值。
　　（2）若*p有右子树，显然此时插入*s后，*p原有的右子树变成了*s的右子树，*s成为*p的右子树。此时必须修改各个指针：
　　（a）使*p原有的后继节点的左线索指向*s；
　　（b）使*p原有的右子树成为*s的右子树；
　　（c）使*s成为*p的右子树；
　　（d）使*s的右标志域改为0。
　　显然，在任何一种情况下，都需要使得*p成为*s的前驱，即使得*s的左线索指向自己的双亲节点*p。其算法描述如下：

　　习题7分析：
　　本题需要借助队列和栈，然后依次再弹出栈中元素，从而实现对二叉树按自下至上，自右至左的层次遍历。

　　3．训练自测表（如表3-3所示）

表3-3 应用题练习自测表