【数据结构】二叉树的概念及结构

提示：学习此篇博客之前，可以先学习【数据结构】树的概念及结构。

---

前言

普通二叉树，很难构成现实的应用场景，但是它是非常重要的非线性数据结构，是学习其它，如平衡二叉树，AVL树，红黑树，B+树，Tire树（字典树）的重要基础。

1.平衡二叉树：平衡二叉树的实际应用较多，常见于快速匹配，搜索等方面。
2.AVL树：最早的平衡二叉树之一。应用相对其它数据结构较少。Windows对进程地址空间的管理用到了AVL树。
3.红黑树：平衡二叉树，广泛用在C++的STL（标准模板库）中。如map和set都是用红黑树实现的，还有Linux的文件管理。
4.B/B++树：用在磁盘文件组织，数据索引和数据库索引。
5.Tire（字典树）：用在统计和排序大量字符串，如自动机，M数据库索引。

1.二叉树的概念

1.二叉树是特殊的树，它不存在度大于2的结点，也就是说父结点至多只能有2个孩结点。
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
3.一棵二叉树是结点的一个有限集合，该集合：或者为空，或者有一个根结点加上两棵别称为左子树和右子树的二叉树组成。

2.特殊的二叉树

1.满二叉树：一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1,则它就是满二叉树。

2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

3.二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1） 个结点;
2. 若规定根节点的层数为1，则深度为K的二叉树的最大结点数是 2^K-1;
3.若规定根节点的层数为1，具有N个结点的满二叉树的深度K=log(N+1) . (ps： 是log以2为底，n+1为对数),若第K层只有一个结点，则深度K=logN +1
4. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0＝ n2＋1

4.二叉树的存储结构

二叉树一般可以使用两种存储结构，一种是顺序结构，一种是链式结构。
1.顺序结构
顺序结构存储使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费（如下），现实中只有堆才会使用数组来存储，关于数据结构——堆，我们在下一个话题的博客会进行讲解。注意：二叉树顺序存储结构在物理上是一个数组，在逻辑上是一棵二叉树。

2.链式结构
二叉树的链式存储结构是指用链表表示一棵二叉树，通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别指向该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。当前我们的学习中一般都输二叉链表，之后学习到高阶数据结构如红黑树等会用到三叉链表。

typedef int BTDataType;

// 二叉链

struct BinaryTreeNode

{

   struct BinTreeNode* _pLeft; // 指向当前节点左孩子

   struct BinTreeNode* _pRight ; // 指向当前节点右孩子

   BTDataType _data ; // 当前节点值域

}

// 三叉链

struct BinaryTreeNode

{ 
   struct BinTreeNode* _pParent ; // 指向当前节点的双亲

   struct BinTreeNode* _pLeft; // 指向当前节点左孩子

   struct BinTreeNode* _pRight ; // 指向当前节点右孩子

   BTDataType _data ; // 当前节点值域

}；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31