二叉树基础知识概览

---

1，树的基本概念

在讲二叉数前，我认为需要先了解树，这个概念。二叉树是一种特殊的树。我们在生活中可以看到各种样式的树。现实中的树是根朝下叶子在上，但是数据结构的树是根在上叶子在下的结构。

1.1树的定义

树（tree） 是n（n>=0）个结点的有限集。n=0时称为空树。在任何一棵非空树中：1. 有且只有一个特定的称为 根（root） 的结点；2. 当n>1时，其余结点可分为m（m>0）个 互不相交 的有限集，其中每一个集合又是一棵树，并且成为 根的子树（subtree）。
需要注意：n>0时，根节点是唯一的，不可能存在多个根节点。树和子树都应遵循。
比如：

A结点的根结点只能是B或者C中的一个，必须是有唯一的根结点，像这样的子树是错误的。

1.2树的关键字

（1）结点的度：结点所拥有的子树的个数称为度
（2）结点的分类：度为0的结点称为叶子结点，也可以叫终端结点。度不为0
的结点称为分支结点或非终端结点。根据度还可以分为内部结点和叶节点，内部结点就是度不为0的结点。
（3）树的度：树的度就是结点度的最大值。

（4）结点间的关系：双亲和孩子，双亲结点是孩子结点的上面连着的唯一结点，比如Q是B的双亲结点，B是Q的孩子结点。兄弟，兄弟结点指共有一个根节点，比如B和C以及W，O和A，他们之间的关系就是兄弟结点。祖先和子孙，为了不出现这中曾曾曾曾曾祖父，曾曾曾曾曾孙子的称谓。我们将从根结点到该点的所经分支的所有结点称为其祖先，孙子结点就是反着来。比如：Q，B是w的祖先。

1.3树的结构

树的深度是树中 结点 的最大层次。

树的结构：

1. 根节点：无双亲。唯一
2. 中间结点：一个双亲，多个孩子
3. 叶子结点：无孩子，可以多个

1.4树的存储结构

树的存储有很多方法，比如有双亲表示法，孩子表示法，孩子兄弟表示法等。目前用的比较多的是孩子兄弟表示法。
（1）双亲表示法
简单的来说就是，记录结点的数据同时记上结点的双亲的位置。如果是用数组来建立树，那存的是双亲的下标；如果使用链表建立树，那么存的双亲的指针（地址）。

struct node
{
  int date;//存数据，默认int了
  int parent;//双亲的下标位置或者是node* parent 
}
1
2
3
4
5

（2）孩子表示法
对照双亲表示法，我们不难想到，应该是包括数据还有记录孩子的位置。那么就有个问题，孩子有多少个这是不确定的，我们在创结构体时，应该留多大的空间去储存孩子的位置呢？
最简单的方法就是，以树的度为标准，来确定储存孩子位置的空间大小。那么大概率会造成不小的空间浪费。
就比如要存储下面这棵树。

简单的分析可得，其度为3，所以需要3个指针域来存储位置。

如果度小于3，那么空的位置存空指针。
于是有：

(3)孩子兄弟表示法
这种方法又被称为左孩子右兄弟法，就是用俩个指针，第一个指针指向第一个孩子结点，第二个指针指向紧挨着得兄弟结点，如果不存在则指向空。如果好几个孩子怎么办？其实大家好好想想，不管是几个孩子，我直管第一个孩子，那么第二孩子谁管，交给了第一个孩子管，用它得第二个指针会指向它的兄弟结点。所以就全管理起来了。

typedef struct node
{
 int date;
 struct node *firstchild,*rightsib;
}node;
1
2
3
4
5

左孩子右兄弟法是被常用的。

---

2，特殊的树–二叉树

对树有基本的了解后，我们就开始学习二叉树，二叉树的应用非常广泛，像学习后面的搜索二叉树，红黑树等，这是在打基础。

2.1 二叉树的定义

二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和两颗互补相交的，分别称为根节点的左子树或右子树的二叉树组成。
所以总结一下就是：

1. 二叉树的度不得超过2
2. 二叉树是有序树，由左子树和右子树组成，次序不能颠倒
3. 二叉树的度可以有0，1，2，注意度为1有两种情况
   

2.2 特殊的二叉树

（1）斜树
所有的结点都只有左子树的叫左斜树，所有的结点都只有右子树的二叉树叫右斜树。
它的特点就是：树的深度和结点的个数相等。

（2）满二叉树
在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树叫做满二叉树。
这样的二叉树，是个对称图形。

特点：叶子结点只在最后一层，
同层度中，满二叉树的结点最多

（3）完全二叉树
一棵深度为k的有n个结点的 二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
完全和满是不同的，完全二叉树必须是层序遍历时，完全是连续的。完全二叉树是由满二叉树引出来的，也就是说满二叉树是完全二叉树，但是完全二叉树不一定是满二叉树。
比如：


总结一下：

• 完全二叉树的前n-1层是满的
• 最后一层必须从左至右连续

2.3 二叉树的性质

