【数据结构】五分钟带你快速解决“基础”二叉树

一、二叉树中的一些基础结论

一棵N个结点的树有N-1条边

父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点； 结点的度：一个结点有几个孩子，他的度就是多少； 树的度：一棵树中，最大的结点的度称为树的度； 叶子结点/终端结点：度为 0 的结点称为叶结点； 分支结点/非终端结点：度不为 0 的结点； 兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)； 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层， 树的高度或深度：树中结点的最大层次； 结点的祖先：从根到该结点所经分支上的所有结点； 路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列； 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。 森林：由 m（m>0） 棵互不相交的树的集合称为森林；

如果一个树是满二叉树，他的层数为K，则他的结点总数是(2^K) - 1；

根据满二叉树的特点可知： 1）若规定根结点的层数为 1 ，则一棵非空二叉树的第 K 层上最多有 2^(K - 1) 个结点 2）若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 (2^h) - 1 3）若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 h  =  log (n + 1)( log 以2为底， n+1 为对数)

向上调整算法建堆时间复杂度为：O(n ∗ log n) 向下调整算法建堆时间复杂度为：O(n)

堆排序时间复杂度为：O(n log n) TOP-K问题时间复杂度：O(n) =k+ (n−k)log k

上述的算法以及更多内容可以详见前俩篇顺序结构二叉树和链式结构二叉树的博客。

我们要记住三种遍历规则： 1）前序遍历：根左右 2）中序遍历：左根右 3）后序遍历：左右根

//前序遍历 -- 根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历 -- 左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历 -- 左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

二、填空题

1、某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（   ）

解析： 我们根据二叉树的性质可以知道：n0 = n2 + 1，叶子结点就是度为0的结点，所有n0 = 199 + 1 = 200

2、在具有 2N 个结点的完全二叉树中，叶子结点个数为（   ）

解析： 我们知道二叉树中：n0 + n1 + n2 = 2N，n0 = n2 + 1；将俩个式子进行联立将n2消掉：2n0 + n1 = 2N + 1；我们随意的画出奇数个结点的完全二叉树与偶数个结点的完全二叉树来进行比较：  

我们可以看到他的度为1的结点要么是1要么是0，原来的结点为偶数，所有他的n1 = 1；带入原式中得：2n0 = 2N，即n0 = N，故叶子结点的个数为 N

3、一棵完全二叉树的结点数位为 531 个，那么这棵树的高度为（   ）

解析： 根据满二叉树的性质我们可以知道他的结点数 n = (2^h) - 1；而满二叉树是完全二叉树的一种，他的n <= (2^h) - 1，我们带入可得 h >= log (n+1)（log以2为底）即h >= log 532，我们可以知道前九层结点个数为 2^9 - 1 = 511，第十层最大结点数为2^(10 - 1) = 512 ，所以这棵二叉树的第10层结点数为531 - 511 = 20，没有达到最大，故这棵二叉树一共有10层

4、一个具有 767 个结点的完全二叉树，其叶子结点个数为（   ）

解析： 依旧根据二叉树中性质：n0 = n2 + 1，n1 + n2 + n0 = 767；联立消去n2，即2n0 + n1 = 768；由上一题我们可以知道完全二叉树度为 1 的结点个数要么为 0 要么为 1，根据题意我们知道他的结点数为奇数，所有n1 = 0，故n0 = 768 / 2 = 384

5、某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（   ）

解析： 根据层序序列我们可以画出二叉树如图所示：

我们根据前序遍历的遍历规则：根左右，可以得出：

如图所示前序遍历为：A B D H E C F G

6、二叉树的前序遍历和中序遍历如下：前序遍历：EFHIGJK；中序遍历：HFIEJKG.则二叉树根结点为（   ）

解析： 根据三种遍历规则我们知道先序遍历就是先根遍历，我们先打印的就是根，所以这题求根结点就是先序遍历的第一个字母：E，我们根据先序遍历和中序遍历尝试给出这题的二叉树的图解：

下面给出推导过程供大家参考：

7、设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为（   ）

解析： 我们知道了中序遍历和后序遍历来求前序遍历，实际还是去为了画出二叉树的图：我们根据后续遍历的遍历规则可以知道a是根结点，在回到中序遍历中，可以知道b就是a的左结点，且这棵二叉树左子树就是一个b，从剩下三个结点并根据后续遍历可知，c就是a的右结点，d就是c的左结点，e就是c的右结点，画出二叉树图：

我们可以写出前序遍历就是：a b c d e

8、某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右） 的序列（   ）

解析： 我们依旧根据遍历规则尝试去画出二叉树的示意图，我们知道后序遍历的尾结点就是二叉树的根节点，故根节点是F，而中序遍历的最后一个结点同样是F，故这棵二叉树没有右结点，我们便可以很快画出二叉树：

所以他的层序序列：F E D C B A