二叉树的基本概念、存储结构和（递归）遍历方式

二叉树
度为二的数
二叉树的子树有左右之分
特殊二叉树
1.斜二叉树（类似链表）
2.完美二叉树（满二叉树）（每个结点都有里两个儿子，除了最底下的结点的叶节点没有儿子
3.完全二叉树：从上往下，从左往右编号，与满二叉树必须完全一致只能少最后面的几个结点，不能有空缺

二叉树的几个重要性质
1.一个二叉树第i层的最大结点数为2^(i-1)
2.深度为K的二叉树有最大结点总数为2^k - 1
3.对任何非空二叉树,若n0表示叶节点的个数，n1表示度为1的结点个数n2表示度为2的结点个数，那么存在这样的关系：n0 = n2 + 1;
总的节点数 n0 + n1 + n2
边的数量 n0 + n1 + n2 - 1 = 0*n0 + 1*n1 + n2 * 2 ----> n0 = n2 + 1

二叉树的抽象数据类型定义
数据对象集：一个有穷的结点集合
若不为空，则由根节点和其左、右二叉子树组成
操作集：
1.判断二叉树是否为空：Boolean IsEmpty(BinTree 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个结点的完全二叉树的结点父子关系
1.非根节点（序号i > 1)的父节点的序号是int（i / 2）
2.结点（序号为i)的左孩子及诶那的序号是2i(2i <= n,否则没有左孩子)
3.结点（序号为i)的右孩子结点的序号是2i+1（2i+1 <= n,否则没有右孩子)

结点 A B O C S M Q W K
序号 1 2 3 4 5 6 7 8 9

一般二叉树也可以采用这种结构，但会造成空间浪费
结点 A B O ∧ ∧ M ∧ ∧ ∧ ∧ ∧ ∧ C
序号 1 2 3 4 5 6 7 8 9 10 11 12 13

2.链表存储

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

二叉树的遍历
1.先序遍历：
遍历顺序：A B D F E C G H I
1.访问根节点
2.先序遍历其左子树
3.先序遍历其右子树

1 void PreOrderTraversal(BinTree BT)
2 {
3     if(BT)
4     {
5         printf("%d", BT->data);
6         PreOrderTraversal(BT->Left);
7         PreOrderTraversal(BT->Right);
8     }
9 }

2.中序遍历
遍历过程：D B E F A G H C I
（1）中序遍历其左子树
（2）访问根节点
（3）中序遍历其右子树

1 void PreOrderTraversal(BinTree BT)
2 {
3 　　if(BT)
4　　 {
5 　　　　PreOrderTraversal(BT->Left);
6 　　　　printf("%d", BT->data);
7　　　　 PreOrderTraversal(BT->Right);
8 　　}
9 }

3.后序遍历
遍历过程: D E F B H G I C A
（1）后序遍历其左子树
（2）后序遍历其右子树
（3）访问根节点

1 void PreOrderTraversal(BinTree BT)
2 {
3 　　if(BT)
4 　　{
5 　　　　PreOrderTraversal(BT->Left);
6 　　　　PreOrderTraversal(BT->Right);
7 　　　　printf("%d", BT->data);
8 　　}
9 }

先序、中序和后序遍历过程：遍历过程中经过结点的路线都是一样，只是访问各节点的时机不同
图中在从入口到出口的曲线上用三种符号分别标
记出了先序、中序和后序刻访问各结点的时刻