3．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原
子时。另外，广义表从元素之间的关系可看成前驱和后继，也符 合线性表，但这时元素有原子，也有子表，即元素并不属于同一 数据对象。
4．方法有二。一是对该算术表达式（二叉树）进行后序遍历， 得到表达式的后序遍历序列，再按后缀表达式求值；二是递归 求出左子树表达式的值，再递归求出右子树表达式的值，最后 按根结点运算符（+、-、*、/ 等）进行最后求值。
5．该算术表达式转化的二叉树如右图所示。 第5题图
6．n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。
7．证明：设二叉树度为0和2的结点数及总的结点数分别为n0，n2 和n，则n=n0+n2 ? (1)
再设二叉树的分支数为B, 除根结点外，每个结点都有一个分支所指，则 n=B+1? ? ?(2)
度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此（2）式可写为
n=2*n2+1 ?????(3)
由（1）、（3）得n2=n0-1,代入（1），并由（1）和（2）得B=2*(n0-1)。 证毕。
h-1
8．(1)k(h为层数)
h-1
（2）因为该树每层上均有K个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是整数，故结点n的双亲i的编号为?n-2)/k?+1。
(3) 结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的第 i个孩子的编号是(n-1)*k+1+i。
(4) 根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (n-1)%k!=0，其右兄弟编号是n+1。
9．最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到
h-1h
各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2 n 10．2-1(本题等价于高度为n的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。) 7-1 11．235。由于本题求二叉树的结点数最多是多少，第7层共有2=64个结点，已知有10个叶子，其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的 7 结点数最多可达(2-1+108)=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能8层。) 10 12．1023（=2-1） 13．证明：设度为1和2 的结点数是n1和n2，则二叉树结点数n为n=m+n1+n2???? (1) 由于二叉树根结点没有分枝所指，度为1和2的结点各有1个和2个分枝，度为0 的结点没有分枝，故二叉树的结点数n与分枝数B有如下关系 n=B+1=n1+2*n2+1?????????.(2) 由（1）和（2），得n2=m-1。即n个结点的二叉树，若叶子结点数是m，则非叶子结点中有（m-1）个度为2，其余度为1。 14．根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是?i/2?，故A[i]和A[j]的最近公共祖先可如下求出： while(i/2!=j/2) if(i>j) i=i/2; else j=j/2; 退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2。 15．N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，第 i-12H-1 i(1<=i<=H)层的结点数K，则N=1+k+k+?+ k，由此得H=?logK(N(K-1)+1)?16. 结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。 17．设分枝结点和叶子结点数分别是为nk和n0，因此有n=n0+nk (1) 另外从树的分枝数B与结点的关系有 n=B+1=K*nk +1 (2) 由（1）和（2）有 n0=n-nk=(n(K-1)+1)/K 18.用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是?i/2?(i=1时无双亲)，其左子女是2i(若2i<=n,否则i无左子女)，右子女是2i+1(若2i+1<=n,否则无右子女)。 19. 根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是?n/2?，这是最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是?n/2?+1。 20. 按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。 21. 设树的结点数为n，分枝数为B，则下面二式成立 n=n0+n1+n2+?+nm (1) n=B+1= n1+2n2+?+mnm (2) 由(1)和(2)得叶子结点数n0=1+ 22. ?log2n? +1 23.15 24. 该结论不成立。对于任一a