二叉树课后习题解析

# 二叉树课后题P154
## s1
 二叉树中度为0的结点数为30,度为1的节点数为20,总结点数?
    设二叉树度为0的结点数为N0     度为1的结点数为N1     度为2的结点数位N2     结点总数为T     所以有
    T = N0 + N1 + N2   (1) (依据结点)     T = N1 + 2*N2 + 1  (2)(依据分支)     (每个N2节点有2个分支,每个N1结点有1个分支,前面相加为分支数,求结点数还要加上根结点)
    (2)-(1)得N2 = N0 - 1     解出N0、N1、N2即可
## s2
设一棵完全二叉树有128个结点,则该完全二叉树的深度为____, 有____个叶子结点
    深度为8.     因为2^7 - 1 < 128 < 2^8 - 1
    有64个叶子结点.     因为 (128+1)/ 2 = 64 (按整型计算)
### 知识点回顾
    高度为h的二叉树中结点最多为2^k-1个
## s3
设有n个结点的完全二叉树,如果按照从自上到下,从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___, 右孩子结点的编号为____
    i/2 2*i+1
     1     2 3     4 5 6 7
## s4
设二叉树中结点的两个指针域分别为lchild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是________.
    p->lchild==NULL&&p->rchild==NULL ??
## s5
设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的后序遍历序列为____,中序遍历序列为______
    DBEAFC     DEBFCA
## s6
设一棵二叉树的前序序列为 ABC ,则有 1_ 种不同的二叉树可以得到这种序列
    5 ![1](./assets/ABC 二叉树.png)
## s7
设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是
    高度等于其结点数
    先序遍历:根左右;后续遍历:左右根     要满足题意,则只有     根左<----->左根     根右<--------->右根     所以高度一定等于节点数
## s8
假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为:
0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10
请为这8个字母设计哈夫曼编码,要求画出哈夫曼树。
![树的高度](./assets/树的高度.PNG)
    编码:0.19:00  0.21:01   0.02:10000  0.03:10001  0.06:1001  0.07:1010   0.10:1011   0.32:11
## s9
设哈夫曼树*有n个结点,则该哈夫曼树中有几个度数为1的结点
    0个
## s10
含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为(  )
    n个结点的二叉链表中,有2n个链域,     每一条非空链域对应一条树枝,     而树支的个数为n-1,     因此,空节点个数为2n-(n-1)=n+1 ![树的高度](./assets/有多少个空指针域.PNG)



上一篇:index


下一篇:Eclipse使用