树和二叉树习题讲解

灰太狼 2022-02-05 08:49 221阅读 0赞

## 树和二叉树习题讲解 ##

1. 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是：

\[解析\]设B为分支总数，N为结点总数，n0, n1, n2 ...分别代表度为0 ，1， 2的结点的个数。通过分析可以知道除了根结点，每一个结点的上面都连有一个分支，故得到关系1：B + 1 = N 其中B = n1 + 2n2+ 3n3 + ... 带入题目中的数据可知答案为82

\[答案\] 82

2.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是： 父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系

\[解析\]首先需要知道将森林转化为二叉树的方法。

森林->树： 把一棵树看成一个结点，不同的树之间是兄弟关系。

普通树->二叉树：左孩子，右兄弟。在兄弟之间加一条连线，对于每个结点，保留长子与其连线，去掉其他孩子与他的连线。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70]

\[答案\] 1和2

3. 具有65个结点的完全二叉树其深度为（根的深度为1）：

\[解析\]完全二叉树是一种特殊的二叉树，当且仅当其每一个结点都与相应的满二叉树编号1~n一一对应时，才是完全二叉树。又因为深度为k的二叉树最多有2^k-1个结点，可推出具有n个结点的完全二叉树的深度为\[log2n\]+1(\[ \]表示不超过这个数的最大整数)。

\[答案\] 7

4. 将\{ 5, 11, 13, 1, 3, 6 \}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：

\[解析\]二叉搜索树：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 1]

根据定义，这一题的二叉搜索树为

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 2]

\[答案\] 3, 1, 6, 13, 11, 5

5. 一棵二叉树的后序序列： fdbgheca，中序序列：bfdagehc。前序遍历序列为（ ）。

\[解析\] 根据后序遍历，最后一个就是根结点所在，所以在给定的中序序列里，以a为界分开，左边的bfd，右边的gehc。对于左边那一小堆，从后续序列可知那一个小堆的根结点是b，以此类推可以得到整棵树：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 3]

\[答案\] abdfcegh

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70]: /images/20220205/ff0eb40dc2114b12882fcde720002989.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 1]: /images/20220205/c485cd601d6c444f9738cc4d695adcb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 2]: /images/20220205/608402df88d64b02a9df75a18d915084.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70 3]: /images/20220205/eef0a510fdb347cfa783f930e7a39931.png