性质1: 在二叉树的第i层至多有2^i-1个结点(i>=1)。
性质2: 深度为k的二叉树至多有2^k-1个结点（k>=1)。
性质3: 对任何一颗二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
性质4: 具有n个结点的完全二叉树的深度为log₂n +1。
对于二叉树的性质，大家有个了解即可，性质3比较常考，完全二叉树结点的度为0 1 2并且度为1的，至多有一个,然后度为0的比度为2的结点多一个。由此可能会出点选择题。

2.4二叉树的储存

二叉树的储存一样可以有顺序储存，用数组储存；也可以用链式储存，称为二叉链表。
（1）顺序储存
顺序储存适用于完全二叉树，非完全二叉树会导致空间浪费。在我们对二叉树的应用中，用顺序存储的一般是堆，堆可以解决很多问题，比如topk问题（选出最大或最小的前几个），排序等。
大家可能会有疑问？数组怎么可以用来储存二叉树呢？怎么才存储的？
其实物理层面我们是用数组来储存二叉树，但是逻辑上我们可以将这一串数字看成二叉树。
比如：

（2）链式储存
链式储存就用的相对广泛许多，有二叉链表和三叉链表。二叉链是容易想到的：一个数据+俩个指针（指向左孩子和右孩子）；三叉链：一个数据+三个指针（左孩子，右孩子，双亲）。

//二叉链表
typedef struct BTnode
{
 int date;
 struct BTnode *lchild,*rchild;
}node;
//三叉链表
typedef struct BTnode
{
 int date;
 struct BTnode *lchild,*rchild，*parent;
}node;
1
2
3
4
5
6
7
8
9
10
11
12

2.5 二叉树的遍历

二叉树的遍历有前序遍历，中序遍历，后序遍历以及层序遍历。这么多的遍历方法，其实是为了在遍历过程中的结点进行各种处理，都有其存在的意义。
（1）前序遍历
如果二叉树为空，就不操作，否则先访问根结点再访问左子树，再访问右子树。所以就是访问根结点的操作在访问左右子树之前。有点抽象不好理解，看图结合代码理解吧。

void preorder(BItree T)
{
//为空就不操作
 if(T==null)
 return;
 //访问根结点
 printf("%d",T->date);
 //前序遍历左树
 preorder(T->lchild);
 //前序遍历右树
 preorder(T->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12

开始结合代码讲解：
先判断A结点是否为空，不为空所以打印A结点数据；

再去遍历A结点的左树的B，判断不为空，所以打印出B的数据；

再去遍历B的左数D，判断不为空，打印D的数据；

再去遍历D的左树，判断为空所以返回，然后遍历D的右树，判断为空所以返回；

相当于B的左树遍历好了，D已经做为B的左数返回了，再去遍历B的右树，判断为空返回；

A的左树B已经遍历完了；再去遍历A的右树C，C不为空，所以打印C的数据;

遍历C的左树，等c的左树遍历好后，遍历C的右树，然后返回;

就相当于A的右树遍历完了，于是这棵树就前序遍历完毕,它的顺序是ABDCEF。其实上面省略一点过程，就是E，F也会去判断其左右子树，为空所以直接返回不操作。
（2）中序遍历
中序遍历就是如果树为空，就不操作，否则从根结点开始，中序遍历根结点的左子数，然后访问根结点，最后中序遍历右子树。也就是说访问根结点在左子树和右子树之间。

void inorder(BItree T)
{
//为空就不操作
 if(T==null)
 return;
 //中序遍历左树
 inorder(T->lchild);
 //访问根结点
 printf("%d",T->date);
 //中序遍历右树
 inorder(T->rchild);
}
1
2
3
4
5
6
7
8
9
10
11
12

还是以上一颗树为例子，其遍历顺序为多少呢？
顺序为：DBAECF
其实按照代码去理解，这块比较考察递归，大家自行画图学习哈。
（3）后序遍历
后序遍历就是，如果树是空就不操作直接返回，否则从根结点开始，先访问左子树再访问右子树，最后访问根结点。也就是说对根结点的访问在遍历其左右子树之后。
代码如下：

void postorder(BItree T)
{
//为空就不操作
 if(T==null)
 return;
 //后序遍历左树
 postorder(T->lchild);
 //后序遍历右树
 postorder(T->rchild);
  //访问根结点
 printf("%d",T->date);
}
1
2
3
4
5
6
7
8
9
10
11
12

上面那颗树，后序遍历的顺序是：DBEFCA。
（4）层序遍历
层序遍历很容易理解，就一层一层的往下遍历。对于上面那颗树，层序遍历就是：ABCDEF。实现层序遍历是用队列实现的。先根结点入队列，然后根结点出队列，再入根结点的左孩子后右孩子。这样一层入队列然后出队列，出队列后带入下一层的结点。

根结点先入队列，

出队列，入其孩子结点，如果孩子结点为空，就不入队列了，

依次过程如下：

---

完结：以上就是本期关于二叉树基本知识的概况，为以后学习avl树等二叉树高阶用法打下基础。希望小伙伴们有所收获。