二叉树基础知识整理

树的定义

树是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

存储在数组中，数组下标从零开始

如果是一般的二叉树的话，如果我在对他进行从上至下，从左至右进行编号时就不能很好的反映数组元素之间的关系了，如果我们进行适当的改造，通过添加一些结点，把他补成一颗完全二叉树，那么再进行编号，就可以进行顺序存储了

img

此可以看出，这样的存储方式，会造成很多空间的浪费，而且如果要进行对树上元素进行删除、插入操作需要移动大量的数据元素，因此二叉树不宜采用顺序存储结构

二叉树的链式存储结构

用类似于链表的存储方法来存储树上元素的逻辑关系，即用指针来表示元素之间的逻辑关系

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