二叉树习题集一

末蓝、 2022-05-09 09:48 276阅读 0赞

## 二叉树 习题集一 ##

> 1、若要惟一地确定一棵二叉树，只需知道该二叉树的（D）

A.前序序列
    B.中序序列
    C.前序和后序序列
    D.中序和后序序列

有两种情况不能确定一棵树：  
（1）只知道先序序列或只知道后序序列  
（2）只知道先序序列和后序序列

> 2、若中序遍历平衡的二叉排序树,可得到排好序的关键码序列。 对

什么是二叉排序树？  
二叉排序树（Binary Sort Tree）或者是一颗空树；或者是具有以下性质的二叉树：  
（1）若它的左子树不为空，则左子树上的所有值均小于它根节点上的值；  
（2）若它的右子树不为空，则右子树上的值均大于根结点的值；  
（3）它的左右子树也分别为二叉排序树  
二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。

扩展：  
什么是平衡二叉树？  
平衡二叉树（Balanced Binary Tree或Height—Balanced Tree）又称AVL树，它或者是一颗空树，或者是具有下列性质的二叉树：  
（1）它的左右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。  
（2）若将二叉树节点的平衡因子BF（Balanced Factor）定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有节点的平衡因子只可能是-1，0或1。若有一个节点的平衡因子的绝对值大于一，则该二叉树就是不平衡的 。

> 3、如果完全二叉树从根结点开始按层次遍历的输序列为1,2,3,4,5,6,7,则该完全二叉树是二叉排序树。 错

二叉树分类很多，其中满二叉树和完全二叉树比较特殊，因为这两种二叉说效率很高。  
首先是满二叉树：从形象上来说满二叉树是一个绝对的三角形，也就是说它的最后一层全部是叶子节点，其余各层全部是非叶子节点，如果用数学公式表示那么其节点数n=2^k-1其中k表示深度，也就是层数。也就是说满二叉树的节点数是一系列固定的数，比如说，1,3,7,15…如果节点数不是这个序列中的数，那么他肯定不是满二叉树，当然了，反之，是不成立的。  
满二叉树的性质：  
（1）节点数和深度的关系 n=2^k-1  
（2）第i层上的节点数为2^(i-1)  
（3）给所有的节点编号（从1号开始而不是从零号开始）那每对于一个编号为i的节点我们可以根据i的大小，判断出他是左节点还是右节点，父节点是谁，子节点是谁。比如我们给一个编号13的节点，那么他是基数所以他是右节点，因为节点的左右变化和数据的基偶性是同步变化的。他的父节点是13/2=6(是从1好开始的)他的左子节点是13*2=26右子节点是13*2+1=27同理还可以求他的兄弟节点，父节点的父节点，

故：在满二叉树中只要有了一个节点的编号那么他在整个二叉树中的位置就确定了，正是由于这个原因，我们更倾向于使用顺序结构而不是链式结构来存储满二叉树。

完全二叉树的节点个数是任意的，从形式上来说他是一个可能有缺失的三角形，但所缺部分肯定是右下角的某个连续部分。这样说不玩整，更准确来说，我们可以说他和满二叉树的区别是，他的最后一行可能不是完整的，但绝对是右方的连续部分缺失。用数学公式讲，对于K层的完全二叉树，其节点数的范围是2(k-1)-1<N<2k-1;

一棵深度为k且有2的k次方减1个结点的二叉树是满二叉树。  
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，（即若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树）称为完全二叉树。

> 4、如果有n个节点用二叉树来存储，那么二叉树的最小深度为(A)

A.Log2(n+1)
    B.Log2(n)
    C.Log2(n-1)
    D.n/2

解析：  
（1）n节点的二叉树，既然深度最小，那么就应该是完全二叉树了；  
（2）完全二叉树的高度计算节点和高度的关系是2^n-1;  
（3）反转过来通过节点求高度，那么就是log2(n+1)了。如果向上取整为：1+log2 n

> 5、若在一棵(分类)平衡树T中先删除某结点N,然后再插入该结点N,得到的新的平衡树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的平衡树T2一定与T完全相同。 错

解析：  
平衡树的特点：  
（1）左右子树的高度差的绝对值不超过 1（左右子树的高度差为该结点的平衡因子，只能取 -1， 0， 1）， 且其左右子树也是平衡树。  
（2）向平衡树中插入结点时，该结点一定是插入在叶子节点上的，这时需要检查平衡树的各结点的平衡因子，如果有平衡因子的绝对值大于 1的结点存在 ， 就需要调整结点使其再次满足平衡树的性质。删除结点的时候也要检查平衡树的性质是否被破坏，然后做出相应的调整，具体的调整方法在这里就不再赘述。

综上，如果删除的结点N是叶子结点且删除之后平衡树不会涉及调整，那么再次插入该结点，树是相同的，否则就不同。同理，先插入结点M，若其不改变平衡树的性质，再删除结点M，树是相同的，否则就会不同。

若在一棵(分类)二叉排序树T中先删除某结点N,然后再插入该结点N,得到的新的二叉排序树T1,则T和T1不一定相同。但是如果在T上先插入结点M,然后再删除M结点,那么得到的新的二叉排序树T2一定与T完全相同。 对

