数据结构(三)二叉树及存储结构

定义

  二叉树$T$T：一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和称为其左子树$T_{L}$TL​和右子树$T_{R}$TR​的两个不相交的二叉树组成。

  有五种基本的形式：

1. 空树。
2. 只有一个节点。
3. 有一个节点，只有左子树，右子树为空。
4. 有一个节点，左子树为空，右子树不为空。
5. 左右子树都不为空。

  具体如下图所示：

  这里需要注意的是：二叉树与度为2的树的区别在于二叉树有左右之分。

特殊二叉树

  有三种特殊的二叉树，斜二叉树、完美二叉树、完全二叉树：

• 斜二叉树(Skewed Binary Tree)

• 完美二叉树(Perfect Binary Tree)

  完美二叉树(Perfect Binary Tree)也称作满二叉树(Full Binary Tree）

• 完全二叉树(Complete Binary Tree)

  有$n$n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为$i（1 ≤ i ≤ n）$i（1≤i≤n）结点与满二叉树中编号为 $i$i 结点在二叉树中位置相同。

二叉树的重要性质

1. 一个二叉树第 $i$i 层的最大结点数为：$2^{i-1}$2i−1，$i \geq 1$i≥1。
2. 深度为 $k$k 的二叉树有最大结点总数为：$2^{k}-1$2k−1，$k \geq 1$k≥1。

  对任何非空二叉树 $T$T，若$n_{0}$n0​表示叶节点的个数、$n_{2}$n2​是度为2的非叶节点个数，那么两者满足关系$n_{0}=n_{2}+1$n0​=n2​+1。

  如上图所示，$n_{0}=4$n0​=4，$n_{1}=2$n1​=2，$n_{2}=3$n2​=3，满足$n_{0}=n_{2}+1$n0​=n2​+1。

抽象数据类型

  类型名称：二叉树

  数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。

  操作集：

  BT $\in$∈ BinTree, Item $\in$∈ ElementType，重要操作有：

1. Boolean IsEmpty( BinTree BT)：判别BT是否为空;
2. void Traversal( BinTree BT)：遍历，按某顺序访问每个结点;
3. BinTree CreatBinTree()：创建-一个二叉树。

  常用的遍历方法有:

• void PreOrderTraversal( BinTree BT)：先序—根、左子树、右子树；
• void InOrderTraversal( BinTree BT )：中序–左子树、根、右子树；
• void PostOrderTraversal( BinTree BT)：后序—左子树、 右子树、根；
• void LevelOrderTraversal( BinTree BT)：层次遍历，从上到下、从左到右；

二叉树的存储结构

1. 顺序存储结构

  对于完全二叉树，一般按照按从上至下、从左到右顺序存储 $n$n 个结点的完全二叉树的结点父子关系；

  可以采用数组的形式对其进行存储：

• 对于非根结点(序号 $i > 1$i>1)的父结点的序号是 $i/2$i/2；
• 结点(序号为 $i$i )的左孩子结点的序号是 $2i$2i， (若$2i \leq n$2i≤n，否则没有左孩子)；
• 结点(序号为 $i$i )的右孩子结点的序号是 $2i+1$2i+1， （若$2 i +1 \leq n$2i+1≤n，否则没有右孩子）;

  对于一般的二叉树也可以采用这种结构，但是会造成空间浪费，如下图所示的补全方法：

2. 链表存储

  用链表存储的话可采用如下结构体：

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
}