共计 4042 个字符，预计需要花费 11 分钟才能阅读完成。
@[TOC]
树的基本概念
图 1
树的结点
结点 ：应用树结构存储的每一个数据元素都被称为“结点”。例如，上图 1 中，数据元素 1 就是一个结点；
父结点（双亲结点）、子结点和兄弟结点 ：对于上图 1 中的结点 1,2,3,4 来说，1 是 2,3,4 结点的父结点（也称为“双亲结点”），而 2,3,4 都是 1 结点的子结点（也称“孩子结点”）。对于 2,3,4 来说，它们都有雷同的父结点，所以它们互为兄弟结点。
树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。上图 1 中，结点 1 就是整棵树的根结点。
叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如上图 1 中，结点 11,12,6,7,13,9,10 都是这棵树的叶子结点。
子树和空树
子树 ：上图 1 中，整棵树的根结点为结点 1，而如果单看结点 2,5,6,11,12 组成的局部来说，也是棵树，而且节点 2 为这棵树的根结点。所以称 2,5,6,11,12 这几个结点组成的树为整棵树的子树；同样，结点 5,11,12 形成的也是一棵子树，根结点为 5。
留神 ：单个结点也是一棵树，只不过根结点就是它自身。上图 1 中，结点 11,12,6 等都是树，且都是整棵树的子树。
晓得了子树的概念后，树也能够这样定义：树是由 根结点和若干棵子树 形成的。
空树 ：如果汇合自身为空，那么形成的树就被称为空树。空树中没有结点。
补充：在树结构中，对于具备同一个根结点的各个子树，相互之间不能有交加。例如，上图 1 中，除了根结点 1，其余元素又各自形成了三个子树，根结点别离为 2,3,4，这三个子树相互之间没有雷同的结点。如果有，就毁坏了树的构造，不能算做是一棵树。
结点的度和档次
对于一个结点，领有的子树数（结点有多少分支）称为结点的 度（Degree）。例如，上图 1 中，根结点 1 下分出了 3 个子树，所以，结点 1 的度为 3。
一棵树的度是树内各结点的度的最大值。上图 1 示意的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。
结点的档次 ：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，顺次类推。对于上图 1 来说，1 结点在第一层，2,3,4 为第二层，5,6,7,8,9,10 在第三层，11,12,13 在第四层。
一棵树的 深度（高度） 是树中结点所在的最大的档次。上图 1 树的深度为 4。
如果两个结点的父结点虽不雷同，然而它们的父结点处在同一档次上，那么这两个结点互为堂兄弟。例如，上图 1 中，结点 5,6,7,8,9,10 的父结点都在第二层，所以之间为堂兄弟的关系。
有序树和无序树
如果树中结点的子树从左到右看，谁在右边，谁在左边，是有规定的，这棵树称为 有序树 ；反之称为 无序树 。
在有序树中，一个结点最右边的子树称为 ” 第一个孩子 ”，最左边的称为 ” 最初一个孩子 ”。
拿上图 1 来说，如果是其自身是一棵有序树，则以结点 2 为根结点的子树为整棵树的第一个孩子，以结点 4 为根结点的子树为整棵树的最初一个孩子。
森林
由 m（m >= 0）个互不相交的树组成的汇合被称为森林。上图 1 中，别离以 2,3,4 为根结点的三棵子树就能够称为森林。
后面讲到，树能够了解为是由根结点和若干子树形成的，而这若干子树自身是一个森林，所以，树还能够了解为是由根结点和森林组成的。用一个式子示意为：Tree =（root,F）
其中，root 示意树的根结点，F 示意由 m（m >= 0）棵树组成的森林。
二叉树的性质
通过前人的总结，二叉树具备以下几个性质：
- 二叉树中，第 i 层最多有 2i-1 个结点。
- 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
- 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
- 二叉树还能够持续分类，衍生出满二叉树和齐全二叉树。
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为 满二叉树。
图 2
如图 2 所示就是一棵满二叉树。
- 满二叉树除了满足一般二叉树的性质，还具备以下性质：
- 满二叉树中第 i 层的节点数为 2n-1 个。
- 深度为 k 的满二叉树必有 2k-1 个节点，叶子数为 2k-1。
- 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度雷同的子树，且叶子节点都在最底层。
- 具备 n 个节点的满二叉树的深度为 log2(n+1)。
齐全二叉树
如果二叉树中除去最初一层节点为满二叉树，且最初一层的结点顺次从左到右散布，则此二叉树被称为齐全二叉树。
图 3
如上图 3a 所示是一棵齐全二叉树，如上图 3b 中因为最初一层的节点没有依照从左向右散布，因而只能算作是一般的二叉树。
齐全二叉树除了具备一般二叉树的性质，它本身也具备一些独特的性质，比如说，n 个结点的齐全二叉树的深度为 ⌊log2n⌋+1。
[log2n]示意取小于 log2n 的最大整数。例如，[log24] = 2，而 [log25⌋]后果也是 2。
对于任意一个齐全二叉树来说，如果将含有的结点依照档次从左到右顺次标号（图 3），对于任意一个结点 i，齐全二叉树还有以下几个论断成立：
- 当 i>1 时，父亲结点为结点 [i/2]。（i=1 时，示意的是根结点，无父亲结点）
- 如果 2 i>n（总结点的个数），则结点 i 必定没有左孩子（为叶子结点）；否则其左孩子是结点 2i。
- 如果 2 i+1>n，则结点 i 必定没有右孩子；否则右孩子是结点 2i+1。
二叉树的顺序存储
二叉树的顺序存储，指的是应用程序表（数组）存储二叉树。须要留神的是，顺序存储只实用于齐全二叉树。换句话说，只有齐全二叉树才能够应用程序表存储。因而，如果咱们想顺序存储一般二叉树，须要提前将一般二叉树转化为齐全二叉树。
有读者会说，满二叉树也能够应用顺序存储。要晓得，满二叉树也是齐全二叉树，因为它满足齐全二叉树的所有特色。
一般二叉树转齐全二叉树的办法很简略，只需给二叉树额定增加一些节点，将其 ” 拼凑 ” 成齐全二叉树即可。如图 4 所示：
图 4
下图中，左侧是一般二叉树，右侧是转化后的齐全（满）二叉树。
解决了二叉树的转化问题，接下来学习如何顺序存储齐全（满）二叉树。
齐全二叉树的顺序存储，仅需从根节点开始，依照档次顺次将树中节点存储到数组即可。
图 5
例如，存储图 5 如下 所示的齐全二叉树，其存储状态如图 6 所示：
图 6
同样，存储由一般二叉树转化来的齐全二叉树也是如此。例如，图 4 中一般二叉树的数组存储状态如图 7 所示：
图 7
由此，咱们就实现了齐全二叉树的顺序存储。
不仅如此，从程序表中还原齐全二叉树也很简略。咱们晓得，齐全二叉树具备这样的性质，将树中节点依照档次并从左到右顺次标号（1,2,3,…），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的齐全二叉树，也就是实现由图 6 到图 5、由图 7 到图 4 的转变。
二叉树的链式存储
二叉树并不适宜用数组存储，因为并不是每个二叉树都是齐全二叉树，一般二叉树应用程序表存储或多或多会存在空间节约的景象。
接下来咱们介绍二叉树的链式存储构造。
图 8
如图 8 所示，此为一棵一般的二叉树，若将其采纳链式存储，则只需从树的根节点开始，将各个节点及其左右孩子应用链表存储即可。因而，图 8 对应的链式存储构造如图 9 所示：
图 9
由图 9 可知，采纳链式存储二叉树时，其节点构造由 3 局部形成（如图 10 所示）：
- 指向左孩子节点的指针（Lchild）；
- 节点存储的数据（data）；
- 指向右孩子节点的指针（Rchild）；
图 10
链式存储代码实现：
/*
* @Description: 二叉树的链式存储
* @Version: V1.0
* @Autor: Carlos
* @Date: 2020-05-29 16:37:38
* @LastEditors: Carlos
* @LastEditTime: 2020-05-29 16:45:13
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct BitNode
{
int data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
void CreateBiTree(BitTree *T){*T=(BitNode*)malloc(sizeof(BitNode));
// 根节点
(*T)->data=1;
(*T)->lchild=(BitNode*)malloc(sizeof(BitNode));
// 1 节点的左孩子 2
(*T)->lchild->data=2;
(*T)->rchild=(BitNode*)malloc(sizeof(BitNode));
// 1 节点的右孩子 3
(*T)->rchild->data=3;
(*T)->rchild->lchild=NULL;
(*T)->rchild->rchild=NULL;
(*T)->lchild->lchild=(BitNode*)malloc(sizeof(BitNode));
// 2 节点的左孩子
(*T)->lchild->lchild->data=4;
(*T)->lchild->rchild=NULL;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
int main() {
BitTree Tree;
CreateBiTree(&Tree);
printf("%d",Tree->lchild->lchild->data);
return 0;
} 文中代码均已测试，有任何意见或者倡议均可分割我。欢送学习交换！
如果感觉写的不错，请点个赞再走，谢谢！
如遇到排版错乱的问题，能够通过以下链接拜访我的 CSDN。
**CSDN:[CSDN 搜寻“嵌入式与 Linux 那些事”]
