前言
学习了二叉树，特此记录一下。代码可能写的不好，大神勿喷。
树
一种数据结构，下图很好的描述了这种数据结构。
树
层
基本概念(摘自《数据结构与算法分析——C语言描述(第二版)》)
路径长(Length)是指该路径上边的条数。
- 比如上图中第一层的节点到0号节点的路径长就是1。
深度(Depth)是指一个节点到root节点的唯一路径长。
- 比如上面这棵树的0号节点深度就是0。第三层节点的深度就是3。
高度(Height)是指到一片树叶的最长路径的长。
- 怎么理解这句话呢，比如，第四层18号节点的高度就是0；第二层3号节点的高度是2，4号节点的高度是1。其实高度就是和深度反着来的，深度是从上往下的，高度是从下往上的。那么一棵树的高度就是指root节点的高度，比如上面那棵树0号节点的高度就是4，所以这棵树的高度就是4。
一棵树的
深度等于它最深的树叶的深度；该深度总是等于这个树的高度。
二叉树(Binary Tree)
基于对树的概念，二叉树便是一个节点上最多有2个子节点的一种树。
二叉树
几种特殊的二叉树
-
满二叉树(Strict/Full Binary Tree)
如图所示的便是满二叉树：通过观察，也就是说，满二叉树每一个节点满足其子节点数不是=0就是=2。满二叉树
-
完美二叉树(Perfect Binary Tree)
完美二叉树更简单的说就是满二叉树的一种特殊情况，他的最底层的节点是铺满的，没有空缺的。完美二叉树
-
完全二叉树(Complete Binary Tree)
完全二叉树结合序号理解起来会好一些。
比如，我们对上面那颗完美二叉树进行标号：这样很容易就能看出来序号的规律。标号后的完美二叉树
那么，假如我们从中拿掉几颗节点：这样你就发现他的序号不连续了，出现了断裂。拿掉了一些节点的二叉树
而完全二叉树的序号是连续的，所以，下面这颗便是完全二叉树：完全二叉树
简单的二叉树性质
实现
数组存
学习了完全二叉树，你就会很好理解用数组存的方式了。
用图来表示就是这样的：
用数组存二叉树
具体的实现，可以参考我写的二叉堆：《C 堆》。
但是，使用数组有一点会很方便。通过观察数字和层数之间的关系，我们可以发现存在这这样一个规律:
| 层数H | 元素数量n |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| ... | ... |
| H |
那么每层序号的最大值便是到该层最后一个元素数量的总和 - 1，简而言之就是一等比数列求和……
那么这样就可以通过一个序号来求一个节点在树中的深度了：(N为序号数，H为层数，我是从0开始的)
结构体+指针存
根据每一个节点的特点，我们可以使用一个结构体来描述每个节点。
每一个节点的图示
用结构体来表示就是：
struct LeafNode {
int data; // 数据
struct LeafNode *left; // 左边叶子的指针
struct LeafNode *right; // 右边叶子的指针
};
由于struct LeafNode太长了，我们可以在#include<...>之后加一句
typedef struct LeafNode Node;
来方便之后操作。
遍历
有了一颗二叉树，那么怎么样才能把它读取出来呢？
通过递归
用类似DFS的思路，我们可以写出下面的方法：
void preorderTraversal(Node *nd)
{
if (nd == NULL) return;
printf("%d ",nd -> data);
preorderTraversal(nd -> left);
preorderTraversal(nd -> right);
}
阅读完代码，其实思路就是遇到一个非空元素就把它输出，然后在先往左节点走，走完了，再往右边走，一级一级往上退，直到遍历完。
这种遍历方式就叫前序遍历(Preorder Traversal)。
看完这个代码，我们也能想到把printf的位置换一下：
void inorderTraversal(Node *nd)
{
if (nd == NULL) return;
inorderTraversal(nd -> left);
printf("%d ",nd -> data);
inorderTraversal(nd -> right);
}
这样就成了中序遍历了(Inorder Traversal)。它是先遇到的节点不输出，然后第二次遇到它时再输出。
同样的，后序遍历(Postorder Traversal)就是这样的了：
void postorderTraversal(Node *nd)
{
if (nd == NULL) return;
postorderTraversal(nd -> left);
postorderTraversal(nd -> right);
printf("%d ",nd -> data);
}
它就是第三次遇到一个节点再输出的。
最后放出一张路径图：
ppt作图大法
通过队列
用队列来实现的话，这个算法就有点类似BFS了。
void levelTraversal(Node *root)
{
if (root == NULL) return; // 如果root是空的直接return掉
queue<Node*> childs; // 创建节点队列
childs.push(root); // 先把root节点加入套餐
while (childs.size() != 0) // 队列空了就结束
{
Node *current = childs.front(); // 取出队列前端的节点
printf("%d ",current -> data); // 提取数据
if (current -> left != NULL) childs.push(current -> left); // 如果不是空的，就加入套餐
if (current -> right != NULL) childs.push(current -> right); // 同上
childs.pop(); // 去掉队列前端的节点
}
}
这个其实就是层次遍历。
构建二叉树
简单的了解了二叉树的概念以及实现之后，我们将自己来构建一颗二叉树。
用类似前序遍历的方式来实现：
Node *preorderAdd(Node **node)
{
Node *n = (Node*) malloc(sizeof(Node)); // 创建新的节点
n -> left = NULL; // 初始化节点中的指针为NULL
n -> right = NULL; // 初始化节点中的指针为NULL
char c; // 用于暂时储存读入的自字符
int isEmpty = 0; // 用于记录是否要创建子节点，/就不新建了，是数字的话才新建节点
int data = 0; // 数据
int hasNum = 0; // 用于记录读入的是否为所需要的数据
while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 当读入的字符为空格或者换行符 以及 读入的字符里有数字或者/的时候挑出循环
{
if (c == '/')
{
isEmpty = 1; // 读入的是/，所以不需要新建节点
hasNum = 1; // 读入了所想要的字符
} else if (c >= '0' && c <= '9') { // 如果是数字
data = data * 10 + c - '0'; // 塞入数据
hasNum = 1; // 读入了所想要的字符
}
}
//--------------------------------上面都是一些输入----------------------------
n -> data = data; // 把数据塞入节点
if (!isEmpty) // 如果不是/，那就记录数据
{
if (node != NULL) *node = n; // 如果传入的节点为空，那就新建一个root节点
preorderAdd(&(n -> left)); // 继续添加节点的左节点
preorderAdd(&(n -> right)); // 继续添加节点的右节点
return n; // 返回节点
} else {
free(n); // 是/那就free掉
return NULL;
}
}
也可以采用类似层次遍历的方法来构建二叉树：(很早写的，代码质量不堪入目)
// 层次读入
Node *addElement()
{
queue<Node*> q;
queue<Node*> next;
int data = 0;
char input; // 输入
char last = '/'; // 方便记录/
while ((input = getchar()) != EOF)
{
if (input == '.' || input == '/') return NULL; // 如果遇到空的，直接跳过
if (input == ' ' || input == '\n') // 如果遇到了空格或者换行符
{
if (last != '/' && last != ' ' && last != '\n') // 如果上一个是数字，那就退出root节点的输入
{
last = input;
break;
}
} else if (input >= '0' && input <= '9') { // 如果是数字
data = data * 10 + input - '0'; // 塞入数据
last = input;
}
}
Node *root_nd = createNode(data); // 创建root节点
q.push(root_nd); // 把root节点加入套餐
int l_f = 0; // 0 - 左节点，1 - 右节点
int isSkip = 0; // 遇到/就跳过
data = 0; // 数据清零，方便读入
while ((input = getchar()) != '.') { // 遇到"."结束输入
if (input == ' ' || input == '\n') // 塞入数据
{
if (last == ' ' || last == '\n') continue;
if (last == '/') isSkip = 1; // 如果上一个输入为/那就当做跳过了
else isSkip = 0;
Node *nd = createNode(data); // 创建子节点
if (!isSkip) // 如果是数据
{
if (!l_f) q.front() -> left = nd; // 左边就塞左节点
else q.front() -> right = nd; // 塞右节点
next.push(nd); // 加入下一次要输入的节点的套餐
}
l_f = !l_f; // 交换
if (!l_f) q.pop(); // 输入一个数据就删掉一个节点
if (q.size() == 0) { // 节点删完了，说明要换层了
q.swap(next); // 交换下一个与当前的队列
next = queue<Node*>(); // 将下一个节点的
}
data = 0; // 清零数据
last = input; // 记录上一个读入的自字符，用于记录是否读入了/或者是空格\n之类的
} else {
last = input; // 记录上一个读入的自字符，用于记录是否读入了/
data = data * 10 + input - '0'; // 把字符转成数据
}
}
return root_nd; // 返回root节点
}
我这边输入的位数字，以输入.为结束标志，/表示空节点。
讲完了遍历&构建，那该如何实际应用呢？更具体的可以了解下别的有关二叉树的数据结构，或者去做一些二叉树的题目。
下面我就将使用前序遍历来更优雅地输出一颗二叉树。
Linux tree命令二叉树版
Linux里有一个命令叫做tree，他的作用是将当前目录下的所有文件通过递归全部输出。而我们的文件系统正是一棵树，所以我们可以用所学知识来模仿tree的格式来输出我们的二叉树，使其更具有可读性。
tree命令示意
观察图中的输出方式，我们很容易就可以理解一个目录下的详细情况，所以这种输出方式很直观。
下面我们就来尝试实现一下这个输出方式。
我们可以发现：
- 只要一个节点下方还有他的兄弟节点，那就会输出一个
|来延长树枝。如果没有的话则用空格来占位。 - 在输出数据的时候，如果一个节点是那一层中最后一个子节点的话，那就以
└──来连接数据，在中间的话，那就用├──连接。 - 数据是以前序遍历输出的。
有了这些规律，那我们就可以尝试用代码来实现一下了：
void printTree(Node *n,int h,vector<int> *l,int hasNext)
{
if (n == NULL) return; // 如果当前节点为空，那就结束递归
for (int i = 0;i < h;i ++) // 输出空格或者树枝
{
if (i == h - 1) // 输出邻近叶子的树枝
{
if (hasNext) printf("├── "); // 如果叶子在中间，那就输出凸型树枝
else {
printf("└── "); // 如果叶子在最下面，那就输出尾树枝
(*l)[i] = 0; // 标志着|可以不用再打印了
}
} else
{
if ((*l)[i]) printf("│ "); // 如果左节点有右节点，那就延长树枝
else printf(" "); // 如果没有的话，那就直接输出空格来占位
}
}
printf("%d\n",n -> data); // 输出叶子里的数据
int b = n -> right != NULL; // 记录除了左节点是否还有右节点
if (l == NULL) // 创建一个vector，用于记录左节点是否有右节点
{
vector<int> arr;
l = &arr;
}
if (l -> size() <= h) l -> push_back(b); // 将是否有右节点的信息压入vector
else (*l)[h] = b;
printTree(n -> left,h + 1,l,b); // 遍历左节点
printTree(n -> right,h + 1,l,0); // 遍历右节点
}
这样，在之后的学习中使用这个二叉树输出方法就可以很直观地观察到数据的结构，从而方便我们debug。
不过这样输出看起来其实并没有那么好，首先我们无法分辨那个是左节点，哪个是右节点，所以我们可以通过修改hasNext来让这个函数输出的左右节点更有区分度：
printTree(n -> pLeft,h + 1,l,1); // 可以显示左右节点：├为左，└为右
也就是说只要改动左节点的遍历即可。
但是，我们一般看的话可以认为这是一颗横着摆放的二叉树，而我们横过来看的话左右节点却是相反的，所以为了方便看，我再一次的修改了代码：
void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
if (n == NULL) return;
for (int i = 0;i < h;i ++)
{
if (i == h - 1)
{
if (hasNext) printf("├── ");
else {
printf("└── ");
(*l)[i] = 0;
}
} else
{
if ((*l)[i]) printf("│ ");
else printf(" ");
}
}
printf("%d\n",n -> data);
int b = n -> left != NULL;
if (l == NULL)
{
vector<int> arr;
l = &arr;
}
if (l -> size() <= h) l -> push_back(b);
else (*l)[h] = b;
// printTree(n -> pRight,h + 1,l,b); // 正常输出
printTree_h(n -> right,h + 1,l,1); // 可以显示左右节点：├为右，└为左
printTree_h(n -> left,h + 1,l,0);
}
其实就是将递归的那两句话换了个位置就好了，这样显示就顺多了。
一颗不太好看的BST树
第二种树的打印方式
之前做蓝桥杯的题的时候遇到一种比较好看的打印方式。
struct ps {
int dps;
int length;
int type;
};
void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
if (root == NULL) return;
ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
if (dps.size() <= d) dps.push_back(p);
else dps[d] = p;
print_binTree(root -> right,d + 1, 1, dps);
for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
{
if (i -> type && i -> dps != 0) printf("|");
else printf(".");
for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
{
printf(".");
}
}
if (d != 0) printf("|-");
printf("%d",root -> data);
if (root -> left != NULL || root -> right != NULL) printf("-|");
printf("\n");
dps[d].type = root -> left != NULL && lr;
print_binTree(root -> left,d + 1, 0, dps);
}
调用方法。
print_binTree(root,0,1,vector<ps>());
tree2的效果
图中正是使用了下面的全部代码。
全部代码
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
typedef struct LeafNode Node;
struct LeafNode {
int data; // 数据
struct LeafNode *left; // 左边叶子的指针
struct LeafNode *right; // 右边叶子的指针
};
Node *createNode(int data)
{
Node *rootNode = (Node*) malloc(sizeof(Node));
rootNode -> data = data;
rootNode -> left = NULL;
rootNode -> right = NULL;
return rootNode;
}
// 层次读入
Node *addElement()
{
queue<Node*> q;
queue<Node*> next;
int data = 0;
char input; // 输入
char last = '/'; // 方便记录/
while ((input = getchar()) != EOF)
{
if (input == '.' || input == '/') return NULL; // 如果遇到空的，直接跳过
if (input == ' ' || input == '\n') // 如果遇到了空格或者换行符
{
if (last != '/' && last != ' ' && last != '\n') // 如果上一个是数字，那就退出root节点的输入
{
last = input;
break;
}
} else if (input >= '0' && input <= '9') { // 如果是数字
data = data * 10 + input - '0'; // 塞入数据
last = input;
}
}
Node *root_nd = createNode(data); // 创建root节点
q.push(root_nd); // 把root节点加入套餐
int l_f = 0; // 0 - 左节点，1 - 右节点
int isSkip = 0; // 遇到/就跳过
data = 0; // 数据清零，方便读入
while ((input = getchar()) != '.') { // 遇到"."结束输入
if (input == ' ' || input == '\n') // 塞入数据
{
if (last == ' ' || last == '\n') continue;
if (last == '/') isSkip = 1; // 如果上一个输入为/那就当做跳过了
else isSkip = 0;
Node *nd = createNode(data); // 创建子节点
if (!isSkip) // 如果是数据
{
if (!l_f) q.front() -> left = nd; // 左边就塞左节点
else q.front() -> right = nd; // 塞右节点
next.push(nd); // 加入下一次要输入的节点的套餐
}
l_f = !l_f; // 交换
if (!l_f) q.pop(); // 输入一个数据就删掉一个节点
if (q.size() == 0) { // 节点删完了，说明要换层了
q.swap(next); // 交换下一个与当前的队列
next = queue<Node*>(); // 将下一个节点的
}
data = 0; // 清零数据
last = input; // 记录上一个读入的自字符，用于记录是否读入了/或者是空格\n之类的
} else {
last = input; // 记录上一个读入的自字符，用于记录是否读入了/
data = data * 10 + input - '0'; // 把字符转成数据
}
}
return root_nd; // 返回root节点
}
Node *preorderAdd(Node **node)
{
Node *n = (Node*) malloc(sizeof(Node)); // 创建新的节点
n -> left = NULL; // 初始化节点中的指针为NULL
n -> right = NULL; // 初始化节点中的指针为NULL
char c; // 用于暂时储存读入的自字符
int isEmpty = 0; // 用于记录是否要创建子节点，/就不新建了，是数字的话才新建节点
int data = 0; // 数据
int hasNum = 0; // 用于记录读入的是否为所需要的数据
while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 当读入的字符为空格或者换行符 以及 读入的字符里有数字或者/的时候挑出循环
{
if (c == '/' || c == '.')
{
isEmpty = 1; // 读入的是/，所以不需要新建节点
hasNum = 1; // 读入了所想要的字符
} else if (c >= '0' && c <= '9') { // 如果是数字
data = data * 10 + c - '0'; // 塞入数据
hasNum = 1; // 读入了所想要的字符
}
}
n -> data = data; // 把数据塞入节点
if (!isEmpty) // 如果不是/，那就记录数据
{
if (node != NULL) *node = n; // 如果传入的节点为空，那就新建一个root节点
preorderAdd(&(n -> left)); // 继续添加节点的左节点
preorderAdd(&(n -> right)); // 继续添加节点的右节点
return n; // 返回节点
} else {
free(n); // 是/那就free掉
return NULL;
}
}
// 前序遍历
void preorderTraversal(Node *nd)
{
if (nd == NULL) return;
printf("%d ",nd -> data);
preorderTraversal(nd -> left);
preorderTraversal(nd -> right);
}
// 中序遍历
void inorderTraversal(Node *nd)
{
if (nd == NULL) return;
inorderTraversal(nd -> left);
printf("%d ",nd -> data);
inorderTraversal(nd -> right);
}
// 后序遍历
void postorderTraversal(Node *nd)
{
if (nd == NULL) return;
postorderTraversal(nd -> left);
postorderTraversal(nd -> right);
printf("%d ",nd -> data);
}
// 层次遍历
void levelTraversal(Node *root)
{
if (root == NULL) return; // 如果root是空的直接return掉
queue<Node*> childs; // 创建节点队列
childs.push(root); // 先把root节点加入套餐
while (childs.size() != 0) // 队列空了就结束
{
Node *current = childs.front(); // 取出队列前端的节点
printf("%d ",current -> data); // 提取数据
if (current -> left != NULL) childs.push(current -> left); // 如果不是空的，就加入套餐
if (current -> right != NULL) childs.push(current -> right); // 同上
childs.pop(); // 去掉队列前端的节点
}
}
void printTree(Node *n,int h,vector<int> *l,int hasNext)
{
if (n == NULL) return; // 如果当前节点为空，那就结束递归
for (int i = 0;i < h;i ++) // 输出空格或者树枝
{
if (i == h - 1) // 输出邻近叶子的树枝
{
if (hasNext) printf("├── "); // 如果叶子在中间，那就输出凸型树枝
else {
printf("└── "); // 如果叶子在最下面，那就输出尾树枝
(*l)[i] = 0; // 标志着|可以不用再打印了
}
} else
{
if ((*l)[i]) printf("│ "); // 如果左节点有右节点，那就延长树枝
else printf(" "); // 如果没有的话，那就直接输出空格来占位
}
}
printf("%d\n",n -> data); // 输出叶子里的数据
int b = n -> right != NULL; // 记录除了左节点是否还有右节点
if (l == NULL) // 创建一个vector，用于记录左节点是否有右节点
{
vector<int> arr;
l = &arr;
}
if (l -> size() <= h) l -> push_back(b); // 将是否有右节点的信息压入vector
else (*l)[h] = b;
printTree(n -> left,h + 1,l,b); // 遍历左节点
printTree(n -> right,h + 1,l,0); // 遍历右节点
}
void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
if (n == NULL) return;
for (int i = 0;i < h;i ++)
{
if (i == h - 1)
{
if (hasNext) printf("├── ");
else {
printf("└── ");
(*l)[i] = 0;
}
} else
{
if ((*l)[i]) printf("│ ");
else printf(" ");
}
}
printf("%d\n",n -> data);
int b = n -> left != NULL;
if (l == NULL)
{
vector<int> arr;
l = &arr;
}
if (l -> size() <= h) l -> push_back(b);
else (*l)[h] = b;
// printTree(n -> pRight,h + 1,l,b); // 正常输出
printTree_h(n -> right,h + 1,l,1); // 可以显示左右节点：├为右，└为左
printTree_h(n -> left,h + 1,l,0);
}
struct ps {
int dps;
int length;
int type;
};
void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
if (root == NULL) return;
ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
if (dps.size() <= d) dps.push_back(p);
else dps[d] = p;
print_binTree(root -> right,d + 1, 1, dps);
for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
{
if (i -> type && i -> dps != 0) printf("|");
else printf(".");
for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
{
printf(".");
}
}
if (d != 0) printf("|-");
printf("%d",root -> data);
if (root -> left != NULL || root -> right != NULL) printf("-|");
printf("\n");
dps[d].type = root -> left != NULL && lr;
print_binTree(root -> left,d + 1, 0, dps);
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Type of building tree (p/l/other=exit):");
char cmd;
set<int> type = {'p','l'};
while (scanf(" %c",&cmd) != EOF && type.find(cmd) != type.end())
{
Node *root = NULL;
switch (cmd) {
case 'p':
root = preorderAdd(NULL);
break;
case 'l':
root = addElement();
break;
}
printf("preorder:\n");
preorderTraversal(root);
printf("\ninorder:\n");
inorderTraversal(root);
printf("\npostorder:\n");
postorderTraversal(root);
printf("\nlevel:\n");
levelTraversal(root);
printf("\ntree:\n");
printTree_h(root,0,NULL,0);
printf("\ntree2:\n");
print_binTree(root,0,1,vector<ps>());
printf("Type of building tree (p/l/other=exit):");
}
return 0;
}
运行截图：
截图
注：这个是之前的老图，是我之前的代码的效果，我更新了代码，具体效果是上面的那幅图。
