四、树与二叉树
1. 二叉树的顺序存储结构
二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有自己的固定位置。
这里要注意一下根结点是取 [0] 和 [1] 的区别。i 层的满二叉树，其节点总数为 2^i - 1 。二叉树每增加一层，结点数就要加倍，所以二叉树的顺序存储结构特别适合完全二叉树。如果二叉树的形态和完全二叉树的差别很大，采用顺序存储结构就很浪费存储空间，这种情况可以采用链式存储结构。
2. 二叉树的链式存储结构
二叉树的二叉链表存储结构删除和插入结点或子树都很灵活。结点动态生成，可充分利用空间。
实现：
//二叉树链表结点结构体
template<typename T>struct BiTNode
{
T data;
BiTNode<T> *lchild, *rchild;
};
//二叉链表结构的二叉树类
enum Tags {Left, Right}; //枚举类型标志位
enum style {Pre, In, Post}; //枚举类型遍历方式
template<typename T>struct StackElem
{//带模板的栈元素类
BiTNode<T> *p;
Tags flag;
}
template<typename T>class SOSTree //声明带模板的静态树表类
template<typename T>class BiTree;
{//带模板的二叉链表结构的二叉树类
friend SOSTree<struct S>; //设置静态树表的实例为友类
protected:
BiTNode<t> *root;
private:
void DestroyBiTree(BiTNode<T>* &t)
{//销毁 t 所指二叉树或子树
if (t != NULL)
{
DestroyBiTree(t->lchild); //递归销毁左子树
DestroyBiTree(t->rchild); //递归销毁右子树
delete t; //释放结点
t = NULL; //指针 t 赋空
}
}
public:
BiTree()
{//构造函数，构造一颗空的二叉树
root = NULL;
}
~BiTree()
{//析构函数，销毁二叉树
DestroyBiTree(root);
}
void CreateBiTreeFromFile(ifstream &f)
{//按先序次序由数据文件输入二叉树中结点的值，构造二叉树
T e;
InputFromFile(f, e); //由文件输入结点的值
if (e == NULL)
return;
root = new BiTNode<T>;
assert(root != NULL);
root->data = e;
BiTree<T> left, right; //子树对象
left.CreateBiTreeFromFile(f); //递归创建左子树
right.CreateBiTreeFromFile(f); //递归创建右子树
root->lchild = left.root; //根结点的左孩子接左子树的根结点
left.root = NULL; //左子树为空树
root->rchild = right.root; //根结点的右孩子接右子树的根结点
right.root = NULL; //右子树为空树
}
bool BiTreeEmpty()const
{//若为空二叉树，则返回 true ；否则返回 false
return root == NULL;
}
int BiTreeDepth(BiTNode<T>* t)const
{//返回 t 所指的二叉树或子树的深度
int i, j;
if (t == NULL)
return 0;
else
{
i = BiTreeDepth(t->lchild);
j = BiTreeDepth(t->rchild);
return i > j ? i+1 : j+1; //t 的深度为其左右子树的深度大者 +1
}
}
void PreOrderTraverse(void(*visit) (BiTNode<T>*))const
{//前序非递归（利用栈）遍历二叉树，对每个结点调用函数 visit 一次且仅一次
stack<BiTNode<T>*> s; //栈元素的类型为结点指针类型
BiTNode<T> *t = root;
s.push(NULL); //压入空指针，作为标记
while(t != NULL)
{
visit(t);
if (t->rchild != NULL)
s.push(t->rchild); //先处理左子树
if (t->lchild != NULL)
t = t->lchild;
else
{
t = s.top();
s.pop();
}
}
}
void InOrderTranverse(void(*visit) (BiTNode<T>*))const
{//中序非递归（利用栈）遍历二叉树，对每个结点调用 visit 一次且仅一次
stack<BiTNode<T>*> s;
BiTNode<T> *t = root;
while(t != NULL || !s.empty())
{
if (t)
{//根指针进栈，遍历左子树
s.push(t);
t = t->lchild;
}
else
{
t = s.top();
s.pop();
visit(t);
t = t->rchild;
}
}
cout << endl;
}
void PostOrderTraverse(void(*visit) (BiTNode<T>*))const
{//后序非递归（利用栈）遍历二叉树，对每个结点调用函数 visit 一次且仅一次
StackElem<T> se;
stack<StackElem<T> > s; //注意：两个 > 中间要有空格，否则与右移运算符相混
BiTNode<T> *t = root;
if (t == NULL)
return;
while(!s.empty() || t != NULL)
{
while(t != NULL)
{//入栈根结点，继续向左，找到最左结点的孩子（空指针）
se.p = t;
se.flag = Left; //表示其出栈时已访问过左子树
s.push(se); //入栈 se
t = t->lchild;
}
se = s.top;
s.pop();
t = se.p;
if (se.flag == NULL) //已访问过左子树
{
se.flag = Right; //表示其出栈时已访问过右子树
s.push(se);
t = t->rchild;
}
else //已访问过右子树
{
visit(t);
t = NULL; //置空，以继续出栈
}
}
}
void LevelOrderTraverse(void(*visit) (BiTNode<T>*))const
{//层序遍历二叉树，对每个结点调用函数 visit 一次且仅一次
queue<BiTNode<T>*> q;
BiTNode<T> *a, *t = root;
if (t != NULL)
{
q.push(t);
while(!q.empty())
{
a = q.front();
q.pop();
visit(a);
if (a->lchild != NULL)
q.push(a->lchild);
if (a->rchild != NULL)
q.push(a->rchild);
}
}
cout << endl;
}
void OrderTraverse(BiTNode<T>* t, style mode, void(*visit) (BiTNode<T>*))
{//根据 mode 的值，先序、中序或后序递归遍历 t 所指的二叉树或子树
if (mode == Pre) //先序递归遍历
visit(t);
OrderTraverse(t->lchild, mode, visit);
if (mode == In) //中序递归遍历
visit(t);
OrderTraverse(t->rchild, mode, visit);
if (mode == Post)
visit(t);
}
BiTNode<T>* Root()
{//返回根结点的地址
return root;
}
bool InsertChild(BiTNode<T>* &p, bool LR, BiTree<T> &c)
{//初始条件：p 指向二叉树中某个结点，非空二叉树 c 的右子树为空
//操作结果：根据 LR 为 false 或 true ，插入 c 为二叉树中 p 所指结点的左或右子树
// p 所指结点的原有左或右子树则成为 c 的右子树，c 为空树
BiTNode<T> *q = c.Root();
c.root = NULL;
if (p != NULL)
{
if (!LR) //把二叉树 c 插为 p 所指结点的左子树
{
q->rchild = p->lchild; //p 所指结点的原有左子树成为 c 的右子树
p->lchild = q; //二叉树 c 成为 p 的左子树
}
else //把二叉树 c 插为 p 所指结点的右子树
{
q->rchild = p->rchild; //p 所指结点的原有右子树成为 c 的右子树
p->rchild = q; //二叉树 c 成为 p 的右子树
}
return true;
}
return false; //p 空
}
bool DeleteChild(BiTNode<T>* &p, bool LR)
{//初始条件：p 指向二叉树中某个结点
//操作结果：根据 LR 为 false 或 true ，删除二叉树中 p 所指结点的左或右子树
if (p != NULL)
{
if (!LR) //删除左子树
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return true;
}
else
return false;
}
T Value(BiTNode<T>* p)const
{//返回二叉树中 p 所指结点的值
return p->data;
}
void Assign(BiTNode<T>* p, T Value)const
{//给二叉树中 p 所指结点赋值为 value
p->data = value;
}
BiTNode<T>* Parent(BiTNode<T>* p)const
{//初始条件：p 指向二叉树的某个结点
//操作结果：若 p 是二叉树的非根结点，则返回它双亲的指针，否则返回 NULL
queue<BiTNode<T>*> q;
BiTNode<T> a;
if (root != NULL)
{
q.push(root);
while(!q.empty())
{
a = q.front();
q.pop();
if (a->lchild && a->lchild == p || a->rchild && a->rchild == p)
return a;
else //未找到 p ，则入队其左右孩子指针（若非空）
{
if (a->lchild != NULL)
q.push(a->lchild);
if (a->rchild != NULL)
q.push(a->rchild);
}
}
}
return NULL;
}
void Child(BiTNode<T>* p, BiTNode<T>* &left, BiTNode<T>* &right)const
{//初始条件：p 指向二叉树的某个结点
//操作结果：分别用 left 和 right 返回 p 的左右孩子指针
left = p->lchild;
right = p->rchild;
}
bool Sibling(BiTNode<T>* p, BiTNode<T>* &sib, bool &LR)const
{//初始条件：p 指向二叉树中某个结点
//操作结果：用 sib 返回 p 的兄弟指针，LR 指示其为左（false）或右（true）兄弟
BiTNode<T> *q = Parent(p);
if (q == NULL)
return false;
if (q->lchild == p)
{
sib = q->rchild;
LR = true;
}
else
{
sib = q->lchild;
LR = false;
}
if (sib != NULL)
return true;
else
return false;
}
};
在上面的实现中，CreateBiTreeFromFile() 是由文件创建二叉树，文件按先序次序输入结点的值，而且还要把叶子结点的左右孩子空指针和度为 1 的结点的空指针输入（以 # 表示）。其原因是只根据结点的先序次序还不能唯一确定二叉树的形状。
由于 BiTNode 结点类型只有左右孩子指针，这使得由 BiTNode 结点类型构造的二叉树查找双亲结点和左右兄弟结点的时间复杂度较高。PBiTNode 结点类型在 BiTNode 的基础上增加了指向双亲的指针。
//三叉链表结点类型结构体
template<typename T>struct PBiTNode
{
T data;
PBiTNode<T> *lchild, *rchild, *parent;
};
由于增加了指向双亲的指针，大大降低了查找双亲结点和左右兄弟结点的时间复杂度，但在创建二叉树和向二叉树插入子树时要处理插入结点的双亲指针。
实现：
//三叉链表结构的二叉树类
template<typename>class PBiTree: public BiTree<T>
{//带模板并继承二叉链表结构的二叉树
public:
void CreateBiTreeFromFile(ifstream &f)
{//按先序次序由数据文件输入二叉树中节点的值，构造二叉树
T e;
InputFromFile(f, e);
if (e == NULL)
return;
root = new PBiTNode<T>;
assert(root != NULL);
root->data = e;
root->parent = NULL;
PBiTree<T> left, right;
left.CreateBiTreeFromFile(f);
right.CreateBiTreeFromFile(f);
root->lchild = left.root;
if (left.root != NULL)
{
left.root->parent = root;
left.root = NULL;
}
root->rchild = right.root;
if (right.root != NULL)
{
right.root->parent = root;
right.root = NULL;
}
}
bool InsertChild(PBiTNode<T>* &p, bool LR, PBiTree<T> &c)
{//初始条件：p 指向二叉树中某个结点，非空二叉树 c 的右子树为空
//操作结果：根据 LR 为 false 或 true ，插入 c 为二叉树中 p 所指结点的左或右子树，
// p 所指结点的原有左或右子树则成为 c 的右子树，c 成为空树
PBiTNode<T> *q = c.Root();
c.root = NULL;
if (p != NULL)
{
if (!LR) //把二叉树 c 插为 p 所指节点的左子树
{
q->rchild = p->lchild;
p->lchild->parent = q;
p->lchild = q;
}
else //把二叉树 c 插为 p 所指节点的右子树
{
q->rchild = p->rchild;
p->rchild->parent = q;
p->rchild = q;
}
q->parent = p;
return true;
}
return false;
}
BiTNode<T>* Parent(BiTNode<T>* p)const
{//初始条件：p 指向二叉树中某个结点
//操作结果：若 p 是二叉树的非根结点，则返回它双亲的指针，否则返回 NULL
return p->parent;
}
bool Sibling(BiTNode<T>* p, BiTNode<T>* &sib, bool &LR)const
{//初始条件：p 指向二叉树中某个结点
//操作结果：用 sib 返回 p 的兄弟指针，LR 指示其为左（false）或右（true）兄弟
if (p->parent == NULL)
return false;
if (p->parent->lchild == p)
{
sib = p->parent->rchild;
LR = true;
}
else
{
sib = p->parent->lchild;
LR = false;
}
return sib != NULL;
}
};
3. 二叉树的遍历
遍历二叉树就是按某种规则，对二叉树的每个结点都访问一次，而且仅访问一次。这实际上就是将非线性的二叉树结构线性化。遍历二叉树的方法有先序、中序、后序和层序，访问顺序各不相同。先序、中序和后序遍历利用递归很简单，层序遍历可以利用队列，先序、中序和后序非递归遍历可以利用栈。
4. 线索二叉树
为了更方便、更快捷地遍历二叉树，最好在二叉树的结点上增加两个指针，他们分别指向对二叉树进行某种遍历时该结点的前驱和后继结点。这样，从二叉树的任一结点都可以方便地找到其遍历的前驱和后继结点。但这样做大大降低了结点的存储密度。另外，根据二叉树的性质，有 n0 = n2 + 1 （叶子结点数 = 度为2的结点数 + 1）。空链域 = 2 * n0 + n1 （叶子结点有两个空链域，度为 1 的结点有一个空链域）= n0 + n1 + n2 + 1 = n + 1 。也就是说，再由 n 个结点组成的二叉树中，有 n+1 个指针是空指针。如果能利用这 n+1 个空指针，使它们指向结点的前驱（当左孩子指针空）或后继（当右孩子指针空），则既可不降低结点的存储密度，又可方便快捷地遍历二叉树。不过，这样就无法区分左右孩子指针所指的到底是结点的左右孩子，还是结点的前驱后继。为了有所区别，另增两个域 LTag 和 RTag 。当所指的是孩子，其值为 0 （Link）；当所指的是前驱后继，其值为 1 （Thread）。这样做，结点的存储密度也有所降低，但不大。因为 LTag 和 RTag 分别只占两个比特位即可。
//线索二叉链表结点类型结构体
enum PointerTag {Link, Thread}; //Link (0)：指针，Thread (1)：线索
template<typename T>struct BiThrNode
{
T data;
BiThrNode<T> *lchild, *rchild;
PointerTag LTag:2, RTag:2; //各占 2 bit
}；
构造线索二叉树和构造二叉链表结构的二叉树方法相似，但除了结点的结构不同之外，它们的区别有两点：
- 线索二叉树比二叉链表结构的二叉树多了一个头结点，其 lchild 域指向根结点；
- 构造线索二叉树时，若有左右孩子结点，还要给左右标志赋值 0 （Link）。
构造一棵可以线索化的二叉树后还需要完成线索化。对于一棵给定的二叉树，其先序、中序、后序和层序的顺序是不同的。显然其线索化的操作和遍历的操作也是不同的。
实现：
//线索而茶链表结构的二叉树类
template<typename T>class BiThrTree
{//带模板的线索二叉链表结构的二叉树
private:
BiThrNode<T> *Thrt, *pre; //Thrt 指向头结点，pre在遍历时始终指向刚刚访问过的结点
void CreateBiThrTreeFromFile(ifstream &f, BiThrNode<T>* &t)
{//按先序次序由文件流 f 输入二叉树结点的值，构造由 t 所指的二叉树
T e;
InputFromFile(f, e);
if (e == NULL)
t = NULL;
else
{
t = new BiThrNode<T>;
assert(t != NULL);
t->data = e;
CreateBiThrTreeFromFile(f, t->lchild);
if (t->lchild != NULL)
t->LTag = Link;
else
t->LTag = Thread;
CreateBiThrTreeFromFile(f, t->rchild);
if (t->rchild != NULL)
t->RTag = Link;
else
t->RTag = Thread;
}
}
void DestroyBiTree(BiThrNode<T>* &t)
{//~BiThrTree() 调用的递归函数，销毁 t 所指二叉树或子树
if (t != NULL)
{
if (t->LTag == Link)
DestroyBiTree(t->lchild);
if (t->RTag == Link)
DestroyBiTree(t->rchild);
delete t;
t = NULL;
}
}
void InOrderThreading(BiThrNode<T>* p)
{//通过中序递归遍历进行中序线索化，线索化后 pre 指向最后一个结点
if (p != NULL)
{
if (p->LTag == Link)
InOrderThreading(p->lchild);
else
p->lchild = pre;
if (pre->RTag == Thread)
pre->rchild = p;
pre = p;
if (p->Rtag == Link)
InOrderThreading(p->rchild);
}
}
void PreOrderThreading(BiThrNode<T>* p)
{//通过先序递归进行先序线索化
if (p != NULL)
{
if (pre->RTag == Thread)
pre->rchild = p;
if (p->LTag == Thread)
p->lchild = pre;
pre = p;
if (p->LTag == Link)
PreOrderThreading(p->lchild);
if (p->RTag == Link)
PreOrderThreading(p->rchild);
}
}
void PostOrderThreading(BiThrNode<T>* p)
{//通过后序递归遍历进行后序线索化
if (p != NULL)
{
if (p->LTag == Link)
PostOrderThreading(p->lchild);
if (p->RTag == Link)
PostOrderThreading(p->rchild);
if (p->LTag == Thread)
p->lchild = pre;
if (pre->Rtag == Thread)
pre->rchild = p;
pre = p;
}
}
public:
BiThrTree()
{//构造函数，构造空的线索二叉树
Thrt = new BiThrNode<T>;
assert(Thrt != NULL);
Thrt->LTag = Link; //左标志为指针
Thrt->Rtag = Thread; //右标志为线索
Thrt->rchild = Thrt->lchild = Thrt; //左右孩子指针回指
}
~BiThrTree()
{//析构函数，销毁线索二叉树
if (Thrt != NULL)
{
if (Thrt->lchild)
DestroyBiTree(Thrt->lchild);
delete Thrt;
}
}
void CreateBiThrTreeFromFile(char* FileName)
{//按先序次序由数据文件输入线索二叉树结点的值，构造线索二叉树
ifstream fin(FileName);
CreateBiThrTreeFromFile(fin, Thrt->lchild);
fin.close();
}
void InOrderThreading()
{//中序遍历线索二叉树，并将其中序线索化
if (Thrt->lchild != Thrt)
{
pre = Thrt;
InOrderThreading(Thrt->lchild);
pre->rchild = Thrt;
Thrt->rchild = pre;
}
}
void InOrderTranverse(void(*visit) (BiThrNode<T>*))const
{//中序遍历线索二叉树
BiThrNode<T> *p = Thrt->lchild;
while(p != Thrt)
{
while(p->LTag == Link)
p = p->lchild;
visit(p);
while(p->Rtag == Thread && p->rchild != Thrt)
{//p->rchild 是线索（后继），且不是遍历的最后一个结点
p = p->rchild;
visit(p);
}
p = p->rchild; //若 p->rchild 不是线索（是右孩子），p 指向右孩子，返回循环，
//找到这颗子树中序遍历的第一个结点
}
}
void PreOrderThreading()
{//先序线索化二叉树，头结点的右孩子指针指向先序遍历的最后一个结点
if (Thrt->lchild != Thrt)
{
pre = Thrt;
PreOrderThreading(Thrt->lchild);
pre->rchild = Thrt;
Thrt->rchild = pre;
}
}
void PreOrderTraverse(void(*visit) (BiThrNode<T>*))const
{//先序遍历线索二叉树
BiThrNode<T> *p = Thrt->lchild;
while(p != Thrt)
{
visit(p);
if (p->LTag == Link)
p = p->lchild;
else
p = p->rchild;
}
}
void PostOrderThreading()
{//后序递归线索化二叉树
if (Thrt->lchild != Thrt)
{
Thrt->rchild = Thrt->lchild;
pre = Thrt;
PostOrderThreading(Thrt->lchild);
if (pre->Rtag != Link) //最后一个结点没有右孩子
pre->rchild = Thrt; //最后一个结点的后继指向头结点
}
}
};
线索二叉树和二叉链表结构的二叉树相比，多了一个头结点。其左孩子指针指向根结点，右孩子指针（线索）指向遍历所访问的最后一个结点；另外，它每个结点的左右孩子指针都不是空指针。在没有孩子的情况下，分别指向该结点遍历的前驱和后继。
InOrderThreading() 的算法是：令数据成员 pre 总是指向遍历的前驱结点， p 指向当前结点；在遍历过程总，如果 p 所指结点没有左孩子，则结点的左孩子指针指向 pre 所指结点，结点的 LTag 域的值为 Thread ；如果 p 所指结点没有右孩子，则结点的右孩子指针指向 p ，结点的 Rtag 域的值为 Thread 。
对于中序线索二叉树，我们能不能在找到遍历的第一个结点后，顺着右孩子指针一直找到遍历的最后一个结点呢？这是不一定的。因为结点的右孩子指针并不一定指向后继结点，它也可能指向右孩子，而右孩子并不一定恰好是后继结点。
InOrderTranverse() 的算法是：当树不空时，由树根向左找，一直找到没有左孩子的结点（最左结点）。这就是中序遍历的第一个结点。若该结点没有右孩子，则右孩子指针指向其后继结点；否则，以其右孩子为子树的根向左找，一直找到没有左孩子的结点。这就是后继结点。当结点的右孩子指针指向头结点，遍历结束。
先序线索化的递归函数 PreOrderThreading() 和后序线索化的递归函数 PostOrderThreading() 与中序线索化的递归函数 InOrderThreading() 很相像，都是利用递归进行线索化，只不过顺序不同。
PreOrderTraverse() 的算法是：根结点是遍历的第一个结点，如果结点有左孩子，则左孩子是其后继；若结点没有左孩子，则右孩子指针所指的结点是其后继（无论该结点有没有右孩子）。
PostOrderTraverse() 的算法是：头结点的左右孩子指针都指向根结点，后序遍历的第一个结点必定是叶子结点，它的左孩子指针指向头结点，对于后序线索化二叉树，因为根结点实在最后遍历，所以后序遍历的算法及时线索化也需要栈或者递归，故后序线索化不具有实际应用价值。
5. 二叉排序树
实现：
//定义数据元素类型和关键字类型
typedef int KeyType;
struct T
{
KeyType key; //关键字
int others; //其他数据
};
//对两个数值型关键字的比较约定如下的宏定义
#define EQ(a, b) ((a) == (b))
#define LT(a, b) ((a) < (b))
#define LQ(a, b) ((a) <= (b))
#define GT(a, b) ((a) > (b))
//二叉排序树的删除类
template<typename T>class BSDTree: public BiTree<T>
{//带模板并继承 BiTree 的二叉排序树的删除类
protected:
virtual void Delete(BiTNode<T>* &p)=0; //虚函数
bool DeleteBST(BiTNode<T>* &p, KeyType key)
{//若二叉排序树 p 中存在关键字等于 key 的数据元素时，则删除该数据元素结点，
//并返回 true ，否则返回 false
if (p == NULL)
return false;
else
{
if EQ(key, p->data.key)
{
Delete(p);
return true;
}
else if LT(key, p->data.key) //关键字小于 p 所指结点的关键字
return DeleteBST(p->lchild, key); //在 p 的左孩子中递归查找
else //关键字大于 p 所指结点的关键字
return DeleteBST(p->rchild, key); //在 p 的右孩子中递归查找
}
}
public:
bool Delete(KeyType key)
{//若二叉排序树 p 中存在关键字等于 key 的数据元素时，则删除该数据元素结点，
//并返回 true ，否则返回 false
return DeleteBST(root, key);
}
};
//二叉排序树的类
template<typename T>class BSTree: public BSDTree<T>
{//带模板并继承 BSDTree 的二叉排序树
private:
void Delete(BiTNode<T>* &p)
{//从二叉排序树中删除 p 所指结点，并重接它的左或右子树
BiTNode<T> *s, *q = p;
if (p->rchild == NULL)
{//p 的右子树空则只须重接它的左子树（待删结点是叶子也走此分支）
p = p->lchild;
delete q;
}
else if (p->lchild = NULL)
{//p 的左子树空，只须重接它的右子树
p = p->rchild;
delete q;
}
else //p 的左右子树均不空
{
s = p->lchild;
while(s->rchild != NULL)
{
q = s;
s = s->rchild;
}//s 向右走到尽头(s 指向待删结点的前驱结点，q 指向 s 的双亲结点)
p->data = s->data;
if (q != p) //情况一：待删结点的左孩子有右子树
q->rchild = s->lchild;
else //情况二：待删结点的左孩子没有右子树
q->lchild = s->lchild;
delete s;
}
}
protected:
bool SearchBST(BiTNode<T>* &p, KeyType key, BiTNode<T>* f, BiTNode<T>* &q)
{//在二叉排序树 p 中递归查找其关键字等于 key 的数据元素，若查找成功，
//则指针 q 指向该数据元素结点，并返回 true ，否则指针 q 指向查找路径上访问的最后
//一个结点（以便插入），并返回 false ，指针 f 指向 p 的双亲，其初始调用值为 NULL
if (p == NULL)
{
q = f;
return false;
}
else if EQ(key, p->data.key)
{
q = p;
return true;
}
else if LT(key, p->data.key) //小于
return SearchBST(p->lchild, key, p, q); //递归查找左子树
else //大于
return SearchBST(p->rchild, key, p, q); //递归查找右子树
}
public:
BiTNode<T>* SearchBST(BiTNode<T>* p, KeyType key)const
{//在指针 p 所指二叉排序树或平衡二叉树中递归查找关键字等于 key 的数据元素，
//成功返回结点指针，失败返回空指针
if (p == NULL || EQ(key, p->data.key))
return p;
else if LT(key, p->data.key) //小于
return SearchBST(p->lchild, key);
else //大于
return SearchBST(p->rchild, key);
}
bool Insert(T e)
{//若二叉排序树中没有关键字等于 e.key 的元素，插入 e 并返回 true ；否则返回 false
BiTNode<T> *p, *s;
if (!SearchBST(root, e.key, NULL, p))
{//查找不成功，p 指向查找路径上访问的最后一个叶子结点
s = new BiTNode<T>;
s->data = e;
s->lchild = s->rchild = NULL;
if (p == NULL)
root = s;
else if LT(e.key, p->data.key) //小于
p->lchild = s;
else
p->rchild = s;
return true;
}
else //查找成功
return false;
}
void CreateBiTreeFromFile(char* FileName)
{//覆盖基类函数，避免构造出不符合二叉排序顺序的二叉树
}
void InsertChild(BiTNode<T>* &p, bool LR, BiTree<T> &c)
{//覆盖基类函数
return false;
}
void Assign(BiTNode<T>* p, T value)
{//覆盖基类函数
}
};
二叉排序树中任何一个结点，其左子树上所有结点的关键字值均小于该结点的关键字值；其右子树所有结点的关键字值均大于该结点的关键字值。中序遍历二叉排序树可得到按关键字有序的序列。通过中序和先序（或中序和后序）遍历二叉排序树，就可以确定二叉排序树的形态。
在二叉排序树中插入一个结点，这个结点总是叶子结点。删除一个结点从算法上分有待删除结点最多一棵子树和待删除结点有两棵子树两种情况。
- 如果待删除结点最多有一棵子树，则待删结点与它的双亲结点最后存在的唯一的孩子结点形成单链表结构。只要将其双亲结点原来指向其的指针指向其唯一的孩子结点（若待删结点是叶子结点，则指空），就从二叉排序树中将其删除了，同时仍然保持二叉排序树的有序性。
- 如果待删结点的两棵子树都存存在，删除其需重接两棵子树，是比较麻烦的。故采取变通的方法：查找待删结点的前驱结点，这个结点是待删结点左子树的最右结点，它没有右子树。把这个结点的值赋给待删结点，相当于删除了待删结点，但却在同一位置增加了一个前驱结点。这样就有了两个相邻的、值与前驱结点相同的结点。再把原来的前驱结点删除即可。原来的前驱结点最多有一棵子树，删除它是很容易的。这样做仍保持了二叉排序树的有序性。当然，对称的，也可以利用待删结点的后继结点（它是待删结点右子树的最左结点）来处理这个问题。
二叉排序树的形态与数据元素插入的顺序有关。如果数据输入的顺序不当，二叉排序树的深度可能很深，导致平均查找长度很长，失去了二叉排序树存在的意义。平衡二叉树（也是排序树）克服了二叉排序树的这个缺点，它通过当左右子树的深度差大于 1 时调换根结点，使树的深度尽量浅，同时仍保持排序特性。
6. 平衡二叉树
实现：
//平衡二叉树的结点类型结构体
template<typename T>struct AVLTNode
{
T data;
int bf; //结点的平衡因子
AVLTNode<T> *lchild, *rchild;
};
//设置平衡因子的值（左子树的深度 - 右子树的深度）
const int LH = 1; //左高
const int EH = 0; //等高
const int RH = -1; //右高
//二叉排序树转换操作的类
template<typename T>class ChangeTree: public BSTree<T>
{//带模板并继承 BSTree 的二叉排序树转换操作的类
protected:
void LL_Rotate(BiTNode<T>* &p)
{//对 *p 为根的平衡二叉树的 LL 型失衡作处理平衡，但不修改平衡因子
BiTNode<T> *lc = p->lchild; //lc 指向中值结点
p->lchild = lc->rchild; //大值结点的新左孩子为中值结点的右孩子
lc->rchild = p; //中值结点的新右孩子为大值结点
p = lc; //p 指向中值结点（新的根结点）
}
void RR_Rotate(BiTNode<T>* &p)
{//对 *p 为根的平衡二叉树的 RR 型失衡作处理平衡，但不修改平衡因子
BiTNode<T> *rc = p->rchild; //rc 指向中值结点
p->rchild = rc->lchild; //小值结点的新右孩子为中值结点的左孩子
rc->lchild = p; //中值结点的新左孩子为小值结点
p = rc; //p 指向中值结点（新的根结点）
}
void LR_Rotate(BiTNode<T>* &p)
{//对 *p 为根的平衡二叉树的 LR 型失衡作处理平衡，但不修改平衡因子
BiTNode<T> *lc = p->lchild; //lc 指向小值结点
p->lchild = lc->rchild->rchild; //中值结点的右子树成为大值结点的左子树
lc->rchild->rchild = p; //大值结点成为中值结点的右子树
p = lc->rchild; //根结点指向中值结点
lc->rchild = p->lchild; //中值结点的左子树成为小值结点的右子树
p->lchild = lc; //小值结点成为中值结点的左子树
}
void RL_Rotate(BiTNode<T>* &p)
{//对 *p 为根的平衡二叉树的 RL 型失衡作处理平衡，但不修改平衡因子
BiTNode<T> *rc = p->rchild; //rc 指向大值结点
p->rchild = rc->lchild->lchild; //中值结点的左子树成为小值结点的右子树
rc->lchild->lchild = p; //小值结点成为中值结点的左子树
p = rc->lchild; //根指针指向中值结点
rc->lchild = p->rchild; //中值结点的右子树成为大值结点的左子树
p->rchild = rc; //大值结点成为中值结点的右子树
}
BiTNode<T>* Parent(BiTNode<T>* p)const
{//覆盖基类函数
if (root == p)
return NULL;
BiTNode<T> *q = root;
while(q != NULL)
{
if (p->data.key > p->data.key) //p 在左子树中
if (q->lchild == p)
return q;
else
q = q->lchild;
else //p 在右子树
if (q->rchild == p)
return q;
else
q = q->rchild;
}
return NULL;
}
BiTNode<T>* Grandfather(BiTNode<T>* p)const
{//返回 p 的祖父结点，否则返回 NULL
BiTNode<T> *a = Parent(p);
if (a != NULL)
a = Parent(a);
return a;
}
};
//平衡二叉树的类
template<typename T>class AVLTree: public ChangeTree<T>
{//带模板并继承 ChangeTree 的平衡二叉树类
private:
void LeftBalance(AVLTNode<T>* &p)
{//初始条件：原本 p 的左子树比右子树高（LH），又在左子树中插入了结点，导致失衡
//对不平衡的树 p 做平衡处理，p 的返回值指向新的平衡二叉树根结点
AVLTNode<T> *lc, *rd;
lc = p->lchild;
switch(lc->bf) //检查 *p 左子树的平衡度，并作相应平衡处理
{
case LH: //LL 型不平衡
p->bf = lc->bf = EH; //旋转后，大值结点的平衡因子都为 EH
LL_Rotate(p);
break;
case RH: //LR 型不平衡
rd = lc_>rchild;
switch(rd->bf) //检查*p左孩子的右子树的平衡度，修改 *p 及其左孩子的平衡因子
{
case LH: //新结点插入在 *p 左孩子的右子树的左子树上
p->bf = RH; //旋转后，大值结点的平衡因子为右高
lc->bf = EH; //旋转后，小值结点的平衡因子为等高
break;
case EH: //新结点插入在 *p 左孩子的右孩子（叶子）上
p->bf = lc->bf = EH; //旋转后，原根和左孩子结点的平衡因子都为等高
break;
case RH: //新结点插入在 *p 左孩子的右子树的右子树上
p->bf = EH; //旋转后，大值结点的平衡因子为等高
lc->bf = LH; //旋转后，小值结点的平衡因子为左高
}
rd->bf = EH; //旋转后的新根结点（中值结点）的平衡因子为等高
LR_Rotate(p);
}
}
void RightBalance(AVLTNode<T>* &p)
{//初始条件：原本 p 的右子树比左子树高（RH），又在右子树中插入了结点，导致失衡
//对不平衡的树 p 做平衡处理，p 的返回值指向新的平衡二叉树根结点
AVLTNode<T> *rc, *ld;
rc = p->rchild;
switch(rc->bf) //检查 *p 的右子树的平衡度，并作相应平衡处理
{
case RH: //RR 型不平衡
p->bf = rc->bf = EH; //旋转后，小值结点和中值结点的平衡因子都是 EH
RR_Rotate(p);
break;
case LH: //RL 型不平衡
ld = rc->lch;
switch(ld->bf) //检查*p右孩子的左子树的平衡度，修改 *p 及其右孩子的平衡因子
{
case RH: //新结点插入在 *p 右孩子的左子树的右子树上
p->bf = LH; //旋转后，小值结点的平衡因子为左高
rc->bf = EH; //旋转后，大值结点的平衡因子为等高
break;
case EH: //新结点插入为 *p 右孩子的左孩子（叶子）
p->bf = rc->bf = EH; //旋转后，原根和右孩子结点的平衡因子都为等高
break;
case LH: //新结点插入在 *p 右孩子的左子树的左子树上
p->bf = EH; //旋转后，小值结点的平衡因子为等高
rc->bf = RH; //旋转后，大值结点的平衡因子为右高
}
ld->bf = EH; //旋转后的新根结点（中值结点）的平衡因子为等高
RL_Rotate(p);
}
}
bool InsertAVL(AVLTNode<T>* &p, T e, bool &taller)
{//若在平衡二叉树 p 中不存在和 e 有相同关键字的结点，则插入一个数据元素为 e 的新
//结点，并返回 true ，否则返回 false 。若因插入使平衡二叉树 p 失衡，则做平衡旋转
//处理，taller 反映调用 InsertAVL() 前后 p 是否长高
if (p == NULL) //树空
{//插入新结点，树 “长高” ，置 taller 为 true
p = new AVLTNode<T>;
p->data = e;
p->lchild = p->rchild = NULL;
p->bf = EH;
taller = true;
}
else //树非空
{
if EQ(e.key, p->data.key)
return false;
else if LT(e.key, p->data.key) //小于
{
if (!InsertAVL(p->lchild, e, taller))
return false; //没插入
if (taller) //插入且左子树 “长高”
switch(p->bf) //检查 *p 的平衡度，并作适当处理
{
case LH: //原本 p 的左子树比右子树高，现在左子树又 “长高” 了
LeftBalance(p);
taller = false;
break;
case EH: //原本左右子树等高，现在左子树 “长高” 了
p->bf = LH;
taller = true;
break;
case RH: //原本 p 的右子树比左子树高，现在左右子树等高
p->bf = EH;
taller = false;
}
}
else //大于
{
if (!InsertAVL(p->rchild, e, taller))
return false; //未插入
if (taller) //已插入
switch(p->bf) //检查 p 的平衡度
{
case LH: //原本 p 的左子树比右子树高，现在左右子树等高
p->bf = EH;
taller = false;
break;
case EH: //原本 p 的左右子树等高，现在右子树 “长高” 了
p->bf = RH;
taller = true;
break;
case RH: //原本右子树比左子树高，现在右子树又 “长高” 了
RightBalance(p);
taller = false;
}
}
}
return true;
}
bool DeleteAVL(AVLTNode<T>* &p, T &e, bool &lower)
{//若在 AVL 树 p 中存在和 e 相同关键字的结点，则删除该结点，并返回 true，
//e 返回删除的结点，否则返回 false 。若因删除而使 AVL 树 p 失衡，则做平衡旋转
//处理，lower 反映在调用 DeleteAVL() 前后 p 是否降低
AVLTNode<T> *rc, *lc;
T e1;
if (p == NULL)
return false;
else
{
if EQ(e.key, p->data.key) //相等
{
e = p->data;
rc = p;
if (p->lchild != NULL && p->rchild != NULL)
{//p 所指结点的度为 2 （左右孩子均有），找前驱或后继结点代替删除
if (p->bf == RH) //右子树更高，找后继
{
lc = p->rchild;
while(lc->lchild)
lc = lc->lchild;
}
else //左子树更高，找前驱
{
lc = p->lchild;
while(lc->rchild)
lc = lc->rchild;
}
e1 = lc->data;
DeleteAVL(p, e1, lower);
rc->data = e1;
}
else //p 所指结点的度为 1 或 0
{
if (p->rchild == NULL)
p = p->lchild;
else
p = p->rchild;
delete rc;
lower = true;
}
}
else if LT(e.key, p->data.key) //大于
{
if (!DeleteAVL(p->lchild, e, lower))
return false; //没删除
if (lower) //删除导致子树降低
{
switch(p->bf) //对 p 所指结点平衡因子分类分析
{
case EH: //原来等高，现在左子树有了删除
p->bf = RH;
lower = false;
break;
case LH: //原来左高，现在左子树有了删除
p->bf = EH;
lower = true;
break;
case RH: //原来右高，现在左子树有了删除，失衡
D_LeftBalance(p, lower);
}
}
}
else //小于
{
if (!DeleteAVL(p->rchild, e, lower))
return false; //未删除
if (lower) //删除导致子树降低
{
switch(p->bf) //对 p 所指结点的平衡因子分类分析
{
case EH: //原来等高，现在右子树有了删除
p->bf = LH;
lower = false;
break;
case RH: //原来右高，现在右子树有了删除
p->bf = EH;
lower = true;
break;
case LH: //原来左高，现在右子树有了删除，失衡
D_RightBalance(p, lower);
}
}
}
return true;
}
}
void D_LeftBalance(AVLTNode<T>* &p, bool &lower)
{//删除结点调用的左失衡处理函数
AVLTNode<T> *ld, *rc = p->rchild;
switch(rc->bf)
{
case EH: //rc 左右子树等高
rc->bf = LH;
p->bf = RH;
RR_Rotate(p);
lower = false;
break;
case RH: //rc 的右子树高于左子树
p->bf = rc->bf = EH;
RR_Rotate(p);
lower = true;
break;
case LH: //rc 的左子树高于右子树
ld = rc->lchild;
switch(ld->bf)
{
case EH: //ld 左右子树等高
p->bf = rc->bf = EH;
break;
case LH: //ld 的左子树高
p->bf = EH;
rc->bf = RH;
break;
case RH: //ld 的右子树高
p->bf = LH;
rc->bf = EH;
}
ld->bf = EH;
RL_Rotate(p);
lower = true;
}
}
void D_RightBalance(AVLTNode<T>* &p)
{//删除结点调用的右失衡处理函数
AVLTNode<T> *rd, *lc = p->lchild;
switch(lc->bf)
{
case EH: //左右子树
lc->bf = RH;
p->bf = LH;
LL_Rotate(p);
lower = false;
break;
case LH: //左子树高于右子树
p->bf = lc->bf = EH;
LL_Rotate(p);
lower = true;
break;
case RH: //右子树高于左子树
rd = lc->rchild;
switch(rd->bf)
{
case EH: //rd 的左右子树等高
p->bf = lc->bf = EH;
break;
case RH: //rd 的右子树高
p->bf = EH;
lc->bf = LH;
break;
case LH: //rd 的左子树高
p->bf = RH;
lc->bf = EH;
}
rd->bf = EH;
LR_Rotate(p);
lower = true;
}
}
public:
bool Insert(T e)
{//若在平衡二叉排序树中不存在和 e 有相同关键字的结点，则插入一个数据元素为 e 的
//新结点，并返回 true ；否则返回 false 。若因插入失衡，则作平衡旋转处理
bool taller;
return InsertAVL(root, e, taller);
}
bool Delete(T &e)
{//在平衡二叉排序树中删除结点，成功返回 true ，否则返回 false 。若因删除造成失衡
//则作平衡旋转处理
bool lower;
return DeleteAVL(root, e, lower);
}
bool DeleteChild(AVLTNode<T>* &p, int LR)
{//覆盖基类函数，避免由于删除子树导致失衡
return false;
}
};
插入结点导致平衡二叉树失衡只有 4 中情况：
- 在左子树的左孩子分支上插入结点导致失衡，称为 LL 型
- 在左子树的右孩子分支上插入结点导致失衡，称为 LR 型
- 在右子树的左孩子分支上插入结点导致失衡，称为 RR 型
- 在右子树的右孩子分支上插入结点导致失衡，称为 RL 型
与插入结点不同的是，删除结点有可能要作多次平衡旋转处理。
7. 红黑树
红黑树也是一种平衡二叉树，红黑树中任何一个结点的左右子树的 “黑色深度” 是相同的，且不允许出现父子都是红色结点的情况。。所以红黑树左右子树的高度差之比不会大于 2 。它的平衡性不如 AVL 树，但它的插入、删除算法比 AVL 树易于实现。因此是一种较好的排序二叉树结构。AVL 树和红黑树的高度都为 O（logn），其中 n 是树的结点数。
实现：
//红黑树的结点类型结构体
enum Color {Red, Black};
template<typename T>struct RBTNode
{
T data;
Color RB; //结点颜色
RBTNode<T> *lchild, *rchild;
};
//红黑树的类
template<typename T>class RBTree: public ChangeTree<T>
{//带模板并继承 ChangeTree 的红黑树类
private:
RBTNode<T>* Uncle(RBTNode<T>* p)const
{//返回 p 的叔叔结点，否则返回 NULL
RBTNode<T> *g, *l, *r, *a = Parent(p);
if (p != NULL)
{
g = Parent(a);
Child(g, l, r); //l 和 r 分别指向 g 的左右孩子
if (l == a)
return r;
else
return l;
}
return NULL;
}
void AdjustDoubleRed(RBTNode<T>* &s, RBTNode<T>* &p)
{//对 *s 和 *s 的双亲结点 *p 作递归双红调整
RBTNode<T> *u, *g, *gp;
int flag;
u = Uncle(s);
g = Grandfather(s);
if (g == root)
flag = 0;
else
{
gp = Parent(g);
if (g->data.key < gp->data.key)
flag = 1; //g 是 gp 的左孩子
else
flag = 2; //g 是 gp 的右孩子
}
if (u == NULL || u->RB == Black)
{
if (g->data.key > p->data.key)
if (p->data.key > s->data.key)
LL_Rotate(g);
else
LR_Rotate(g);
else
if (p->data.key < s->data.key)
RR_Rotate(g);
else
RL_Rotate(g);
g->RB = Black;
g->lchild->RB = g->rchild->RB = Red;
switch(flag)
{
case 0: root = g; break; //更新根结点
case 1: gp->lchild = g; break; //重接 *g 子树
case 2: gp->rchild = g; //重接 *g 子树
}
}
else
{
p->RB = u->RB = Black; //设置双亲结点和叔叔结点为黑色
if (flag > 0) //祖父结点不是根结点
{
g->RB = Red; //设置祖父结点为红色
u = Parent(g); //u 为祖父结点的双亲结点
if (u->RB == Red) //出现双红色问题
AdjustDoubleRed(g, u); //向上递归作双红调整
}
}
}
void AdjustDoubleBlack(RBTNode<T>* &pa, bool lr)
{//由于 *pa 的左（lr = true）或右（lr = false）子树的黑色深度减 1 ，作双黑调整
RBTNode<T> *gp;
int flag;
if (pa == root)
flag = 0;
else
{
gp = Parent(pa);
if (pa->data.key < gp->data.key)
flag = 1;
else
flag = 2;
}
if (lr) //*pa 的左孩子被删除
{
if (pa->lchild != NULL && pa->lchild->RB == Red) //*pa的新左孩子存在且红
pa->lchild->RB = Black; //设置 *pa 的新左孩子为黑色
else //*pa 的新左孩子不存在或是黑色
{
if (pa->rchild != NULL && pa->rchild->RB == Black) //*pa的右孩子是黑色
{
if (pa->rchild->rchild != NULL && pa->rchild->rchild->RB == Red)
{//*pa 的右孩子的右孩子是红色
pa->rchild->RB = pa->RB; //*pa 的右孩子颜色同 *pa 的（新根）
pa->RB = pa->rchild->rchild->RB = Black;
RR_Rotate(pa);
switch(flag)
{
case 0: root = pa; break;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
}
else if (pa->rchild->lchild != NULL && pa->rchild->lchild->RB==Red)
{
pa->rchild->lchild->RB = pa->RB;
pa->RB = pa->rchild->RB = Black;
RL_Rotate(pa);
switch(flag)
{
case 0: root = pa; break;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
}
else //*pa 的右孩子的左右孩子都是黑色或空
{
pa->rchild->RB = Red;
if (pa->RB == Red)
pa->RB = Black;
else
{
switch(flag)
{
case 1: AdjustDoubleBlack(gp, true); break;
case 2: AdjustDoubleBlack(gp, false);
}
}
}
}
else if (pa->rchild != NULL && pa->rchild->RB == Red)
{
pa->RB = Red;
pa->rchild->RB = Black;
RR_Rotate(pa);
switch(flag)
{
case 0: root = pa; break;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
AdjustDoubleBlack(pa->lchild, true);
}
}
}
else //*pa 的右孩子被删除
{
if (pa->rchild != NULL && pa->rchild->Rb == Red)
pa->rchild->RB = Black;
else
{
if (pa->lchild->lchild != NULL && pa->lchild->lchild->RB == Red)
{
pa->lchild->RB = pa->RB;
pa->RB = pa->lchild->lchild->RB = Black;
LL_Rotate(pa);
switch(flag)
{
case 0: root = pa; break;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
}
else if (pa->lchild->rchild != NULL && pa->lchild->rchild->RB == Red)
{
pa->lchild->rchild->RB = pa->RB;
pa->RB = pa->lchild->RB = Black;
LR_Rotate(pa);
switch(flag)
{
case 0: root = pa;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
}
else //*pa 的左孩子的左右孩子都是黑色或空
{
pa->lchild->RB = Red;
if (pa->RB == Red)
pa->Rb = Black;
else
switch(flag)
{
case 1: AdjustDoubleBlack(gp, true); break;
case 2: AdjustDoubleBlack(gp, false);
}
}
}
else if (pa->lchild != NULL && pa->lchild->RB == Red)
{
pa->RB = Red;
pa->lchild->RB = Black;
LL_Rotate(pa);
switch(flag)
{
case 0: root = pa; break;
case 1: gp->lchild = pa; break;
case 2: gp->rchild = pa;
}
AdjustDoubleBlack(pa->rchild, false);
}
}
}
void Delete(RBTNode<T>* &p)
{//从红黑树中删除 p 所指结点，并重接它的左或右子树
RBTNode<T> *pa, *s, *q = p;
bool lr, deleflag = false; //调用双黑调整函数的标志，初始为 false （不调用）
bool rootflag = (p == root);
if (p->rchild == NULL || p->lchild == NULL)
{
if (p->RB == Black && p != root)
{
deleflag = true;
pa = Parent(p);
if (p->data.key < pa->data.key)
lr = true;
else
lr = false;
}
if (p->rchild == NULL)
p = p->lchild;
else
p = p->rchild;
if (rootflag && p != NULL)
p->RB = Black;
delete q;
}
else
{
s = p->lchild;
while(s->rchild != NULL)
{
q = s;
s = s->rchild;
}
if (s->RB == Black)
{
deleflag = true;
pa = Parent(s);
if (s->data.key < pa.data.key)
lr = true;
else
lr = false;
}
p->data = s->data;
if (q != p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
delete s;
}
if (deleflag)
AdjustDoubleBlack(pa, lr);
}
public:
bool Insert(T e)
{//若红黑树中没有关键字等于 e.key 的元素，输入 e 并返回 true ；否则返回 false
RBTNode<T> *p, *s;
if (!SearchBST(root, e.key, NULL, p))
{
s = new RBTNode<T>;
s->data = e;
s->lchild = s->rchild = NULL;
if (p == NULL)
{
root = s;
s->RB = Black;
}
else
{
if LT(e.key, p->data.key) //小于
p->lchild = s;
else
p->rchild = s;
s->RB = Red;
if (p->RB == Red)
AdjustDoubleRed(s, p);
}
return true;
}
else //查找成功
return false;
}
};
8. 伸展树
伸展树也是一种排序二叉树。它并不限制树的左右子树高度差在较低的范围。事实上，有时它还会形成单支树。它通过伸展操作把刚刚插入或查找的结点旋转到根结点的位置。如果查找失败，伸展查找终止处的叶子结点。删除结点后，伸展实际被删结点的父结点。伸展树把访问最频繁的结点聚集在距离树根较近的位置，从而使得平均查找次数较低。所以，伸展树使用与结点的查找频率差别较大的情况。
实现：
//伸展树的类
template<typename T>class SqTree: public ChangeTree<T>
{//带模板并继承 ChangeTree 的伸展树类
private:
void Zig(BiTNode<T>* p)
{//将结点 p 伸展为根结点
if (p->data.key < root->data.key)
{
root->lchild = p->rchild;
p->rchild = root;
}
else
{
root->rchild = p->lchild;
p->lchild = root;
}
root = p;
}
void ZigZig(BiTNode<T>* p, BiTNode<T>* pp, BiTNode<T>* pg)
{//将结点 p 做一次同向或异向偏转，使其深度减少 2 层，pp 是 p 的双亲，pg是p的祖父
BiTNode<T> *r = Parent(pg);
if (pp->data.key < pg->data.key)
{
if (p->data.key < pp->data.key)
{//同向偏转，p 在双亲和祖父的左边
pp->lchild = p->rchild;
pg->lchild = pp->rchild;
pp->rchild = pg;
p->rchild = pp;
}
else
{//异向偏转
pp->rchild = p->lchild;
pg->lchild = p->rchild;
p->lchild = pp;
p->rchild = pg;
}
}
else
{
if (p->data.key > pp->data.key)
{//同向偏转，p 在双亲和祖父的右边
pp->rchild = p->lchild;
pg->rchild = pp->lchild;
pp->lchild = pg;
p->lchild = pp;
}
else
{//异向偏转
pp->lchild = p->rchild;
pg->rchild = p->lchild;
p->rchild = pp;
p->lchild = pg;
}
}
if (r == NULL)
root = p;
else if (r->data.key > p->data.key)
r->lchild = p;
else
r->rchild = p;
}
void Splay(BiTNode<T>* p)
{//伸展 p 所指结点
BiTNode<T> *pg, *pp;
if (p != root && p != NULL)
{
pp = Parent(p);
pg = Grandfather(p);
if (pg == NULL)
Zig(p);
else
{
ZigZig(p, pp, pg);
Splay(p);
}
}
}
void Delete(BiTNode<T>* &p)
{//从二叉树中删除 p 所指结点，并重接它的左或右子树
BiTNode<T> *s = Parent(p), *q = p;
if (p->rchild == NULL)
{
p = p->lchild;
delete q;
}
else if (p->lchild == NULL)
{
p = p->rchild;
delete q;
}
else
{
s = p->lchild;
while(s->rchild != NULL)
{
q = s;
s = s->rchild;
}
p->data = s->data;
if (q != p) //待删结点的左孩子有右子树
q->rchild = s->lchild;
else //待删结点的左孩子没有右子树
q->lchild = s->lchild;
delete s;
s = q;
}
Splay(s);
}
public:
bool Insert(T e)
{//若伸展树中没有关键字等于 e.key 的元素，就插入并返回 true ；否则返回 false
BiTNode<T> *p, *s;
if (!BSTree::SearchBST(root, e.key, NULL, p))
{
s = new BiTNode<T>;
s->data = e;
s->lchild = s->rchild = NULL;
if (p == NULL)
root = s;
else if LT(e.key, p->data.key)
{
p->lchild = s;
Splay(p->lchild);
}
else
{
p->rchild = s;
Splay(p->rchild);
}
return true;
}
else //查找成功
return false;
}
bool Search(KeyType key)
{//在伸展树中查找关键字等于 key 的数据元素，若查找成功，则将该数据元素结点伸展为
//根结点，并返回 true ，否则将查找路径上访问的最后一个结点伸展为根结点并返回false
BiTNode<T> *p;
bool f = BSTree<T>::SearchBST(root, key, NULL, p);
Splay(p);
return f;
}
};
9. 树的存储结构
二叉树是最简单的树，还有多于二叉的树，多于二叉的树统称为树。一棵树无论有多少叉，它最多有一个长子和一个排序恰好在其下的兄弟。孩子-兄弟二叉链表结构的树就是根据这样的定义，把每个结点的结构都统一到了二叉链表结构上。这样有利于对结点进行操作。
在数据结构中，多于一棵树的情况称为 “森林” 。孩子-兄弟二叉链表结构也可以存储森林。根结点为第一棵树的根，其他树的根结点作为第一棵树根结点的兄弟。
实现：
//孩子-兄弟二叉链表结点类型结构体
template<typename T>struct CSNode
{
T data;
CSNode<T> *firstchild, *nextsibling; //长子，下一个兄弟的指针
};
//孩子-兄弟二叉链表结构的树或森林类
template<typename T>class CSTree
{//带模板的孩子-兄弟二叉链表结构的树或森林类
friend DFST<struct V, struct A>; //设置深度优先生成树类的实例为友类
private:
CSNode<T> *root;
void ClearTree(CSNode<T>* &t)
{//清空 t 所指树或森林
if (t != NULL)
{
ClearTree(t->firstchild);
ClearTree(t->nextsibling);
delete t;
t = NULL;
}
}
int TreeDepth(CSNode<T> *t)const
{//返回树 t 的深度
CSNode<T> *p;
int depth, max = 0;
if (t == NULL)
return 0;
for(p = t->firstchild; p != NULL; p = p->nextsibling)
{//对于树 t 根结点的所有孩子结点，求子树深度最大值
depth = TreeDepth(p);
if (depth > max)
max = depth;
}
return max+1;
}
void PreOrderTraverse(CSNode<T>* t, void(*visit) (CSNode<T>*))const
{//先序递归遍历
if (t != NULL)
{
visit(t);
PreOrderTraverse(t->firstchild, visit);
PreOrderTraverse(t->nextsibling, visit);
}
}
void PostOrderTraverse(CSNode<T>* t, void(*visit) (CSNode<T>*))const
{//后序递归遍历
if (t != NULL)
{
PostOrderTraverse(t->firstchild, visit);
visit(t);
PostOrderTraverse(t->nextsibling, visit);
}
}
public:
CSTree()
{//构造函数，构造空树或森林
root = NULL;
}
~CSTree()
{//析构函数，清空树或森林
ClearTree();
}
void ClearTree()
{//清空树或森林
ClearTree(root); //递归清空
}
void CreateTreeFromFile(char *FileName)
{//根据文件安层序构造树或森林
ifstream fin(FileName);
CSNode<T> *p;
queue<CSNode<T>*> q;
int i, m;
fin >> m; //树的棵数
root = new CSNode<T>;
fin >> root->data;
q.push(root);
p = root;
for(i = 1; i < m; i++) //对除第一棵树之外的其他树
{
p->nextsibling = new CSNode<T>;
p = p->nextsibling;
fin >> p->data;
q.push(p);
}
p->nextsibling = NULL;
while(!q.empty())
{
p = q.front();
q.pop();
fin >> m; //输入 p 所指结点的孩子数
if (m > 0) //p 所指结点有孩子
{
p = p->firstchild = new CSNode<T>;
fin >> p->data;
q.push(p);
for(i = 1; i < m; i++)
{
p->nextsibling = new CSNode<T>;
p = p->nextsibling;
fin >> p->data;
q.push(p);
}
p->nextsibling = NULL;
}
else //没孩子
p->firstchild = NULL;
}
fin.close();
}
bool TreeEmpty()const
{//判空
if (root == NULL)
return true;
else
return false;
}
int TreeDepth()const
{//返回树或森林的深度（森林中所有树中深度的最大值）
CSNode<T> *p;
p = root;
int dep, max = TreeDepth(p);
if (p != NULL)
p = p->nextsibling;
while(p != NULL)
{
dep = TreeDepth(p);
if (dep > max)
max = dep;
p = p->nextsibling;
}
return max;
}
CSNode<T>* Point(T s)const
{//返回树或森林中指向元素值为 s 的结点的指针
CSNode<T> *p;
queue<CSNode<T>*> q;
if (root)
{
q.push(root);
while(!q.empty())
{
p = q.front();
q.pop();
if (p->data == s)
return p;
if (p->firstchild)
q.push(p->firstchild);
if (p->nextsibling)
q.push(p->nextsibling);
}
}
return NULL;
}
T Value(CSNode<T> *p)const
{//返回 p 所指结点的值
if (p != NULL)
return p->data;
else
return Nil; //返回空结点
}
void PreOrderTraverse(void(*visit) (CSNode<T>*))const
{//先序遍历
PreOrderTraverse(root, visit);
}
void PostOrderTraverse(void(*visit) (CSNode<T>*))const
{//后序遍历
PostOrderTraverse(root, visit);
}
void LevelOrderTraverse(void(*visit) (CSNode<T>*))const
{//层序遍历
CSNode<T> *p = root;
queue<CSNode<T>*> q;
if (p != NULL)
{
while(p != NULL)
{
visit(p);
q.push(p);
p = p->nextsibling;
}
while(!q.empty())
{
p = q.front();
q.pop();
if (p->firstchild)
{
p = p->firstchild;
visit(p);
q.push(p);
while(p->nextsibling)
{
p = p_>nextsibling;
visit(p);
q.push(p);
}
}
}
}
}
CSNode<T>* Root()const
{//返回根结点指针
return root;
}
void Assign(CSNode<T>* p, T value)const
{//给 p 所指结点赋值为 value
if (p != NULL)
p->data = value;
}
T Parent(T e)const
{//返回 e 的双亲的值，否则 Nil
CSNode<T> *t, *p = root;
queue<CSNode<T>*> q;
if (p != NULL)
{
while(p != NULL)
if (Value(p) == e) //e 为树的根结点
return Nil;
else
{
q.push(p);
p = p->nextsibling;
}
while(!q.empty())
{
p = q.front();
q.pop();
if (p->firstchild)
{
if (p->firstchild->data == e)
return p->data;
t = p;
p = p->firstchild;
q.push(p);
while(p->nextsibling)
{
p = p->nextsibling;
if (p->data == e)
return t->data;
q.push(p);
}
}
}
}
return Nil;
}
T LeftChild(T e)const
{//返回值为 e 的结点的左孩子的值
CSNode<T> *f = Point(e);
if (f && f->firstchild)
return f->firstchild->data;
else
return Nil;
}
T RightSibling(T e)const
{//返回值为 e 的结点的右兄弟的值
CSNode<T> *f = Point(e);
if (f && f->nextsibling)
return f->nextsibling->data;
else
return Nil;
}
bool InsertChild(CSNode<T> *p, int i, CSTree<T> &c)const
{//插入非空树 c 为树中 p 结点的第 i 棵子树
int j;
CSNode<T> *q, *s = c.Root();
c.root = NULL;
if (root != NULL)
{
if (i == 1) //插入 s 为 p 的长子
{
s->nextsibling = p->firstchild;
p->firstchild = s;
}
else //s 不作为 p 的长子
{
q = p->firstchild;
j = 2;
while(q && j < i)
{
q = q->nextsibling;
j++;
}
if (j == i) //找到插入位置
{
s->nextsibling = q->nextsibling;
q->nextsibling = s;
}
else
return false;
}
return true;
}
else //树空
return false;
}
bool DeleteChild(CSNode<T> *p, int i)
{//删除树中 p 所指结点的第 i 棵子树
CSNode<T> *b, *q;
int j;
if (i == 1) //删除长子
{
b = p->firstchild;
p->firstchild = b->nextsibling;
b->nextsibling = NULL;
ClearTree(b);
}
else //删除非长子
{
q = p->firstchild;
j = 2;
while(q && j < i)
{
q = q->nextsibling;
j++;
}
if (j == i) //找到第 i 棵子树
{
b = q->nextsibling;
q->nextsibling = b->nextsibling;
b->nextsibling = NULL;
ClearTree(b);
}
else //p 没有孩子
return false;
}
return true;
}
};
10. 赫夫曼树和赫夫曼编码
赫夫曼树又称为最优二叉树。它是带权路径长度最短的二叉树。根据结点的个数、权值的不同，最优二叉树的形状也各不相同。特点是：带权值的结点都是叶子结点；权值越小的结点，其到根结点的路径越长。
构造最优二叉树的方法如下：
- 将每个带有权值的结点作为一棵仅有根结点的二叉树，树的权值为结点的权值；
- 将其中两颗权值最小的树组成一棵新的二叉树，新树的权值为两棵树的权值之和；
- 重复第二步，直到所有结点都在一棵二叉树上，这棵二叉树就是最优二叉树。
最优二叉树的左右子树是可以互换的，因为这不影响树的带权值路径长度。当结点的权值差别大到一定程度，最优二叉树就形成了 “一边倒” 的形状；而当权值差别很小的时候，最优二叉树就形成了接近满二叉树的形状，叶子结点的路径长度近似相等。
最优二叉树除了叶子结点就是度为 2 的结点，没有度为 1 的结点，也称为 “真二叉树” 。这样才使得树的带权路径长度最短。
//赫夫曼树结点类型结构体
template<typename T>struct HTNode
{
T weight; //权值
int parent, lchild, rchild; //结点的双亲，左右孩子静态指针
};
这次将使用静态三叉链表二叉树结构建立赫夫曼树，因为它特别适合建立赫夫曼树。赫夫曼树是由最初多棵单结点二叉树（森林）组合而成的一棵二叉树。这种二叉树结构既适合表示树，也适合表示森林。赫夫曼树结点包括权值、双亲及左右孩子静态指针。设置根结点的双亲值和叶子结点的左右孩子值均为 -1 。这种二叉树结构是动态生成的顺序结构。当叶子结点树确定，赫夫曼树的结点树也就确定了。可以按需动态生成数组，因此不需要建立备用链表。
实现：
//赫夫曼树类
template<typename T>class HuffmanTree
{//带模板的赫夫曼树类
private:
HTNode<T> *HT; //基址
T Sum; //权值总和
int N; //叶子结点数
int min(int i)const
{//返回赫夫曼树的前 i 个结点中权值最小的树的根结点的序号，并给选中的根结点的双亲
//赋非负值
int j, m;
T k = Sum;
for(j = 0; j < i; j++)
if (HT[j].weight < k && HT[j].parent < 0) //HT[j]的权值小于k，又是根结点
{
k = HT[j].weight;
m = j;
}
HT[m].parent = i;
return m;
}
void CreateHT(char *FileName)
{//根据文件建立赫夫曼树
int m, i, s1, s2;
ifstream fin(FileName);
fin >> N;
if (N <= 1)
return;
m = 2 * N - 1;
HT = new HTNode<T>[m];
assert(HT != NULL);
Sum = 0; //初值
for(i = 0; i < N; ++i) //给叶子结点赋值
{
fin >> HT[i].weight;
Sum += HT.weight;
HT[i].parent = -1; //-1 表示空
HT[i].lchild = -1;
HT[i].rchild = -1;
}
fin.close();
for(i = N; i < m; ++i) //非叶子结点
HT[i].parent = -1;
for(i = N; i < m; ++i) //建立建立赫夫曼树
{//在 HT[0 ~ i-1] 中选择 parent 为 -1 且 weight 最小的两个结点
s1 = min(i);
s2 = min(i);
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
void HuffmanCodingLeaf()const
{//从叶子到根逆向求赫夫曼编码 HC
int i, p, c;
string *HC = new string[N];
assert(HC != NULL);
cout << "从叶子到根逆向求得的赫夫曼编码为：" << endl;
for(i = 0; i < N; i++)
{
for(c = i, p = HT[i].parent; p >= 0; c = p, p = HT[p].parent)
if (c == HT[p].lchild)
HC[i] = '0' + HC[i]; //将 '0' 加在串前
else
HC[i] = '1' + HC[i]; //将 '1' 加在串前
cout << HC[i] << endl;
}
delete[] HC;
}
void HuffmanCodingRoot()const
{//无栈非递归从根到叶子求赫夫曼编码 HC
string str = "", *HC = new string[N];
assert(HC != NULL);
int c = 2 * N - 2;
for(int i = 0; i <= c; ++i)
HT[i].weight = 0; //权值域改作结点状态标志，0 表示其左右孩子都不曾被访问
while(c >= 0)
{
if (HT[c].weight == 0)
{//向左
HT[c].weight = 1;
if (HT[c].lchild != -1) //有左孩子
{
c = HT[c].lchild;
str = str + '0'; //左分支编码为 0
}
else //c 为叶子结点
{
HC[c] = str;
c = HT[c].parent;
str = str.substr(0, str.length() - 1); //退到父结点，编码长度减 1
}
}
else if (HT[c].weight == 1) //左孩子被访问过，右孩子不曾被访问
{//向右
HT[c].weight = 2;
c = HT[c].rchild;
str = str + '1'; //右分支编码为 1
}
else //左右孩子均被访问过，向根结点退一步
{
c = HT[c].parent;
str = str.substr(0, str.length() - 1); //退到父结点，编码长度减 1
}
}
for(i = 0; i < N; i++)
cout << HC[i] << endl; //依次输出赫夫曼编码
delete[] HC;
}
public:
HuffmanTree()
{//构造函数
HT = NULL; //树空
}
void HuffmanCoding(char *FileName)
{//建立赫夫曼树并用两种方法求赫夫曼编码 HC ，然后销毁赫夫曼树
CreateHT(FileName);
HuffmanCodingLeaf(); //从叶子到根逆向求赫夫曼编码 HC
HuffmanCodingRoot(); //无栈非递归从根到叶子求赫夫曼编码 HC
delete[] HT;
}
};