> 6、已知一棵二叉树的先序和中序遍历序列如下：先序：A、B、C、D、E、F、G、H、I，J中序：C、B、A、E、F、D、I、H、J、G其后序遍历序列为：(E)

A. C、B、D、E、A、G、I、H、J、F
    B. C、B、D、A、E、G、I、H、J、F
    C. C、E、D、B、I、J、H、G、F、A
    D. C、E、D、B、I、H、J、G、F、A
    E. C、B、F、E、I、J、H、G、D、A
    F. C、B、F、E、I、H、J、G、D、A

解析：  
1.由先序，知A是根  
2.由中序，知B、C为A左子树，D、E、F、G、H、I、J为A右子树  
3.由先序，知B为A左子树根  
4.由后序，知C为B左子树  
5.由先序，知D为A右子树根  
6.由中序，知E、F为D左子树，G、H、I、J位D右子树  
7.由先序，知E为D左子树根  
8.由后序，知F为E左子树  
9.由先序，知G为D右子树根  
10.由中序，知H、I、J为G左子树  
11.由先序，知H为G左子树根  
12.由中序，知I为H左子树，J为H右子树  
13.树推导构造完毕

> 7、初始序列为1 8 6 2 5 4 7 3的一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为：(A)

A. 8 3 2 5 1 6 4 7
    B. 3 2 8 5 1 4 6 7
    C. 3 8 2 5 1 6 7 4
    D. 8 2 3 5 1 4 7 6

解析：  
考察点：堆排序的建堆以及调整堆的操作  
1.堆在内存中的表现形式是以数组的形式存储  
2.堆是一个完全二叉树  
建堆：建堆的过程就是一个反复筛选的过程  
1.每次都插到数组的末端，形成一个完全二叉树；  
2.从最后一个非终端节点开始，直到第一个节点为止（只和子节点比较）；  
删除堆：  
1.每次都是删除第一个；  
2.然后最后一个数字补进来；  
3.然后调整堆  
调整堆：  
1.每次都是与最小的儿子进行交换；  
2.每次都是从倒数第一个非终端节点开始调整；

二叉堆的定义  
二叉堆是完全二叉树或者是近似完全二叉树。  
二叉堆满足二个特性：  
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。  
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。  
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

> 8、在9阶B-树中,除叶子以外的任意结点的分支数介于5和9之间。 错

B-树的详解：  
[https://blog.csdn.net/qq\_35644234/article/details/66969238][https_blog.csdn.net_qq_35644234_article_details_66969238]

1、背景知识  
动态查找树主要有：二叉查找树，平衡二叉查找树，红黑树，B-tree/B±tree/ B\*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

必须面对的一个实际问题：就是在大规模数据存储中，实现索引查询，由于树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），而如果元素数量较多的话，会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是（解决方案）：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

于是提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，即B树结构(后面，我们将看到，B树的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率)。

2、B-树的介绍  
B-树其实就是我们平时所说的B树，除了B-树外，还有另外一种叫B+树，我们这里先介绍什么是B-树：  
B-树是一种平衡的多路查找树，它在文件系统中很有用（原因之前已经介绍了）。  
B-树的结构有如下的特点：  
**一棵度为m的B-树称为m阶B-树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分  
为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求  
m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：**  
树中的每个结点至多有m颗子树。  
若根结点不是叶子结点，则至少有两颗子树。  
除根结点外，所有非终端结点至少有\[ m/2 \] ( 向上取整 )颗子树。  
所有的非终端结点中包括如下信息的数据

（n,A0,K1,A1,K2,A2,….,Kn,An）  
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，  
Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.

n 为关键码的个数。  
所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

> 9、一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是(B)

A. 0
    B. 1
    C. 2
    D.不确定

解析：

注意：前序和后续线索化都是1，中序是2。

> 10、已知二叉树Node定义如下, 现在需要设计一个方法交换左子树和右子树, 下列方法中, 可以实现交换的是? （D）

class Node {
    public:    
    	Node* left;    
    	Node* right;    
    	char content;    
    	Node(char content);
    private:    
    	Node(const Node&);    
    	Node& operator=(const Node& node);
    };

--------------------

A. void swap(Node root) {Node* temp=root.left;root.left=root.right;root.right=temp;}
    B. void swap(Node& left, Node& right) {Node temp=left; left=right;right=temp;}
    C. void swap(Node* left, Node* right) {Node* temp=left; left=right;right=temp;}
    D. void swap(Node*& left, Node*& right) {Node* temp=left; left=right;right=temp;}

解析：  
要交换二叉树的左右子树的方法可以有两种方法：  
（1）是传递参数根结点，选项A就是这种方法，不过根结点的类型应该是Node \* ，即为：  
void swap(Node *root) \{Node* temp=root->left; root->left=root->right; root->right=temp;\}，  
否则修改的只是实参的副本，并不能真正修改实参。不懂的话去看一下参数传递的三种方式（值传递，指针传递，引用传递），这里的D选项就是值传递，值传递的只是实参的一个副本，函数对参数的修改只是体现在实参的副本上并不会体现在实参上。  
（2）是直接传递左右子树，二叉树的左右孩子都是指针类型，要修改指针类型的变量应该用指针的指针（\*\*）或者指针的引用（\*&）类型。

[https_blog.csdn.net_qq_35644234_article_details_66969238]: https://blog.csdn.net/qq_35644234/article/details/66969238