数据结构-树

树

树是由若干个有限结点组成的一个具有层次关系的集合，每棵树有且仅有一个根，比如在图中，最上面的结点就是树的根结点。例子里的/、etc、usr、lib等等都是这棵树上的结点，其中/是树的根结点。

二叉树

二叉树的性质

二叉树的第 i 层最多有 $2^{i−1} 2i−1 个结点。$
由定义可知，二叉树的每个结点最多有两个孩子结点，那么第 i 层最多的结点数等于第 i−1 层最多结点数的 2 倍。而第 1 层最多只有 1 个结点，所以我们可以知道第 i 层最多有 $2 i − 1 2 ^ {i – 1} 个结点。$
深度为 k 的二叉树最多有
任意一棵二叉树上，其叶子结点个数 $n_0 n0 比度为 2 的结点数 n 2 n_2 n2 多1。$
我们记树上结点总个数为 n，度为 1 的结点个数为 $n_1 n1，则有 n = n 0 n_0 n0 + n 1 n_1 n1 + $n_2 n=n 。$
另外我们可以发现一棵二叉树一共有 n−1 条边，度为 2 的结点可以延伸出 2 条边，度为 1 的结点可以延伸出 1 条边，叶子结点没有边延伸出来，所以又有 n – 1= $n_1 n1 + 2 × n 2 n_2 n2 。$
结合以上两个式子，我们可以得到 $n_0 n0 = n 2 n_2 n2 + 1。$

满二叉树和完全二叉树

第一个是 满二叉树 ，如果一棵树深度为 k 而且有

−

2 ^ k – 1

$2^{k} - 1$ 个结点，那么我们称该二叉树为满二叉树，也就是说在此深度上，不能再添加结点了。
第二个是完全二叉树，如果一棵树深度为 k，从第 1 层到第 k – 1 层该树是满二叉树，第 k 层的结点都集中在左边，那么我们称该二叉树为完全二叉树。完全二叉树因其结构的特殊性具有很高的效率，经常被用在算法的优化里。

二叉树的广义表表示形式

我们可以用广义表来表示二叉树，形式为 a(b,c)，表示根节点 a 的左孩子节点为 b，右孩子节点为 c，中间用一个逗号隔开。如果左右孩子节点不为空，则用以上形式来替换；如果节点为空，则不填任何字符。以下是几种常见的格式：

a：表示根节点为 a，左右孩子节点均为空；
a(b)：表示根节点为 a，左孩子节点为 b，右孩子节点为空；
a(,c)：表示根节点为 a，左孩子节点为空，右孩子节点为 c；
a(b,c)：表示根节点为 a，左孩子节点为 b，右孩子节点为 c。
如 7(4(3,6),15(,55)) 可以表示以下这棵二叉树：

如何将广义表创建成二叉树

将广义表创建成二叉树，可以借助栈来实现，利用栈先进后出的特点，先将根节点压入栈中，如果左孩子节点不为空，则将其作为栈顶节点（即其父亲节点）的左孩子节点，并压入栈中，递归左子树，处理完之后左孩子节点出栈；如果右孩子不为空，则将其作为栈顶节点（即其父亲节点）的右孩子节点，并压入栈中，递归右子树，处理完之后右孩子节点出栈。
在转换过程中，我们可以这么理解，左括号表示进入二叉树的下一层，右括号表示返回上一层，逗号表示从左子树转到右子树。
用广义表创建二叉树的伪代码如下：

设置一个标记变量 k，初始为 -1；
设置一个标记节点 p；
循环遍历存储广义表的字符串 str：
    如果 str[i] 是左括号：
        则设置 k 为 0；
        把 p 压入栈中。
    否则如果 str[i] 是逗号：
        则设置 k 为 1。
    否则如果 str[i] 是右括号：
        则栈顶元素出栈。
    否则如果 str[i] 是一个字母，用节点 temp 来存储：
        如果 k 为 -1：
            则把 temp 作为根节点并压入栈中。
        如果 k 为 0：
            如果此时栈顶节点是 p，则先出栈；
            然后将 temp 作为栈顶节点的左孩子；
            再把 temp 压入栈中。
        如果 k 为 1：
            栈顶元素出栈；
            将 temp 作为栈顶节点的右孩子；
            再把 temp 压入栈中。

如何输出二叉树的广义表的形式

输出二叉树的广义表形式，有点类似于二叉树的先序遍历。先输出根节点，如果左孩子不为空则递归输出左子树，如果右孩子不为空则递归输出右子树，在输出过程中，根据节点是否为空，在合适的地方输出左右括号以及逗号。
输出二叉树的广义表形式的伪代码如下：

输出节点存储的值；
如果左孩子不为空：
    输出 "("；
    递归输出左子树；
    如果右孩子为空：
        输出 ")"。
如果右孩子不为空：
    如果左孩子为空：
        输出 "("。
    输出 “,”；
    递归输出右子树；
    输出 ")"。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/77026.html