15张图来了解【树】，面试再也不怕被刷了
共 5364字，需浏览 11分钟
·
2020-11-01 11:03
我之前的文章
树的概念
什么是树？
树属于非线性数据结构的一种，概念也极多，是由结点或顶点和边组成的且不存在着任何环的一种数据结构。
没有结点的树称为空树。一棵非空的树包括一个根结点，还很可能有多个附加结点，并且所有结点构成一个多级分层结构。
树的定义
n个节点组成的有限集合。n=0，空树；n>0,1个根节点，m个互不相交的有限集，每个子集为根的子树，如图所示为一颗树：
树的基本术语
节点的度：树中某个节点的子树的个数。
树的度：树中各节点的度的最大值。
分支节点：度不为零的节点。
叶子节点：度为零的节点。
路径：i->j；
路径长度：路径经过节点数目减1。
孩子节点：某节点的后继节点；
双亲节点：该节点为其孩子节点的双亲节点（父母节点）；
兄弟节点：同一双亲的孩子节点；
子孙节点：某节点所有子树中的节点；
祖先节点：从树节点到该节点的路径上的节点；
节点的层次：根节点为第一层，以此类推；
树的高度：树中节点的最大层次；
有序树：树中节点子树按次序从左向右安排，次序不能改变；
无序树：与有序树相反；
森林：互不相交的树的集合。
树的性质
树的节点树为所有节点度数加1（加根节点）。
度为m的树中第i层最多有
m^(i-1)个节点。高度为h的m次树至多
(m^h-1)/(m-1)个节点。具有n个节点的m次树的最小高度为
logm( n(m-1) + 1 )向上取整。
二叉树
二叉树简介
二叉树是n(n>=0)个结点的有限集合，每一个结点中最多拥有一个左结点和一个右结点，并且没有多余的结点，如图所示：
二叉树的特点
根据二叉树的定义以及图示分析得出二叉树有以下特点：
每个结点最多有两颗子树，不存在度大于2的结点。
左子树和右子树的次序不能任意颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树的性质
二叉树具有以下几种特征
二叉树第i层上的结点数目最多为
2{i-1} (i≥1)。深度为k的二叉树至多有
(2{k}-1)(k≥1)个结点。包含n个结点的二叉树的高度至少为
log2 (n+1)。在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则
n0=n2+1。
几种特殊的二叉树
斜树
所有的结点都只有左(右)子树的二叉树叫左(右)斜树，统称为斜树，如图所示：
满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树，其有以下特点
叶子只能出现在最下一层，否则就不可能达成平衡。
非叶子结点的度一定是2。
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
二叉树的存储
简介
以创建一颗二叉树，并实现通过特定的插入顺序和读取顺序达成读取为顺序为例子进行简介。
结点设计
一颗二叉树的结点设计一定要有如下内容：
结点元素，data域，用来存储数据；
左孩子结点，left指针，用来指向当前结点的下一层的左边结点；
右孩子结点，right指针，用来指向当前结点的下一层的右边结点；
除此之外，我们使用一棵树的时候需要建立一颗树根，由这个根，来进行逐步的向下构建，其代码如下：
//树的结点
typedef struct node{
int data;
struct node* left;
struct node* right;
} Node;
//树根
typedef struct {
Node* root;
} Tree;
树的创建
首先创建一个空的结点进行连接，将这个空的结点中的date域赋予数据，再判断tree中是否是一个空树，如果为空，只需要将整个根指向这一个结点即可，如果不为空，再进行两个判断，判断输入的数据是否大于或者小于当前比对的结点数据，根据其大小进行相应的排列，这样存储进入的数据总是有一定规律的，在输出的时候根据这个规律进行输出即可，其代码可以显示为：
//创建树--插入数据
void insert(Tree* tree, int value){
//创建一个节点，让左右指针全部指向空，数据为value
Node* node=(Node*)malloc(sizeof(Node));
node->data = value;
node->left = NULL;
node->right = NULL;
//判断树是不是空树，如果是，直接让树根指向这一个结点即可
if (tree->root == NULL){
tree->root = node;
} else {//不是空树
Node* temp = tree->root;//从树根开始
while (temp != NULL){
if (value < temp->data){ //小于就进左儿子
if (temp->left == NULL){
temp->left = node;
return;
} else {//继续往下搜寻
temp = temp->left;
}
} else { //否则进右儿子
if (temp->right == NULL){
temp->right = node;
return;
}
else {//继续往下搜寻
temp = temp->right;
}
}
}
}
return;
}
遍历，显示树
代码如下：
//树的中序遍历 In-order traversal
void inorder(Node* node){
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
树的遍历之先序遍历二叉树
遍历简介
遍历是按照一定的规则性，将数据结构中的所有数据全部依次访问，而二叉树需要通过在各节点与其孩子之间约定某种局部次序，间接地定义某种全局次序。
先序遍历：根左右
先序遍历：
先序遍历就是在访问二叉树的结点的时候采用，先根，再左，再右的方式，对于一个最简单的访问而言如下图，先序遍历的访问顺序就是A，B，C
多个结点相互嵌套构成的二叉树如图所示，在访问遍历一开始的时候，先访问根结点A，次访问左节点B，由于左结点中嵌套了一组结点，因此左节点又作为下一个结点的根结点。
继续沿着B访问到了D，同样由于D中包含了一组新的结点，D又作为根节点继续访问，就又访问到了E，由于E没有后面的结点了，作为D为根的左结点E访问结束后，访问到F，这一组访问结束之后再回退访问G，那么这一个二叉树的先序遍历访问顺序就是：ABDEFGCH
代码实现
//树的先序遍历 Preorder traversal
void preorder(Node* node){
if (node != NULL)
{
printf("%d ",node->data);
inorder(node->left);
inorder(node->right);
}
}
扩展->前缀表达式
我们日常的运算表达式通常是如下形式，这种成为中缀表达式，也就是运算符在运算数的中间，如图，为常规表达式：(a+b)*c
其二叉树的表现形式为：
而前缀表达式的表达方式就是 *+cab ，它的一个特征就是符号迁移，常规的表达式是需要大量的括号表达先后顺序的，而这样的表达式表达形式不需要，更容易让计算机处理。
我们常规的表达式的计算是中序的，而计算机更方便对前缀表达式这样的方式进行理解，进行这样的转换首先思路要进行转换。
在代码中我们实现这样的转换一般可以利用栈，熟练书些这样的转换就需要STL的掌握。
树的遍历之中序遍历二叉树
简介
中序遍历：左根右
如下图，就一个最简单的二叉树遍历而言，中序遍历的遍历访问过程是先B再A再C。
多个结点构成的如图所示，进行第一次访问的时候，我们在ABC中进行遍历，由左根右的顺序，我们遍历访问到B，B同时又作为BDG的根结点，因此需要继续向下进行遍历。
此时我们遍历到DEF，这时E属于这一组之中的左结点，因此我们根据根左右的先后顺序得到了最先的遍历效果，EDF。
这EDF同时作为BDG中的左节点（把EDF看作一个整体）进行回溯，此时的访问的结点顺序为EDFBG。
同理EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC，左半部分访问完毕接着访问右半部分，我们将^CH（^表示空）看作一组左中右，而C就是由EDFBGAC组合而成，因此最终的遍历顺序为：EDFBGACH
代码实现
//树的中序遍历 In-order traversal
void inorder(Node* node){
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
中缀表达式（常规算式）
中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式，也是人最容易理解的表达式形式。
如图，为常规表达式：(a+b)*c
其二叉树的表现形式为：
由前文可知前缀表达式的表达方式就是 *+cab ，我们常规的表达式的计算是中序的，其表达式就是(a+b)*c。
我们可以理解为将表达式利用二叉树化，然后通过中序遍历的方式进行提取，如果需要发生组合时，需要我们借助括号的形式表示优先级，这样也有一个弊端，就是当多个嵌套的时候需要的括号较多。
树的遍历之后序遍历二叉树
简介
后序遍历：左右根
后序遍历就是在访问二叉树的结点的时候采用，先左，再右，再根的方式，对于一个最简单的访问而言如图，先访问左节点B，之后访问右结点C，最后访问根节点A，后序遍历的访问顺序就是BCA
多个结点相互嵌套构成的二叉树如下图所示，在访问遍历一开始的时候，先访问左节点B再访问右结点C最后访问A；
由于B结点其中也包含了新的结点，在面对处理的结点后还存在有与之相联的结点的时候，需要优先处理其的子结点，这也是“递归”的基本思路；
因此，由于B属于DG的根结点，相较于B，应该先访问D结点，而又由于D结点属于EF的根结点，就又变成先访问E结点，E属于最末端了，根据后序遍历左右根的访问顺序，依次生成EFDGB作为一个整体；
接着我们需要访问C，由于C又是^HC之中的根结点，我们先访问这个空结点，又因为其是一个空的结点，我们会跳过，就变成了HC的访问顺序；
最后在汇总的时候EFDGB作为左节点，HC作为右结点，A作为根结点，完成我们最终的遍历顺序EFDGBHCA。
代码实现
//树的后序遍历 Post-order traversal
void postorder(Node* node){
if (node != NULL)
{
inorder(node->left);
inorder(node->right);
printf("%d ",node->data);
}
}
后缀表达式
后缀表达式与前缀表达式不同，前缀表达式采用先序遍历的方式遍历访问我们的公式顺序，常规式则就是中序方式，而后缀表达式采用后续遍历的方式进行访问。
如图，为常规表达式：(a+b)*c
其二叉树的表现形式为：
而后缀表达式的表达方式就是ab+c* ，相较于前缀表达式，后缀表达式则就是将符号进行后移，其在计算机中的读取运算概念也符合栈的思路，因此没有什么特殊的不同。
总结
树的概念还有很多，比如DFS（深度优先搜索），森林与树，哈夫曼树等等，这里小编讲一些树的基础，帮助大家入门了解。我们下一期，再见！
#推荐阅读： 专辑|Linux文章汇总 专辑|程序人生 专辑|C语言
嵌入式Linux 微信扫描二维码，关注我的公众号
