02 二叉树及存储结构

02-二叉树及存储结构

定义与性质

定义

二叉树（Binary Tree）：一个有穷的结点集合

• 集合可以为空
• 不为空时，是由根节点和称为左子树 \(T_L\) 和右子树 \(T_R\) 的两个不相交二叉树组成

• 五种基本形态

  

• 二叉树子树有左右顺序之分

特殊二叉树

• 斜二叉树（Skewed Binary Tree）

  • 每个结点都只有左子节点或者右子结点。例如只有左子结点的：

    

• 完美二叉树（Perfect Binary Tree）/满二叉树（Full Binary Tree）

  • 所有层的结点都被填满

    

• 完全二叉树（Complete Binary Tree）

  • 仅允许最底层结点不完全填满，且最底层的结点必须从左至右依次连续填充
  • 或者说从上到下从左到右依次编号，编号为 \(i\) 的结点与满二叉树中编号为 \(i\) 的结点在二叉树中位置相同

  • 

重要性质

• 一个二叉树第 \(i\) 层的最大结点数：\(2^{i-1},i\geqslant 1\)
• 深度为 \(k\) 的二叉树的最大结点总数为：\(2^k-1,k\geqslant 1\)
• 对任何非空二叉树 \(T\)，若 \(n_0\) 表示叶结点的个数，\(n_2\) 是度为 \(2\) 的非叶节点个数，那么两者满足关系 \(n_0=n_2+1\)

  • 证明：用两种思路表示树中边的数量

    \[ \begin{array}{rl} n_0+n_1+n_2-1 &= 0\times n_0+1\times n_1+2\times n_2 \\ n_0 &= n_2+1 \end{array} \]

ADT 定义

类型名称：二叉树

数据对象集：一个有穷的结点集合。

• 若不为空，则由根结点和其左、右二叉子树组成。

操作集：\(\text{BT} \in \text{BinTree}\), \(\text{Item} \in \text{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)：层次遍历/层序遍历，从上到下、从左到右。

存储结构

顺序存储

使用数组存储：可适合表示完全二叉树。

因为完全二叉树的特性，可以保证一个数组表示唯一的一个完全二叉树。数组按照从上到下、从左到右的顺序存储一个完全二叉树。

• 非根节点（序号 \(i>1\)）的父节点的序号是 \(\lfloor \dfrac{i}{2}\rfloor\)
• 序号为 \(i\) 的结点的左孩子结点的序号是 \(2i\)（前提是 \(2i\leqslant n\)，否则没有左孩子）
• 序号为 \(i\) 的结点的右孩子结点的序号是 \(2i+1\)（前提是 \(2i+1\leqslant n\)，否则没有左孩子）

也可以表示一般二叉树，只不过会造成空间浪费。方法是空位也留出来，用None或者null等表示

链表存储

using ElementType = char;
using BiTree = struct TreeNode*;

struct TreeNode {
    ElementType data;
    BiTree left;
    BiTree right;
};