第6章 树要点：
1、掌握树和二叉树的逻辑结构和基本概念；
2、掌握二叉树的性质、二叉链存储、遍历及其相关算法；
3、二叉树与树、森林的转换。
教材习题参考解答：
6.1 树有2种，二叉树有5种
6.3 n-1 = n1+2n2+3n3+……+knk
n +n1+n2+……+nk
n0 =1+n2+2n3+……+(k-1)nk
6.5 99
6.6 (1)均只有右子结点；(2)均只有左子结点；(3)仅有根结点。
6.7 n * k – n +1
6.8
6.10 可以不用递归，二叉树后序序列中的第一个结点是根结点的最左子结点的最右子结点（如果最左子结点没有右子树，则该结点就是后序序列的第一个结点）。
练习：
1、假定有如图的树，则该树的度为,树的深度为,终端结点的个数为,单分支结点的个数为,双分支结点的个数为,C结点的双亲结点为,其孩子结点为 。
2、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有 个。
3、对于一个具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树（除终端结点外，所有的结点都为单分支结点）时具有最大高度，即为 。
4、对于一棵具有n个结点的二叉树，当采用二叉链进行存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点,个空闲着。
5、一棵深度为k的满二叉树的结点总数为,一棵深度为k的完全二叉树的结点总数的最小值为,最大值为 。
6、由a，b，c三个结点构成的二叉树，共有 种不同的结构。
7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是,若有右子女，则右子女为 。
8、一棵二叉树如右。
（1）写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列。
（2）画出其中序线索二叉树。
9、已知一棵二叉树的中序遍历序列为CDBAEGF，先序遍历序列为ABCDEFG，试问能不能确定唯一一棵二叉树，若能请画出该二叉树。
10、给定一棵用二叉链表示的二叉树，其根结点指针为t，试写出求二叉树叶子结点数目的算法：int leaf(BiTree t);
11、将以下森林转化为相应的二叉树。
参考解答：
1、3 4 6 1 1 A F，G
2、n+1 3、满,log2(n+1) 最大 n
4、2n n-1 n+1 5、2k-1,2k-1,2k-1
6、30 7、R[2i] R[2i+1]
8、（1）ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH
（2）如右。
9、
10、int leaf(BiTree t)
{ BiTree a[10],p=t;
int i=0,n=0;
while(p)
{ if(p){ a[i++]=p; p=p->lchild;}
else
{ p=a[--i];
if(p->lchild==NULL&&p->rchild==NULL)n++;
p=p->rchild;
}
}
return n;
}
4、如右：
1、掌握树和二叉树的逻辑结构和基本概念；
2、掌握二叉树的性质、二叉链存储、遍历及其相关算法；
3、二叉树与树、森林的转换。
教材习题参考解答：
6.1 树有2种，二叉树有5种
6.3 n-1 = n1+2n2+3n3+……+knk
n +n1+n2+……+nk
n0 =1+n2+2n3+……+(k-1)nk
6.5 99
6.6 (1)均只有右子结点；(2)均只有左子结点；(3)仅有根结点。
6.7 n * k – n +1
6.8
6.10 可以不用递归，二叉树后序序列中的第一个结点是根结点的最左子结点的最右子结点（如果最左子结点没有右子树，则该结点就是后序序列的第一个结点）。
练习：
1、假定有如图的树，则该树的度为,树的深度为,终端结点的个数为,单分支结点的个数为,双分支结点的个数为,C结点的双亲结点为,其孩子结点为 。
2、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有 个。
3、对于一个具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为,当它为一棵单支树（除终端结点外，所有的结点都为单分支结点）时具有最大高度，即为 。
4、对于一棵具有n个结点的二叉树，当采用二叉链进行存储时，其二叉链表中的指针域的总数为 个，其中 个用于链接孩子结点,个空闲着。
5、一棵深度为k的满二叉树的结点总数为,一棵深度为k的完全二叉树的结点总数的最小值为,最大值为 。
6、由a，b，c三个结点构成的二叉树，共有 种不同的结构。
7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是,若有右子女，则右子女为 。
8、一棵二叉树如右。
（1）写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列。
（2）画出其中序线索二叉树。
9、已知一棵二叉树的中序遍历序列为CDBAEGF，先序遍历序列为ABCDEFG，试问能不能确定唯一一棵二叉树，若能请画出该二叉树。
10、给定一棵用二叉链表示的二叉树，其根结点指针为t，试写出求二叉树叶子结点数目的算法：int leaf(BiTree t);
11、将以下森林转化为相应的二叉树。
参考解答：
1、3 4 6 1 1 A F，G
2、n+1 3、满,log2(n+1) 最大 n
4、2n n-1 n+1 5、2k-1,2k-1,2k-1
6、30 7、R[2i] R[2i+1]
8、（1）ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH
（2）如右。
9、
10、int leaf(BiTree t)
{ BiTree a[10],p=t;
int i=0,n=0;
while(p)
{ if(p){ a[i++]=p; p=p->lchild;}
else
{ p=a[--i];
if(p->lchild==NULL&&p->rchild==NULL)n++;
p=p->rchild;
}
}
return n;
}
4、如右：
