二叉树
二叉树的性质：
二叉树的第 i 层最多有
2
i
−
1
2^{i – 1}
2i−1 个结点。由定义可知，二叉树的每个结点最多有两个孩子结点，那么第 i 层最多的结点数等于第 i−1 层最多结点数的 2 倍。而第 1 层最多只有 1 个结点，所以我们可以知道第 i 层最多有
2
i
−
1
2 ^ {i – 1}
2i−1 个结点。
深度为 k 的二叉树最多有
2
k
−
1
2 ^ k – 1
2k−1 个结点。由上一个性质，我们可以知道二叉树每层最多的结点个数，从第 1 层到第 k 层把最多结点数累加起来，我们就可以得到深度为 k 的二叉树最多有
2
k
−
1
2 ^ k – 1
2k−1 个结点。
任意一棵二叉树上，其叶子结点个数
n
0
n_0
n0 比度为 2 的结点数
n
2
n_2
n2 多 1。
我们记树上结点总个数为 n，度为 1 的结点个数为
n
1
n_1
n1 ，则有
n
=
n
0
+
n
1
+
n
2
n = n_0 + n_1 + n_2
n=n0+n1+n2 。另外我们可以发现一棵二叉树一共有 n−1 条边，度为 2 的结点可以延伸出 2 条边，度为 1 的结点可以延伸出 1 条边，叶子结点没有边延伸出来，所以又有 n – 1 =
n
1
n_1
n1 +
2
×
2 \times
2×
n
2
n_2
n2 。结合以上两个式子，我们可以得到
n
0
=
n
2
+
1
n_0 = n_2 + 1
n0=n2+1 。
二叉树的性质还有很多，下面我们来了解下两个特殊的二叉树。
第一个是 满二叉树 ，如果一棵树深度为 k 而且有
2
k
−
1
2 ^ k – 1
2k−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 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 压入栈中。
如何输出二叉树的广义表形式？
输出二叉树的广义表形式，有点类似于二叉树的先序遍历（在本章的后面几节会有先序遍历的具体介绍）。先输出根节点，如果左孩子不为空则递归输出左子树，如果右孩子不为空则递归输出右子树，在输出过程中，根据节点是否为空，在合适的地方输出左右括号以及逗号。
输出二叉树的广义表形式的伪代码如下：
输出节点存储的值；
如果左孩子不为空：
输出 "("；
递归输出左子树；
如果右孩子为空：
输出 ")"。
如果右孩子不为空：
如果左孩子为空：
输出 "("。
输出 “,”；
递归输出右子树；
输出 ")"。
#include <stdio.h>
#include <stdlib.h>
// 创建一个结点结构体Node
// 二叉树上有很多个结点，每个几点都可能会有左孩子和右孩子
// 每个结点上都有自己的数据据
typedef struct Node {
// 定义一个int 类型的变量 data , 存储结点的数据域
int data;
// 定义两个struct Node 类型的指针变量 *lchild 和 *rchild ，
//分别指向的左孩子和右孩子
struct Node *lchild, *rchild;
} Node;
// 实现初始阿虎函数 init 函数返回值是Node的指针类类型, 参数是一个int 类型的变量data。
Node* init(int data) {
// 定义一个Node 类型的指针变量node, 并分配一个Node 类型的空间大小
Node *node =(Node *)malloc(sizeof(Node));
// 把data 赋值给data
node->data = data;
// 将lchild 和 rchild 分别都 指向空地址
node->lchild = NULL;
node->rchild = NULL;
// 最后返回node
return node;
}
// 创建一个二叉树的存储函数 build_demo 函数没有参数， 返回值为 Node 的指针类型。
Node* build_demo() {
// 1. 我们先创建一个Node 类型的指针变量node 作为树的根节点，调用 初始化函数 init 完成 初始化，参数设为1， node 作为函数接受值。
Node *node = init(1);
// 2. 接下来创建跟结点的左右孩子， 根节点的左孩子的数据域是2， 右孩子的数据域是3， 那么，我们调用初始化函数 init ， 参数为2，
// 3. 根节点得到左孩子作为函数的接收值。 同样调用初始化对右孩子进行初始化，参数为3.
node->lchild = init(2);
node->rchild = init(3);
// 4. 创建结点2 的左右孩子， 结点2 的左孩子数据为4， 右孩子数据域为 5 . 这里 我们没有变量直接指向结点2，但我们知道结点2是根节点的左孩子，所以我们调用 初始化函数init, 参数为4， 根节点左孩子的左孩子做为函数的接受值， 同样调用初始化函数init, 参数为5， 根结点左孩子的右孩子做为函数的接受值。
node->lchild->lchild = init(4);
node->lchild->rchild = init(5);
// 最后我们来创建结点3 的左右孩子，因为结点3 没有左孩子， 所以我们只用创建它的右孩子即可。 和结点 2 的创建函数一样，我们给调用初始化函数 init, 参数为6， 根结点的右孩子的右孩子作为函数的接受值。 最后我们将 node 返回即可。
node->rchild->rchild = init(6);
return node;
}
// 二叉树的先序遍历
//先序遍历是二叉树遍历的一种，对于每个结点，先访问当前结点， 然后访问结点左子树，最后访问结点的右子树. 在子树里依然按照这个遍历顺序访问。
// 定义一个先序遍历的函数 preorder 函数没有返回值， 只有有一个Node 类型的指针变量 参数 node .
void preorder(Node *node) {
// 按照先序遍历的顺序，我们先访问当前结点，这一步我们把当前结点的数据域输出，为了显示清晰，我们在输出数据域后再输出一个空格。
printf("%d ", node->data);
// 访问完当前结点，接下类我们来访问结点的左子树，如果左子树不为空，那么我们就递归调用先序遍历函数 preorder, 参数设为左孩子即可， 【提示一下，我们可以看左孩子结点是否为空指针来判断它的左子树是否为空。】
if (node->lchild != NULL) {
preorder(node->lchild);
}
// 访问完左子树， 下面我们来访问右子树. 和左子树一样， 如果 左子树不为空， 则递归调用preorder 函数，参数设为 preorder ，写法同和左孩子的基本类似。
if (node->rchild != NULL) {
preorder(node->rchild);
}
}
// 中序遍历 中序遍历先访问当前结点的左子树，然后访问当前结点，最后访问右子树. 如果左右孩子不为空， 则递归调用孩子结点的中序遍历函数。
// 定义一个没有返回值，参数为一个Node 类型的指针变量node 的中序遍历 函数 inorder .
void inorder(Node *node) {
// 实现 inorder 函数 首先访问当前结点的左子树， 如果左子树不为空，则递归调用inorder 函数中序遍历左子树
if (node->lchild != NULL) {
inorder(node->lchild);
}
//访问完 左孩子结点，现在我们来访问当前结点， 我们只要不当前结点的数据域输出即可， 输出后再输出空格。
printf("%d ", node->data);
// 访问完当前结点，最后我该访问当前结点的 右子树了。如果右子树不为空，那么就递归调用 inorder 函数中序遍历右子树，这里实现方法和先序遍历 是一样的。
if (node->rchild != NULL) {
inorder(node->rchild);
}
}
// 请在下面实现后序遍历函数 postorder
void postorder(Node *node) {
if(node->lchild != NULL) {
postorder(node->lchild);
}
if(node->rchild != NULL) {
postorder(node->rchild);
}
printf("%d ",node->data);
}
// 1. 初始化函数之后定义一个没有返回值 参数为 Node 类型 的指针变量 node 的函数 clear.
void clear(Node *node) {
// 2.如果当前结点的左孩子不为空，则递归调用 clear 函数对左孩子进行操作
if (node->lchild != NULL) {
clear(node->lchild);
}
// 3.如果右孩子不为空 ，那么再递归调用clear 对右孩子进行同样的操作。
if (node->rchild != NULL) {
clear(node->rchild);
}
// 4. 最后, 再利用free 将指针 node 指向的内存 空间释放掉就可以了。
free(node);
}
int main() {
// 创建一个Node 类型的指针变量 root, 并调用 建立 函数 build_demo, 让root 作为函数接受值，建立起一棵以root 为根结点的二叉树了。
Node *root = build_demo();
// 接下来我们在主函数里调用先序函数 preorder, 先序输出以 root 为根的二叉树。 输出二叉树后， 换行操作。
preorder(root);
printf("\n");
// 请调用 中序遍历函数 inorder 完成以 root 为根的二叉树的中序遍历，之后再输出一个换行。
inorder(root);
printf("\n");
postorder(root);
printf("\n");
// 最后在函数结束前调用clear 函数释放内存。
clear(root);
return 0;
}
已知先序和中序求后序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
struct Node *lchild, *rchild;
} Node;
Node* init(int data) {
Node *node =(Node *)malloc(sizeof(Node));
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
void postorder(Node *node) {
if (node->lchild != NULL) {
postorder(node->lchild);
}
if (node->rchild != NULL) {
postorder(node->rchild);
}
printf("%d ", node->data);
}
// 已知二叉树的先序遍历和中序遍历，求后序遍历。算法过程如下： 我们可以再先序遍历里知道根结点的编号， 在中序遍历中我们找到根结点所在的位置，那么位置前面的结点就是根节点的左子树上的结点，位置后面的结点就是右子树上的结点。按照以上函数递归建立起一个二叉树，最后我们调用二叉树的后续遍历函数，输出后序遍历。
// 建立二叉树的build 函数，函数返回值为Node 类型的指针变量 参数有三个 ： char 类型的字符串pre_str, 表示二叉树的先序遍历； char 类型的字符串in_str, 表示二叉树的中序遍历； int 类型的len ， 表示 in_str 的长度，也就是中序遍历中的结点个数.
Node* build(char pre_str[], char in_str[], int len) {
// 按照先序遍历顺序，先访问当前结点， 所以我们可以从先序遍历中知道第一位 一定是当前的结点 。
// 定义一个 Node 类型的 指针变量 p , 并调用 init 初始化函数，参数为先序遍历 pre_str 的第一个字符对应的数字， 【提示一下 因为字符都是阿拉伯数字】，所以求字符a 对应的数字，可以用 a - '0' 表示。；
Node *p = init(pre_str[0] - '0');
// 现在我们知道了 根节点， 下面我们要 寻找根结点的左右树。 我们可以在中序遍历 in_str 里找到根结点的位置 pos, 根据中序遍历先访问左子树再访问根结点最后访问左子树，在pos 后面的一定是根结点的右子树。 我们可以用 strchr 函数来确定 pos.
// 我们定义 一个 int 类型的 变量 pos ，表示根结点在 in_str 里位置 ，再调用 strchr 函数 ， 参数 为 in_str 和 根结点 per_str 的第一个字符，由于 strchr 函数返回的是地址，所以需要在函数后面 减去 首地址 in_str 这样才能得到 pos 的值。
int pos = strchr(in_str, pre_str[0]) - in_str;
// 我们确定了 根结点在 in_str 里的位置 pos, 如果 pos 大于0， 则代表根结点的左子树不为空， 那么我们就可以递归的建立根结点的左子树了。
// 想想看 为什么 pos 大于 0 代表左子树不为空， 还记得中序遍历的顺序么， 先左子树再根结点 最后右子树的顺序，而 pos 指的就是根结点在的位置， 如果 pos 等于0 ， 则表明根结点的左子树 已经没有结点了， 左子树为空.
// 接下来我们来递归建立根结点的左子树。 我们调用 build 函数， 让 p 的左孩子作为函数的接受值, 最后我们来确定下函数的三个参数
// 第一个是左子树的先序遍历， 在先序遍历里我们知道 pre_str 的第0 位是根结点，第1 位开始时左子树的结点， 所以pre_str 第1 的位开始， 这里我们可以用 pre_str + 1 表示 pre_str 第1 位以后的字符串。
if (pos > 0) {
// 第二时左子树的中序遍历， 左子树的中序遍历即是 in_str 里 第 0 位 开始的字符串。
// 第三是中序遍历的长度，也就是根结点前面字符总数，自然是有 pos了， 这一步
p->lchild = build(pre_str + 1, in_str, pos);
}
// 现在我们来递归建立 右子树
// 首先我们来看看限制条件，自然是右子树不能为空，我们已经在中序遍历中找到了根结点的位置 pos， 那么pos 后面的字符个数就是右子树上的结点个数。我们可以很容易的算出 pos 后面一共有 len - pos - 1 字符，所以条件就是 len - pos -1 要大于0.
// 接下来我们调用 build 函数来递归建立 右子树，让 p 的右孩子作为函数的接收值。现在我们来确定下函数的三个参数吧。
// 第一个是右子树的先序遍历，在先序遍历
if(len - pos - 1 > 0 ) {
p->rchild = build(pre_str + pos + 1, in_str + pos + 1, len - pos -1 );
}
return p;
}
void clear(Node *node) {
if (node->lchild != NULL) {
clear(node->lchild);
}
if (node->rchild != NULL) {
clear(node->rchild);
}
free(node);
}
int main() {
char pre_str[] = "136945827";
char in_str[] = "963548127";
Node *root = build(pre_str, in_str, strlen(pre_str));
postorder(root);
printf("\n");
clear(root);
return 0;
}
接下来我们调用 build 函数 来 递归建立右子树， 让 p 的右孩子作为函数的接收值。现在我们来确定下函数的三个参数吧:
第一个是右子树的先序遍历。在先序遍历里面我们已经知道了 根结点和左子树的结点，那么最后剩下的就是右子树的结点了， 在 pre_str 里从 pos + 1 开始 到 末位的都是右子树结点。那么我们可以用 pre_str + pos + 1 来表示，表示取pre_str 第 pos + 1 位 到末位的字符串。
第二是右子树的中序遍历。在中序遍历里我们知道根结点后面的结点都是右子树上的结点。同样我们可以用 in_str + pos + 1 来表示, 表示取 in_str 第 pos + 1 位到末位的字符串。
第三是右子树中序遍历的长度。 右子树的中序遍历是in_str 第 pos + 1 位 到 末位的字符串，所以长度为u len – pos – 1 .
树的建立也就完成了， 我们最后把 怕返回结束函数 。
首先我们来完成二叉树的定义和创建， 定义一个 Node 类型的指针变量 root , 并调用 build 建立二叉树， 参数依次是 pre_str , in_str, 以及 pre_str 的长度，我们可以用 strlen 来获得它的长度。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76977.html
