当前位置：首页 > news >正文

二叉树的一些题目

news 2024/10/22 11:11:41

下面就是二叉树的一些题目，如果都能做出来说明二叉树学得不错。

题目

1、用创建结点方法创建二叉树；

2、层次遍历算法实现；

3、将二叉树的顺序存储结构转换为链式存储结构非递归算法和递归算法；

4、垂直输出二叉树；

5、二叉树前序遍历、中序遍历和后序遍历的递归和非递归算法实现；

6、用前序遍历算法创建二叉树；

7、二叉树前序遍历应用：快速排序递归算法；

8、二叉树前序遍历应用：求幂集递归算法；

9、二叉树前序遍历应用：汉诺塔问题递归算法；

10、用递归算法求二叉树的高度；

11、用递归算法完成两个二叉树的复制；

12、由前序和中序序列建立二叉树。

思考题

1、设一棵完全二叉树结点总数为n，其中叶子结点的个数是多少？

2、具有三个结点的二叉树共有几种形态？试画出这些形态。

3、设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。

4、举例说明由二叉树前序遍历序列和后序遍历序列不能确定一棵二叉树。

5、如何通过对二叉树遍历统计二叉树叶子结点、度为1的结点和度为2的结点的个数？

延展题

1、判断一个二叉树是不是完全二叉树；

2、快速排序非递归算法；

3、汉诺塔问题非递归算法；

4、由中序和后序遍历序列建立二叉树；

5、复制二叉树非递归算法；

6、求根到叶子的所有路径的递归算法和非递归算法；

7、求幂集非递归算法；

8、实现二叉树所有结点的左右孩子交换；

9、利用层次遍历求二叉树的高度；

10、实现二叉树类。

下面是答案和解析

首先二叉树节点类封转，包的头文件，等。

用创建结点方法创建二叉树；

我这里理解的节点方法插入就是平衡搜索树那种创建：

2层次遍历算法实现；

层序遍历不用多说，就是用队列存节点来实现广度优先遍历（BFS）

将二叉树的顺序存储结构转换为链式存储结构非递归算法和递归算法；

垂直输出二叉树；

垂直输出二叉树需要借助K-V结构的红黑树数据结构—map来存储节点的偏移点，先设根节点的偏移点是0，根节点往左节点走就-1，往右节点走就加1。同时记录往左走的最大长度和往右走的做大长度。然后再遍历一遍，把偏移点相同的节点放到一个数组里面。这里k-V结构还可以用unordered_map，但是我还不是很熟练，这个存储的效率也够了。

垂直遍历挺有意思的，刚好用到了我最近学的这个数据结构。

二叉树前序遍历、中序遍历和后序遍历的递归和非递归算法实现；

前序非递归我有两种写法

中序也是

后序只有一种

用前序遍历算法创建二叉树；

前序建立二叉树用递归就行了。

二叉树前序遍历应用：快速排序递归算法；

这里我写了最简单的，最后的优化版本我就不写了（inser_sort优化，heap_sort优化

，三数取中优化，还有前后指针等等…）

二叉树前序遍历应用：求幂集递归算法；

思想就是，根节点是空节点，下一层就增加一个元素，左边是不入，右边是入这个元素。然后一直递归下去。递归完了那么就有2^n中刚好就是幂集个数

二叉树前序遍历应用：汉诺塔问题递归算法；

用递归算法求二叉树的高度；

一个是在public域的tree_hight，一个是私有的。这个高度就是先看自己是不是空，不是空就返回1加上左右高度最高的数。

用递归算法完成两个二叉树的复制；

这个思路很简单，我就不多介绍了

由前序和中序序列建立二叉树。

这个老师上课也讲过，按这个思路我自己也实现了一下，但是我实现的是拷贝版本的，递归下来空间复杂度很高，应该改成引用的，用左右节点进行管理的。这样空间复杂度就低

很多。

思考题：

设一棵完全二叉树结点总数为n，其中叶子结点的个数是多少？

取n以2为底数的值并向下取整，就可以得到二叉树的高度h=[log2n]。然后知道二叉树的高度就可以知道二叉树前面几层节点的和为sum=2^h-1，叶子节点个数就是n-sum

具有三个结点的二叉树共有几种形态？试画出这些形态。

设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。
举例说明由二叉树前序遍历序列和后序遍历序列不能确定一棵二叉树。
前序和后续都是确定一颗二叉树当前的根节点的，无法确定二叉树的左右子树。
如何通过对二叉树遍历统计二叉树叶子结点、度为1的结点和度为2的结点的个数？
第一个就是先判断这个点是不是空的，是就是直接返回0，是不是就继续递归左右子树，递归的时候判断一下你要判断的要求，如果是判断叶子节点，那么左右都为空，如果是度为1那么就是有一个为空，如果是度为2，就是两个不为空。满足了就按对应情况判断是否继续递归下去就行了。
拓展题（选做）：
判断一个二叉树是不是完全二叉树；
完全二叉树必须要用层序遍历来判断：

这里本质就是层序遍历，只是看当出现空的时候是否队列里面的全是空的指针，那么我们可以用一个num来进行记录。每次非空指针进来或出去就加或者减1。
快速排序非递归算法；
快速排序画完递归展开图就是一个二叉树，和二叉树的前序遍历非递归是一样的，我就不细讲了。
汉诺塔问题非递归算法；
汉诺塔递归都很简单，非递归更不用说了
由中序和后序遍历序列建立二叉树；
因为后序遍历和前序遍历的结果是很相似的。一个是前中后，一个是后中前，就是一个倒着的只是稍微不同的是前序先走的左子树，后序先走的右子树。和前序一模一样。这里我只说一下思路。
复制二叉树非递归算法；刚开始我想着用层序遍历进行复制的，但是我意识到不是每一棵树都是每层都满的情况，所以我就转到了前序遍历来复制树。用两个队列分别来管理拷贝节点和原来树的节点。让等价节点同时入同时出完成节点和位置两者的同时拷贝。
求根到叶子的所有路径的递归算法和非递归算法；
这个递归是没有难度的，把唯一递归的root为空的情况--_root为空给去掉，即在public域里面path函数中直接返回。Private里面的就可以直接不考虑root为空了，因为下面几个判空都提前return了，或者直接不让nullptr的递归运行下去。然后判断一下是否是nullptr就能找到路径了。用一个引用ret来记录每次路径，用pa来记录不同路径，注意pa必须是拷贝，ret必须是引用，不然是不能实现的。
求幂集非递归算法；
看了递归形式的幂集的代码，我们大概就知道要用层序了。

那代码就很好写了：
8、实现二叉树所有结点的左右孩子交换；

这个题没有难度，我用递归和非递归来实现一下

递归版本
非递归：

非递归就是在层序遍历之间加一个交换左右节点的代码就行了。

9、利用层次遍历求二叉树的高度；

这里我们对层序遍历稍微做一个改变：

首先我们要了解一个东西，第一层root会push所有第二层的节点。那么我们就可以统计此时队列里面的数据量，然后一次性将此时队列里面的节点释放完，并同时push好了下一层的节点。没进行一次内部的循环，就是一层的深入。那么再用一个变量记录层数就行了。