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

二叉树

度为二的数

二叉树的子树有左右之分

特殊二叉树

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 }

先序、中序和后序遍历过程：遍历过程中经过结点的路线都是一样，只是访问各节点的时机不同

图中在从入口到出口的曲线上用 三种符号分别标

记出了 先序、中序和后序刻 访问各结点的时刻