树的定义
树是n（n>=0）个元素的的有限集合。在任何一颗非空树中：
- 有且仅有一个节点被称为根节点，在整棵树最上面
- 当 n>1时，除根节点以外的其他节点可被分为 m(m>0)个互不相交的有限集合T1...Tn，其中每个集合本身又是一颗树，并且称为根的子数。
树的相关术语
img
- 节点：树中的数据元素称为节点，每个节点都保存了该节点的信息，即数据元素和数据项与数据元素之间的关系
- 节点的度：节点拥有子树的个数
二叉树
树型结构中有一种特殊的树叫做二叉树，二叉树的结构也比较简单，规律性较强，并且可以证明，即使一般的树也能转化成二叉树。而且许多实际问题抽象出来的数据结构往往就是二叉树的形式。
二叉树的定义
二叉树是个有限元素的集合，该集合为空或者由一个根和两个互不相交的左子树和右子树组成。在二叉树中，一个元素也称为一个节点。
二叉树基本特征
- 每个节点最多只有两棵子树，即不存在度大于 2 的节点
- 左子树和右子树次序不能颠倒，即二叉树是有序树，而且哪怕只有
一颗子树，也要区分是左子树还是右子树。
二叉树的 5 种基本形态
- 空集
- 根有两颗子树
- 根只有一颗子树（左子树或右子树）
- 根没有子树
二叉树的性质
- 在二叉树的第 i 层上至多有 **2^(i-1) **个结点 (i>0)
-
一棵深度为 k 的二叉树中，最多有 2^k-1 个结点
-
具有 n 个结点的完全二叉树的深度 k 为 [log2n]+1
-
对于一棵非空的二叉树，如果叶子结点数为 n0，度为 2 的结点数为 n2，
则 n0 = n2+1 -
对于具有n个节点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树中所有结点进行从1的编号，则对于任意的序号为i结点，有:
如果 i>1，则序号为 i 的结点的双亲结点为 i/2，如果 i==1，则序号为 i 的结点是根节点，无双亲结点
如果 2i<=n，则序号为i的结点的左孩子节点的序号为 2i，否则i结点无左孩子
如果 2i+1<=n，则序号为i的结点的右孩子节点的序号为 2i，否则i结点无右孩子注意：性质 1,2,4 所有二叉树都通用，性质 3,5 只有完全二叉树适用
二叉树的存储结构
- 顺序存储结构
- 链式存储结构
顺序存储结构
一组连续的存储单元依次从上至下，从左至右存储二叉树上的节点元素。对于完全二叉树来说，树中结点的序号都是按照从上至下，从左至右进行编排的，所以结点的序号可以唯一的反映节点之间的逻辑关系（性质5）
img
存储在数组中，数组下标从零开始
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 数据 | A | B | C | D | E | F | G | H | I |
如果是一般的二叉树的话，如果我在对他进行从上至下，从左至右进行编号时就不能很好的反映数组元素之间的关系了，如果我们进行适当的改造，通过添加一些结点，把他补成一颗完全二叉树，那么再进行编号，就可以进行顺序存储了
img
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 数据 | A | B | C | D | E | 0 | 0 | 0 | 0 | 0 | F |
此可以看出，这样的存储方式，会造成很多空间的浪费，而且如果要进行对树上元素进行删除、插入操作需要移动大量的数据元素，因此二叉树不宜采用顺序存储结构
二叉树的链式存储结构
用类似于链表的存储方法来存储树上元素的逻辑关系，即用指针来表示元素之间的逻辑关系
img
data 是数据域，leftChild 和 rightChild 是指针域，leftChild 是指向左儿子的指针，rightChild 是指向右儿子的指针，当左儿子或右儿子为空时，相应的指针域也为空
代码描述
//存储的数据类型
typedef char DataType
typedef struct node
{
DataType data; //数据域
struct node* leftChild; //左儿子
struct node* rightChild; //右儿子
}BinNode;
typedef BinNode* BinTree;
这是二叉链表的定义，除此之外还有三叉链表，三叉链表比起二叉链表多了一个指向双亲结点的指针域，如图所示
img
代码描述
//存储的数据类型
typedef char DataType
typedef struct node
{
DataType data; //数据域
struct node* leftChild; //左儿子
struct node* rightChild; //右儿子
struct node* parent; //双亲
}BinNode;
typedef BinNode* BinTree;
在二叉树中有两种特殊的二叉树 >>> 满二叉树和完全二叉树
满二叉树
在一棵树中所有的分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，这样的二叉树称为满二叉树。
img
完全二叉树
一棵深度为 k 且具有 n 个节点的二叉树，对树中节点按从上至下，从左至右的顺序进行编号，当且仅当节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应
时，才称这棵二叉树为完全二叉树。显然满二叉树也是完全二叉树的一种。
完全二叉树的特点：
- 叶子节点只可能在层次最大的两层上出现
- 对任一节点，其右分支下的儿子的最大层次为 h，则其左分支下的儿子最大层次为 h 或 h+1
网友评论