二叉树的实现
BinNode ： 二叉树结点
BinNode
二叉树结点结构代码 ：
#define BinNodePosi BinNode *
struct BinNode
{
BinNodePosi parent, lchild, rchild;
T Data; //数据项，数据类型为T
int height; //该结点的高
int size(); //子树的规模，包括该节点
int color; // 节点的颜色，RB-Tree使用
BinNodePosi insertAsLC(T const &); //作为左孩子插入新结点
BinNodePosi insertAsRC(T const &); //作为右孩子插入新结点
BinNodePosi succ(); //中序遍历下，当前结点的直接后继
void travLevel(); //该结点（包括该结点）所在的子树层次遍历
void travPre(); //该结点（包括该结点）所在的子树先序遍历
void travIn(); //该结点（包括该结点）所在的子树中序遍历
void travPost(); //该结点（包括该结点）所在的子树后续遍历
}；
二叉树常用接口实现
-
将新结点作为左/右孩子插入
BinNodePosi insertAsLC(T const &); //作为左孩子插入新结点BinNodePosi insertAsRC(T const &); //作为右孩子插入新结点
/* 创建一个新结点，该结点之后作为左孩子结点 */
BinNodePosi insertAsLC(T const &e)
{
BinNodePosi lChild = new BinNode(e, this); //this指针：父结点为当前结点;条件 ： this.LC == NULL
return lChild;
}
/* 创建一个新结点，该结点之后作为右孩子结点 */
BinNodePosi insertAsRC(T const &e)
{
BinNodePosi rChild = new BinNode(e, this); //this指针：父结点为当前结点;条件 ： this.RC == NULL
return rChild;
}
- 规模 size : 返回包括当前结点在内的所有后代的总数
int size()
{
int s = 1; //计入自身
if (lchild)
{
s + = lchild->size(); //递归计入左子树的规模
}
if (rchild)
{
s + = rchild->size(); //递归计入右子树的规模
}
return s;
}
-
高度更新
某结点插入或删除后代结点，可能其高度以及其祖先结点的高度都会更新；(从插入或删除的结点的父结点[第一个高度可能更新的结点]开始更新)
[注] 结点高度 ： 约定空(子)树高度为 0；单结点(子)树高度为 0
#define NodeHeight(p) ((p) ? p->height : 0) //节点高度，约定空树的节点高度为 0
/* 更新当前结点 x 的高度 */
int updateHeight(BinNodePosi x)
{
return x->height = 1 + max(NodeHeight(x->lchild), NodeHeight(x->rchild));
}
/* 更新 x 的高度及其历代祖先的高度 */
void updateHeightAbove(PinNodePosi x)
{
while (x)
{
updateHeight(x);
x = x->parent;
}
return;
}
- 结点插入
/* 新节点作为 x 节点的左孩子插入 */
BinNodePosi insertAsLC(BinNodePosi x, T const &e)
{
_size ++; //整体规模 ＋1
x->insertAsLC(e); // BinNode 结构体中的接口
updateHeightAbove(x); // x的历代祖先(包括x)的高度 *可能*增加，其余节点*必然不变*
return x->lchild;
}
/* 新节点作为 x 节点的右孩子插入 */
BinNodePosi insertAsRC(BinNodePosi x, T const &e)
{
_size ++; //整体规模 ＋1
x->insertAsRC(e); // BinNode 结构体中的接口
updateHeightAbove(x); // x的历代祖先(包括x)的高度 *可能*增加，其余节点*必然不变*
return x->rchild;
}
二叉树遍历算法实现
1. 先序遍历（Pre_order）
二叉树先序 ：
- 先根节点
- 先序遍历根节点的左子树
- 先序遍历根节点的右子树
遍历顺序 ： 节点 --- 左孩子 --- 右孩子
-
1.1 递归实现二叉树先序遍历算法
补上递归实现的图解
/* 递归实现*/
void traversePre(BinNodePosi x)
{
if (NULL == x) //递归出口
{
return;
}
Visit(x); // Visit()为访问节点数据函数
traversePre(x->lchild); //先序遍历左子树
traversePre(x->rchild); //先序遍历右子树
}
-
1.2 非递归实现二叉树先序遍历算法 --- "实现1"
补上非递归实现方式1的图解
/* 非递归实现 code 1 */
-
1.3 非递归实现二叉树先序遍历算法 --- "实现2"
补上非递归实现方式2的图解
/* 非递归实现 code 2 */
2. 中序遍历（In_order）
二叉树中序 ：
- 中序遍历根节点的左子树
- 访问根节点
- 中序遍历根节点的右子树
遍历顺序 ： 左孩子 --- 节点 --- 右孩子
-
2.1 递归实现二叉树中序遍历算法
补上递归实现方式的图解
/* 递归实现 code */
-
2.2 非递归实现二叉树中序遍历算法
补上非递归实现方式的图解
/* 非递归实现 code 1 */
3. 后序遍历（Post_order）
二叉树后序 ：
- 后序遍历根节点的左子树
- 后序遍历根节点的右子树
- 访问根节点
遍历顺序 ： 左孩子 --- 右孩子 --- 节点
-
3.1 递归实现二叉树后序遍历算法
补上递归实现方式的图解
/* 递归实现 code */
-
3.2 非递归实现二叉树后序遍历算法
补上非递归实现方式的图解
/* 非递归实现 code */
4. 层次遍历 （广度遍历）
5. 补充
对于二叉树，树的遍历通常就以上四种：先序遍历、中序遍历、后序遍历、广度优先遍历。（前三种亦统称深度优先遍历）
对于多叉树，树的遍历通常有两种：深度优先遍历、广度优先遍历。
这里补上之后整理的多叉树的深度和广度遍历链接
二叉树的重构
已知某二叉树的遍历序列，如何重构？条件是什么？
- 任一二叉树 ： 三种遍历序列(Pre, In, Post)
- 已知 [ 先序 / 后序 ] ＋ 中序，即可重构一棵二叉树
[分析]
只靠 先序 ＋ 后序，当出现子树为空的情况，无法判断子树是 L or R，造成分歧。
但是在一种情况下， 先序 + 后序 可构造出唯一对应的二叉树。
- 即 [ 先序 ＋ 后序 ＋ 真二叉树 ]
真二叉树 ： 分叉数为偶数个（0，2）
补充：二叉树的几种分类
真二叉树：所有节点的度不为1，即叶子节点的度为0，其他节点的度为2
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树
满二叉树：完全二叉树的一种特殊情况，所有叶节点同处于最底层，每一层的节点数都达到饱和，称为满二叉树
二叉树的应用
1. 二叉树的深度 ： "输入根节点，求该树的深度"
2. 输入二叉树的根节点，判断其是否是平衡二叉树
判断某一节点是否平衡的标准 ： 其左右子树的深度之差的绝对值是否不大于 1
判断一棵二叉树是否平衡 ： 其所有节点是否平衡
