⑴ 设计算法求二叉树的结点个数。
【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的―访问‖操作改为―计数操作‖，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。 具体算法如下：
⑵ 设计算法按前序次序打印二叉树中的叶子结点。
【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：
⑶ 设计算法求二叉树的深度。
【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下：
36
⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。
【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：
⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。
【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：
37
⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。
【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下：
⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。 【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下：
① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。
② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。 具体算法如下：
38
⑻ 编写算法交换二叉树中所有结点的左右子树。
【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。 具体算法如下：
⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。
【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。
树的孩子兄弟表示法中的结点结构定义如下： template struct TNode { T data;
TNode *firstchild, *rightsib; };
具体算法如下：
39
学习自测及答案
1．前序遍历和中序遍历结果相同的二叉树是（ ）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树
C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树 【解答】D
1．前序遍历和中序遍历结果相同的二叉树是（ ）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D
2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。 A 24 B 48 C 53 D 72 【解答】C
3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（ ）。
A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D
4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（ ）。 A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律 【解答】C
5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ）。 A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D
6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ ）。
A h B h+1 C h或h+1 D 任意 【解答】C
7．假定一棵度为3的树中结点数为50，则其最小高度应为 。 A 3 B 4 C 5 D 6 【解答】C
40