二叉树

1.二叉树的概念

定义

二叉树的特点是每个结点至多有两颗子树（二叉树不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。 二叉树是有序树，若将其左、右子树颠倒，则成为另一颗不同的二叉树，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

几个特殊的二叉树

1）满二叉树 满二叉树的结点都集中在二叉树的最下层，并且除叶子结点之外的每个结点度数均为2。

2）完全二叉树 高度为h、有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。 其特点如下： ① 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。 ② 若有度为1的结点，则可能只有一个，且该结点只有左孩子而无右孩子。 ③ 按层序编号后，一旦出现某节点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子节点。 ④ 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都没有。

3）二叉排序树 左子树上所有结点的关键字均小于根节点的关键字；右子树上的所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一颗二叉排序树。

4）平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过1。

2.二叉树的存储结构

顺序存储结构

用一组地址连续的存储单元依次自下而上、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i~1的分量中。 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反应结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域：数据域data、左指针域lchild和右指针域rchild。 二叉树的链式存储结构描述如下：

typedef struct BiNode { ElemType data; BiNode* lchild, * rchild; }BiNode, * BiTree;

在含有n个结点的二叉链表中，含有n+1个空链域。

3.二叉树的遍历（递归）

先序遍历

void PreOrder(BiTree T) { if (T != NULL) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }

中序遍历

void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } }

后序遍历

void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }

层序遍历

要进行层次遍历，需要借助一个队列。先将二叉树根节点入队，然后出队，访问出队结点，若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根节点入队。然后出队，访问出队结点…如此反复，直至队列为空。

void LevelOrder(BiTree T) { SqQueue Q; BiTree p; EnQueue(Q, T->data);//入队 while (!IsEmpty(Q)) { DeQueue(Q, p);//出队 visit(p); if (p->lchild != NULL) { EnQueue(Q, p->lchild); } if (p->rchild != NULL) { EnQueue(Q, p->rchild); } } }

4.二叉树的遍历（非递归）

先序遍历

void PreOrder2(BiTree T) { SqStack S; BiTree p = T; InitStack(S); while (p || isEmpty(S)) { if (p) { visit(p); Push(S, p);//入栈 p = p->lchild; } else { Pop(S, p);//出栈 p = p->rchild; } } }

中序遍历

void InOrder2(BiTree T) { SqStack S; InitStack(S); BiTree p = T; while (p || isEmpty(S)) { if (p) { Push(S, p);//入栈 p = p->lchild; } else { Pop(S, p);//出栈 visit(p); p = p->rchild; } } }