树、二叉树、三叉树、平衡排序二叉树AVL
一、树的定义
树是计算机算法最重要的非线性结构。树中每个数据元素至多有一个直接前驱，但可以有多个直接后继。树是一种以分支关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。{N.沃恩}
(树是n(n≥1)个结点组成的有限集合。{D.E.Knuth})
在任意一棵非空树中：
⑴有且仅有一个没有前驱的结点----根(root)。
⑵当n>1时，其余结点有且仅有一个直接前驱。
⑶所有结点都可以有0个或多个后继。
b. 树是n(n≥0)个结点组成的有限集合。
在任意一棵非空树中：
⑴有一个特定的称为根（root）的结点。
⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的子集T1，T2，…，Tm。 每个集合本身又是一棵树，并且称为根的子树（subtree）
树的固有特性---递归性。即非空树是由若干棵子树组成，而子树又可以由若干棵更小的子树组成。
树的基本操作
1、InitTree(&T) 初始化
2、DestroyTree(&T) 撤消树
3、CreatTree(&T,F) 按F的定义生成树
4、ClearTree(&T) 清除
5、TreeEmpty(T) 判树空
6、TreeDepth(T) 求树的深度
7、Root(T) 返回根结点
8、Parent(T,x) 返回结点 x 的双亲
9、Child(T,x,i) 返回结点 x 的第i 个孩子
10、InsertChild(&T,&p,i,x) 把 x 插入到 P的第i棵子树处
11、DeleteChild(&T,&p,i) 删除结点P的第i棵子树
12、traverse(T) 遍历
树的结点：包含一个数据元素及若干指向子树的分支。
●结点的度: 结点拥有子树的数目
●叶结点: 度为零的结点
●分枝结点: 度非零的结点
●树的度: 树中各结点度的最大值
●孩子: 树中某个结点的子树的根
●双亲: 结点的直接前驱
●兄弟: 同一双亲的孩子互称兄弟
●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。
●子孙: 某结点的子树中的任一结点称为该结点的子孙
●结点层次: 从根结点到某结点 j 路径上结点的数目（包括结点j）
●树的深度: 树中结点的最大层次
●有向树：结点间的连线是有向的。我们所讲的树都是有向的。
●有序树: 若树中结点的各子树从左到右是有次序的,称该树为有序树,否则为无序树
●森林: 由 m 棵互不相交的树构成 F=(T1,T2,.......Tm)
一棵树去掉根结点后就变成了森林。
二叉树的性质
二叉树的第i层结点数最多为2^(i-1)个(i>0)。
深度为K的二叉树至多有(2^k)-1个结点(K>0)。
对任何一棵二叉树，设n0,n1,n2分别是度为0,1,2的结点数，则有：n0＝n2+1
证明:
∵ n= n0+ n1 + n2 (n为结点总数)
b= n1 +2 n2 (b 为分支总数)
b=n-1 (除根结点外,任一结点都有分支连入父结点)
∴ n=b+1= n1 +2 n2 +1= n0+ n1 + n2
整理得: n0 = n2 +1
具有n个结点的完全二叉树高度为
具有n个结点的完全二叉树具有如下特征：
① i=1 根结点，无双亲
i>1 其双亲结点为 (PARENT(i)= 
)
② 2i>n 结点i无左孩，否则 lchild(i)=2i
③ 2i+1>n 结点i无右孩，否则 rchild(i)=2i+1
二、二叉树三序遍历
2.1．实验内容
1.用先序递归遍历法建二叉树
2.输出三序递归遍历与层次遍历节点访问次序,三序遍历要求使用非递归和递归两种！！！！！！
3.用先序，中序遍历序列建二叉树
4.后序遍历复制一棵二叉树,计算叶子个数和树的深度！！！！
5.输出后序递归遍历及层次遍历结果
2.2.输入与输出
输入：输入建立二叉树的先序序列并且带‘#’，用以建树
输出 ：输出四种遍历的序列和用先序中序序列建成的二叉树
2.3．关键数据结构与算法描述
关键数据结构：二叉树的结构，节点，左孩子右孩子；栈的数据结构用以采用非递归方式遍历二叉树，循环队列的数据结构用以层次遍历二叉树。
具体代码如下：
typedef struct TreeNode
{
ElemType elem;
struct TreeNode *LChild,*RChild;
}BiTree,*BinaryTree; //二叉树数据结构
typedef struct Queue
{
BinaryTree value[MAXSIZE];
int front,rear;
}LinkQueue; //队列数据结构
typedef BinaryTree ElemType1; //为BinaryTree起别名
typedef struct Stack
{
ElemType1 StackElem[MAXSIZE];
int top;
}STACK; //栈的数据结构
算法描述：用递归方法进行先序，中序，后序遍历都十分方便与简单，因为利用了树的左右结构。若树空时什么也不做，否则，按照便利的次序依次递归访问即可，如先序遍历：
//先序递归遍历
void PreOrderTraverse(BinaryTree tree)
{
if(tree!=NULL)
{
visit(tree);
PreOrderTraverse(tree->LChild);
PreOrderTraverse(tree->RChild);
}
}
而对于非递归的三序遍历，就需要栈来做数据结构了，对于前序，中序遍历来说，只需要从根节点开始，一直往左走，直至最左边左子树为空，并且在这个过程中，若是先序遍历对于路上的节点都要访问并且入栈直至访问到到最左边的节点，然后退栈访问退栈节点的右子树；若是中序遍历则只需不断的向左走并且入栈但不访问，直至最左边，然后访问最左边节点。然后退栈并访问该节点，用同样的方法访问退栈节点的右子树。最后若栈为空，则访问完成。故此设立一个一直向左走访问并且入栈的函数如下（中序与此类似，暂不赘述）：
/***一直向左走直至获得最左边的指针*************/
BinaryTree GofarleftVisit(BinaryTree tree,STACK *s)
{
if(!tree)
return NULL; //若无树直接返回
BinaryTree p=tree;
visit(p); //先访问逻辑根节点
while(p->LChild)
{
push(s,p); //把访问之后的入栈以便访问右子树
visit(p->LChild); //访问左子树
p=p->LChild; //不断向左移动直至为空
}
return p;
}
非递归先序遍历的算法为：
//用非递归法先序访问
void PreOrder(BinaryTree tree)
{
if(!tree)
return ;
STACK s;
InitStack(&s);
BinaryTree p;
p=GofarleftVisit(tree,&s); //获得最左指针
while(p)
{
if(p->RChild)
p=GofarleftVisit(p->RChild,&s); //右边继续向左走
else
if(!IsEmptyStack(&s))
{
pop(&s,p);
}
else
p=NULL; //栈空时退出
}
}
对于非递归后序遍历，根据其特点，先遍历左子树再遍历右子树，最后访问根节点。则需用两个指针cur和pre来分别标记当前指针和前一个指针的位置。注意压栈时先压根节点，再压右子树，最后左子树。若当前指针cur指向叶子节点则需访问，或者pre指针不为空并且pre指向的节点恰是当前指针指向的左或右节点则代表pre子树的下一层已经无树，并且若等于左指针则右边已无节点，（右边若有则访问完左边之后必然先访问右边而不会跳到头节点）；若等于右节点，则左边已访问完或无左边（因右边先压栈）。具体代码如下：
//非递归后序遍历
void postOrder(BinaryTree tree)
{
STACK s;
InitStack(&s);
BinaryTree cur,pre=;
push(&s,tree);
/*****用两个指针来判断，如果为叶子节点或者左右子树都访问过就访问该节点****/
while(!IsEmptyStack(&s))
{
cur=gettop(&s);
if((cur->LChild==NULL&&cur->RChild==NULL)||
(pre!=NULL&&(pre==cur->RChild||pre==cur->LChild)))
{ //注意pre只要与一个相等，若为左子树则无右子树；
//若为右子树则必然访问过左子树或无左子树
visit(cur); //如果当前结点为叶子节点或者孩子节点都已被访问就访问
pop(&s,cur);
pre=cur; //标记上次被访问的节点
}
else
{
if(cur->RChild!=NULL)
push(&s,cur->RChild); //注意先把右子树入栈再入左子树，才能保持先访问左子树后访问右子树，后进先出！
if(cur->LChild!=NULL)
push(&s,cur->LChild);
}
}
}
接下来是用队列数据结构层次遍历。其实就是迭代的过程，先访问头节点，然后进左儿子，右儿子。每次出队列后都要访问该节点，然后再看该节点是否有左右子树若有则按照先左后右的顺序进队排在队尾等待遍历然后不断地循环迭代直至队为空则遍历结束。很容易理解！
具体代码如下：
//队列进行的二叉树层次遍历
void HierarchyBiTree(BinaryTree tree)
{
LinkQueue Q; //注意此处不能是指针
InitQueue(&Q);
BinaryTree p=tree;
if (tree==NULL)
return ;
visit(p);
if (p->LChild)
EnQueue(&Q,&p->LChild); //若指针不空则入队列
if (p->RChild)
EnQueue(&Q, &p->RChild); //若指针不空则入队列
while (!IsEmpty(&Q))
{
DeQueue(&Q, &p); //弹出指针进行访问
visit(p);
if (p->LChild)
EnQueue(&Q, &p->LChild); //对指针所指的结构进行判断若左右子树不空
if (p->RChild)
EnQueue(&Q, &p->RChild); //则先进左子树，后进右子树，以保证从左到右遍历
}
}
然后关于二叉树的复制，先复制左子树，然后复制右子树，最后复制头节点；在复制左右子树的时候同时也是复制树，故可用递归实现。同理，关于求叶子节点，求树的深度也是如此用递归即可实现，复制树的具体代码如下：
/************后序遍历复制一棵二叉树*************/
void CopyBiTree(BinaryTree tree,BinaryTree &newtree)
{
BinaryTree lchild,rchild;
if(!tree)
{
newtree=NULL;
}
if(tree->LChild)//若左子树存在则递归复制
{
CopyBiTree(tree->LChild,lchild);
}
else
{
lchild=NULL; //否则为零
}
if(tree->RChild)
{
CopyBiTree(tree->RChild,rchild);
}
else
{
rchild=NULL;
}
newtree=(BinaryTree)malloc(sizeof(BiTree));
newtree->elem=tree->elem;
newtree->LChild=lchild;
newtree->RChild=rchild;
}
最后就是根据先序和中序序列建树，有一定的难度需要用到递归和分治法的一些知识。首先可以证明用先序，中序遍历序列是可以还原二叉树的，因为根据先序序列可以很清楚的知道二叉树的根节点就是第一个元素，然后以这个节点把中序序列分成两半，在这个节点左边的必是左子树（因为是中序序列），而在其右边的是右子树，而左子树右子树有是一个树，故可以在更小的范围内找到左子树的根节点，在以该节点为分界点，在更小的范围内查找下去，右子树也是如此。在递归的过程中要注意进行比较的两个序列长度必然要相等，递归终止的条件就是左边分到不能再比，右边也向右不能再比为止。这样也就在递归中建立了二叉树。具体代码如下：
//首先得到中序序列二分后左边的长度
int get_left_len(int rootpos,int in_begin,int in_end,char * pre_order,char * in_order )
{
for(int i = in_begin; i <= in_end; i++)
{
if(in_order[i] == pre_order[rootpos])
{
return i-in_begin; //以双亲节点为分界点划分，返回左边的真实长度
}
}
return -; //若没有则返回负值，用于判断
} void creat(BinaryTree *pnode,int pre_begin,int pre_end,int in_begin,int in_end,
char * pre_order,char * in_order)
{
*pnode =(BinaryTree)malloc(sizeof(BiTree)); //申请空间
BinaryTree temp = *pnode; //创建遍历指针
temp->elem = pre_order[pre_begin]; //开始必为根节点
temp->LChild = NULL; //一定要初始化为0
temp->RChild = NULL;
if(pre_begin == pre_end)
{
return ; //只有一个节点，则已创建完毕
}
int left_len = get_left_len(pre_begin,in_begin,in_end,pre_order,in_order);
if(left_len > ) //若没有会返回-1；若为0，则上面已创建；否则创建左子树
{
creat(&temp->LChild,pre_begin+,pre_begin+left_len,
in_begin,in_begin+left_len-,pre_order,in_order);
}
if(left_len < (in_end - in_begin)) //若left_len+inbegin>in_end-1则已经结束，否则创建右子树
{
creat(&temp->RChild,pre_begin+left_len+,pre_end,
in_begin+left_len+,in_end,pre_order,in_order);
}
}
2.4.测试与理论
具体的测试与理论见下图
测试数据一：
先序遍历：ABDFCEG
中序遍历：DFBAECG
后序遍历：FDBEGCA
输入数据: ABD#F###CE##G##
对于测试先序和中序序列建树的序列为
char * pre_order = "ABDEGJCFHIK";//先序序列
char * in_order = "DBGJEACFIKH"; //中序序列
输出结果截图：
测试数据二：
先序遍历：ABDEGJCFHIK
中序遍历：DBGJEACFIKH
后序遍历：DJGEBKIHFCA
输入序列：ABD##EG#J###C#F#HI#K###
输出结果见下图：
2.5.附录
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXSIZE 100
#define OK 1
#define NO 0
/**********************************************/
typedef int status;
typedef char ElemType;
typedef struct TreeNode
{
ElemType elem;
struct TreeNode *LChild,*RChild;
}BiTree,*BinaryTree; //二叉树数据结构
typedef struct Queue
{
BinaryTree value[MAXSIZE];
int front,rear;
}LinkQueue; //队列数据结构
typedef BinaryTree ElemType1; //为BinaryTree起别名
typedef struct Stack
{
ElemType1 StackElem[MAXSIZE];
int top;
}STACK; //栈的数据结构
/************************************************/
/*************以下是循环队列的定义**************/
void InitQueue( LinkQueue *q)
{
q->front=-; //注意初始化为-1
q->rear=-;
}
status IsEmpty(LinkQueue *q)
{
if(q->rear==q->front)
return OK; //循环队列开始为空或者运行时出队的光标指到入队的光标
else
return NO;
}
status IsFull(LinkQueue *q)
{
if(q->front==(q->rear+)%MAXSIZE)
return OK; //队满的标志就是q->front指向哑元且哑元左边为q->rear
else
return NO;
}
void EnQueue(LinkQueue *q, BinaryTree *tree)
{
if(IsFull(q))
return ; //入队操作，若队满则不能入队
q->rear=(++(q->rear))%MAXSIZE; //注意一定要先自加，再赋值
q->value[q->rear]=*tree;
}
void DeQueue(LinkQueue *q, BinaryTree *tree)
{
if(IsEmpty(q))
return ;
q->front=(++q->front)%MAXSIZE;
*tree=q->value[q->front]; //注意tree是指向指针的指针，不然将出错
}
/**************************************************************/
/******************以下是栈的定义******************************/
void InitStack(STACK *s)
{
s->top=-; //初始化
}
void push(STACK *s,ElemType1 e)
{
if(s->top>=MAXSIZE-)
return ;
s->StackElem[++s->top]=e; //压栈
}
void pop(STACK *s,ElemType1 &e)
{
if(s->top<=-)
return ;
e=s->StackElem[s->top]; //出栈
s->top--;
}
ElemType1 gettop(STACK *s)
{
return s->StackElem[s->top]; //获得栈顶元素
}
status IsEmptyStack(STACK *s) //判断是否栈空
{
if(s->top==-)
return OK;
else
return NO;
}
/******************************************************************/
/***************递归创建二叉树，要求读入先序序列和‘#’****************/
BinaryTree CreatTree(BinaryTree tree)
{
char ch;
if((ch=getchar())=='#')
tree=NULL;
else
{
tree=(BinaryTree)malloc(sizeof(BiTree));
tree->elem=ch;
tree->LChild=CreatTree(tree->LChild);
tree->RChild=CreatTree(tree->RChild);
}
return tree;
}
//最简单的访问二叉树
void visit(BinaryTree tree)
{
printf("%c ",tree->elem);
}
/**************以下是四种对二叉树的遍历方法***********************/
//先序递归遍历
void PreOrderTraverse(BinaryTree tree)
{
if(tree!=NULL)
{
visit(tree);
PreOrderTraverse(tree->LChild);
PreOrderTraverse(tree->RChild);
}
} /***一直向左走直至获得最左边的指针*************/
BinaryTree GofarleftVisit(BinaryTree tree,STACK *s)
{
if(!tree)
return NULL; //若无树直接返回
BinaryTree p=tree;
visit(p); //先访问逻辑根节点
while(p->LChild)
{
push(s,p); //把访问之后的入栈以便访问右子树
visit(p->LChild); //访问左子树
p=p->LChild; //不断向左移动直至为空
}
return p;
}
//用非递归法先序访问
void PreOrder(BinaryTree tree)
{
if(!tree)
return ;
STACK s;
InitStack(&s);
BinaryTree p;
p=GofarleftVisit(tree,&s); //获得最左指针
while(p)
{
if(p->RChild)
p=GofarleftVisit(p->RChild,&s); //右边继续向左走
else
if(!IsEmptyStack(&s))
{
pop(&s,p);
}
else
p=NULL; //栈空时退出
}
} //中序递归遍历
void InOrderTraverse(BinaryTree tree)
{
if(tree!=NULL)
{
InOrderTraverse(tree->LChild);
visit(tree);
InOrderTraverse(tree->RChild);
}
}
//中序非递归遍历二叉树
BinaryTree gofarleft(BinaryTree tree,STACK *s)
{
if(!tree)
return NULL;
BinaryTree p=tree;
while(p->LChild) //一直向左走，不断入栈
{
push(s,p);
p=p->LChild;
}
return p;
}
void InOrder(BinaryTree tree)
{
if(!tree)
return ;
STACK s;
InitStack(&s);
BinaryTree p;
p=gofarleft(tree,&s);
while(p)
{
visit(p); //先访问最左元素
if(p->RChild)
p=gofarleft(p->RChild,&s);
else
if(!IsEmptyStack(&s))
{
pop(&s,p); //向上追溯
}
else
p=NULL; //栈空时恰访问完
}
}
/************************************/ //后序递归遍历
void PostOrderTraverse(BinaryTree tree)
{
if(tree!=NULL)
{
PostOrderTraverse(tree->LChild);
PostOrderTraverse(tree->RChild);
visit(tree);
}
}
//非递归后序遍历
void postOrder(BinaryTree tree)
{
STACK s;
InitStack(&s);
BinaryTree cur,pre=;
push(&s,tree);
/*****用两个指针来判断，如果为叶子节点或者左右子树都访问过就访问该节点****/
while(!IsEmptyStack(&s))
{
cur=gettop(&s);
if((cur->LChild==NULL&&cur->RChild==NULL)||
(pre!=NULL&&(pre==cur->RChild||pre==cur->LChild)))
{ //注意pre只要与一个相等，若为左子树则无右子树；
//若为右子树则必然访问过左子树或无左子树
visit(cur); //如果当前结点为叶子节点或者孩子节点都已被访问就访问
pop(&s,cur);
pre=cur; //标记上次被访问的节点
}
else
{
if(cur->RChild!=NULL)
push(&s,cur->RChild); //注意先把右子树入栈再入左子树，才能保持先访问左子树后访问右子树
if(cur->LChild!=NULL)
push(&s,cur->LChild);
}
}
}
/******************************************************/
//队列进行的二叉树层次遍历
void HierarchyBiTree(BinaryTree tree)
{
LinkQueue Q; //注意此处不能是指针
InitQueue(&Q);
BinaryTree p=tree;
if (tree==NULL)
return ;
visit(p);
if (p->LChild)
EnQueue(&Q,&p->LChild); //若指针不空则入队列
if (p->RChild)
EnQueue(&Q, &p->RChild); //若指针不空则入队列
while (!IsEmpty(&Q))
{
DeQueue(&Q, &p); //弹出指针进行访问
visit(p);
if (p->LChild)
EnQueue(&Q, &p->LChild); //对指针所指的结构进行判断若左右子树不空
if (p->RChild)
EnQueue(&Q, &p->RChild); //则先进左子树，后进右子树，以保证从左到右遍历
}
}
/***************************************************/
/********计算叶子节点数*************/
void CountLeaf(BinaryTree tree,int &count)
{
if(tree)
{
if((tree->LChild==NULL)&&(tree->RChild==NULL))
count++;
CountLeaf(tree->LChild,count);
CountLeaf(tree->RChild,count);
}
}
/************计算树的深度**************/
int TreeDepth(BinaryTree tree)
{
int depth,ldepth,rdepth;
if(!tree)
depth=;
else
{
ldepth=TreeDepth(tree->LChild);
rdepth=TreeDepth(tree->RChild);
depth=(ldepth>rdepth ? ldepth:rdepth)+;
}
return depth;
}
/************后序遍历复制一棵二叉树*************/
void CopyBiTree(BinaryTree tree,BinaryTree &newtree)
{
BinaryTree lchild,rchild;
if(!tree)
{
newtree=NULL;
}
if(tree->LChild)//若左子树存在则递归复制
{
CopyBiTree(tree->LChild,lchild);
}
else
{
lchild=NULL; //否则为零
}
if(tree->RChild)
{
CopyBiTree(tree->RChild,rchild);
}
else
{
rchild=NULL;
}
newtree=(BinaryTree)malloc(sizeof(BiTree));
newtree->elem=tree->elem;
newtree->LChild=lchild;
newtree->RChild=rchild;
}
/*****************************************************/
/*************根据先序和中序序列建二叉树*******************/
//首先得到中序序列二分后左边的长度
int get_left_len(int rootpos,int in_begin,int in_end,char * pre_order,char * in_order )
{
for(int i = in_begin; i <= in_end; i++)
{
if(in_order[i] == pre_order[rootpos])
{
return i-in_begin; //以双亲节点为分界点划分，返回左边的真实长度
}
}
return -; //若没有则返回负值，用于判断
} void creat(BinaryTree *pnode,int pre_begin,int pre_end,int in_begin,int in_end,
char * pre_order,char * in_order)
{
*pnode =(BinaryTree)malloc(sizeof(BiTree)); //申请空间
BinaryTree temp = *pnode; //创建遍历指针
temp->elem = pre_order[pre_begin]; //开始必为根节点
temp->LChild = NULL; //一定要初始化为0
temp->RChild = NULL;
if(pre_begin == pre_end)
{
return ; //只有一个节点，则已创建完毕
}
int left_len = get_left_len(pre_begin,in_begin,in_end,pre_order,in_order);
if(left_len > ) //若没有会返回-1；若为0，则已创建；否则创建左子树
{
creat(&temp->LChild,pre_begin+,pre_begin+left_len,
in_begin,in_begin+left_len-,pre_order,in_order);
}
if(left_len < (in_end - in_begin)) //若left_len+inbegin>in_end-1则已经结束，否则创建右子树
{
creat(&temp->RChild,pre_begin+left_len+,pre_end,
in_begin+left_len+,in_end,pre_order,in_order);
}
}
/*********************************************************/
void MainMenu( )
{
BinaryTree tree=,newtree;
int count=,depth;
/**********display***********/
tree=CreatTree(tree);
printf("前序遍历：\n");
PreOrderTraverse(tree);
printf("\n中序遍历：\n");
InOrderTraverse(tree);
printf("\n后序遍历：\n");
PostOrderTraverse(tree);
printf("\n层次遍历二叉树:\n");
HierarchyBiTree(tree);
printf("\n非递归先序遍历\n");
PreOrder(tree);
printf("\n非递归中序遍历\n");
InOrder(tree);
printf("\n非递归后序遍历\n");
postOrder(tree);
/********algorithm************/
CountLeaf(tree,count);
printf("\n叶子个数为:%d\n",count);
depth=TreeDepth(tree);
printf("\n树的深度为：%d\n",depth);
printf("\n复制二叉树后的结果：\n");
CopyBiTree(tree,newtree);
printf("\n先序遍历：\n");
PreOrderTraverse(newtree);
printf("\n中序遍历：\n");
InOrderTraverse(newtree);
printf("\n后序遍历：\n");
PostOrderTraverse(newtree);
printf("\n层次遍历二叉树:\n");
HierarchyBiTree(newtree);
/*********用先序和中序建树并输出*************/
char * pre_order = "ABDEGJCFHIK";//先序序列
char * in_order = "DBGJEACFIKH"; //中序序列
BinaryTree root = NULL;
creat(&root,,strlen(pre_order)-,,strlen(in_order)-,pre_order,in_order);
printf("用先序和中序建树后的结果：\n");
printf("\n后序遍历：\n");
PostOrderTraverse(root);
printf("\n层次遍历二叉树:\n");
HierarchyBiTree(root);
printf("\n操作结束\n");
} /* 测试数据 ABD#F###CE##G## */
/* 测试数据 ABD##EG#J###C#F#HI#K### */
int main()
{
MainMenu();
return ;
}
三、三叉树——带双亲指针的二叉树非递归遍历
3.1．实验内容
建立三叉链表存储结构，实现三序非递归遍历。
3.2．输入与输出
输入：带有“#”的二叉树字符串。
输出：三序遍历的结果。
3.3．关键数据结构与算法描述
关键数据结构：
三叉链表的数据结构如下：
typedef char ElemType;
typedef struct TriTree
{
ElemType elem;
struct TriTree *lchild,*rchild,*parent;
}*TRITREE,TriTreeNode;
算法描述：
三叉链表的创建和二叉树创建基本相同，只不过增加了双亲指针就要给其赋值，根节点的双亲为NULL,其他节点在先序递归遍历建二叉树的时候赋值，若该节点有左右子树，则左右节点的双亲指针就指向该节点。具体代码为：
if(tree->lchild)
{
tree->lchild->parent=tree;//指向双亲节点
}
if(tree->rchild)
{
tree->rchild->parent=tree;//指向双亲节点
}
然后是三序遍历，1.首先是先序非递归遍历，先遍历头节点，再遍历左子树，然后是右子树，注意到从此处的双亲指针的用法，可以回溯。因此，当树不为空的时候，首先遍历该节点，然后看是否有左子树，若有则指向左子树，若无左子树，则看是否有右子树，若有则指向右子树。如果左右子树都不存在，则是叶子节点需要回溯。选定一个“记录指针p”，永远指向遍历指针刚刚走过的位置。而遍历指针则回溯。若遍历指针的左儿子为p，并且右儿子不空则遍历右子树；若回溯到根节点的双亲则结束。否则继续回溯。直至两种情况出现一种。一直循环就可实现先序遍历。代码如下：
//非递归先序遍历三叉链表
void preorder(TRITREE tree)
{
TRITREE p;
while(tree) //有树就循环
{
visit(tree); //访问根节点
if(tree->lchild)
{
tree=tree->lchild ; //一定要先看左子树再看右子树
}
else if(tree->rchild )
{
tree=tree->rchild ; //进入下一循环
}
else
while()
{
p=tree;
tree=tree->parent;//形成连接结构
if(!tree)
break; //若无树则退出
if(tree->lchild == p&&tree->rchild )
{
tree=tree->rchild ; //访问完左子树，访问右子树
break;
} }
}
}
2.中序遍历思想是先遍历左子树再遍历头节点，最后遍历右子树。因回溯时有左子树和右子树两种情况，则用一个标量来记录mark=0代表未遍历左子树，mark=1代表已遍历左子树。则当树不空时开始循环，mark开始置为零。要是没遍历左子树则要先遍历左子树。左子树遍历之后mark置为一。然后看以该节点为根的右子树是否存在若存在则遍历，若不存在则回溯，同样设p跟随遍历节点，若是左边回溯则遍历该节点，若是右边回溯则继续向上推进，若推进到最上面则遍历结束。具体代码如下：
//非递归中序遍历三叉链表
void inorder(TRITREE tree)
{
TRITREE p;
int mark=;//表示左子树未遍历
while(tree)
{
if(mark==)
{
if(tree->lchild)
{
tree=tree->lchild;//一直到最左边的节点
}
else
{
mark=; //然后标记左边已遍历，其实在下面遍历
}
}
else
{
visit(tree); //遍历标记节点
if(tree->rchild)
{
tree=tree->rchild;//若有右子树，则移位
mark=; //标记未遍历，回到上步
}
else
{ //若无右子树，则回溯
while()
{
p=tree;
tree=tree->parent;
if(!tree)
break;
if(tree->lchild == p)
{
mark=;//表示左孩子遍历过
break;
}
} }
}
}
}
3.后序遍历需要设定一个标量flag分别表示（0）：左子树未遍历（1）：左子树已遍历，该遍历右子树；（2）右子树已遍历，应遍历头节点。则开始flag=0；开始遍历遍历完左子树flag=1；开始遍历右子树，此时若右子树还是棵树则要flag=0；判断这棵树的左右子树情况直至右边也被遍历则要遍历头节点置flag=2；开始访问。访问完后要进行回溯，若是从左边过来的就要访问右边，若是从右边过来的则要访问该节点。一直循环就可得到结果，具体代码如下：
//非递归后序遍历三叉链表
void postorder(TRITREE tree)
{
int flag=;//标志变量可取0，1，2三种状态
TRITREE p;
while(tree)
{
switch(flag)
{
case ://左子树未遍历
if(tree->lchild)
tree=tree->lchild;
else
flag=;
break;
case ://右子树未遍历
if(tree->rchild)
{
tree=tree->rchild;
flag=; //右子树可能是一棵树，重新遍历树的左孩子
}
else
{
flag=; //没有右子树则开始遍历头节点
}
break;
case : //开始遍历头节点
visit(tree);
p=tree;
tree=tree->parent; //回溯判断
if(tree)
{
if(p==tree->lchild)
{
flag=;//左孩子已遍历，开始右子树
}
else
{
flag=;//右孩子已遍历，开始遍历头节点
}
}
break;
}
}
}
3.4.测试与理论
测试数据：
先序遍历：ABDFCEG
中序遍历：DFBAECG
后序遍历：FDBEGCA
输入数据: ABD#F###CE##G##
结果见下图显示:
3.5.附录
#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
typedef char ElemType;
typedef struct TriTree
{
ElemType elem;
struct TriTree *lchild,*rchild,*parent;
}*TRITREE,TriTreeNode; //先序遍历创建三叉链表
TRITREE CreatTree(TRITREE &tree)
{
char ch;
if((ch=getchar())=='#')
tree=NULL;
else
{
tree=(TRITREE)malloc(sizeof(TriTreeNode));
tree->elem=ch;
tree->lchild=CreatTree(tree->lchild);
tree->rchild=CreatTree(tree->rchild);
//增加parent指针，若无左右孩子则不用赋值
if(tree->lchild)
{
tree->lchild->parent=tree;//指向双亲节点
} if(tree->rchild)
{
tree->rchild->parent=tree;//指向双亲节点
}
}
return tree;
}
//最简单的访问二叉树
void visit(TRITREE tree)
{
printf("%c ",tree->elem); }
//非递归先序遍历三叉链表
void preorder(TRITREE tree)
{
TRITREE p;
while(tree) //有树就循环
{
visit(tree); //访问根节点
if(tree->lchild)
{
tree=tree->lchild ; //一定要先看左子树再看右子树
}
else if(tree->rchild )
{
tree=tree->rchild ; //进入下一循环
}
else
while()
{
p=tree;
tree=tree->parent;//形成连接结构
if(!tree)
break; //若无树则退出
if(tree->lchild == p&&tree->rchild )
{
tree=tree->rchild ; //访问完左子树，访问右子树
break;
} }
}
}
//非递归中序遍历三叉链表
void inorder(TRITREE tree)
{
TRITREE p;
int mark=;//表示左子树未遍历
while(tree)
{
if(mark==)
{
if(tree->lchild)
{
tree=tree->lchild;//一直到最左边的节点
}
else
{
mark=; //然后标记左边已遍历，其实在下面遍历
}
}
else
{
visit(tree); //遍历标记节点
if(tree->rchild)
{
tree=tree->rchild;//若有右子树，则移位
mark=; //标记未遍历，回到上步
}
else
{ //若无右子树，则回溯
while()
{
p=tree;
tree=tree->parent;
if(!tree)
break;
if(tree->lchild == p)
{
mark=;//表示左孩子遍历过
break;
}
} }
}
}
} //非递归后序遍历三叉链表
void postorder(TRITREE tree)
{
int flag=;//标志变量可取0，1，2三种状态
TRITREE p;
while(tree)
{
switch(flag)
{
case ://左子树未遍历
if(tree->lchild)
tree=tree->lchild;
else
flag=;
break;
case ://右子树未遍历
if(tree->rchild)
{
tree=tree->rchild;
flag=; //右子树可能是一棵树，重新遍历树的左孩子
}
else
{
flag=; //没有右子树则开始遍历头节点
}
break;
case : //开始遍历头节点
visit(tree);
p=tree;
tree=tree->parent; //回溯判断
if(tree)
{
if(p==tree->lchild)
{
flag=;//左孩子已遍历，开始右子树
}
else
{
flag=;//右孩子已遍历，开始遍历头节点
}
}
break;
}
}
} //abd#f###ce##g##
int main()
{
TRITREE tree; tree=CreatTree(tree);
tree->parent=;
cout<<endl<<"先序非递归遍历三叉树："<<endl;
preorder(tree);
cout<<endl<<"中序非递归遍历三叉树："<<endl;
inorder(tree);
cout<<endl<<"后序非递归遍历三叉树："<<endl;
postorder(tree);
cout<<endl;
return ;
}
四、平衡排序二叉树AVL
4.1．实验内容
建立排序平衡二叉树。
4.2．输入与输出
输入：输入一组节点，从而建立平衡排序二叉树。
输出：输出平衡二叉树的先序，中序遍历，以及每个节点的平衡因子，以便进行还原二叉树的形状，判断算法是否正确。
4.3．关键数据结构与核心算法
关键数据结构：
因为是二叉树，则要有基本的节点，左右孩子指针，因为要排序旋转，则要知道平衡因子，注意此处可以根据需要来添加双亲指针，因为运用了引用，则省去了此处。因此数据结构为：
typedef struct BSTNode
{
int data;//信息
int bf;//平衡因子
struct BSTNode *lchild,*rchild; //平衡树左右儿子指针
}BSTNode,*BSTree;//平衡二叉排序树结构的定义
核心算法：
建立平衡排序二叉树算是算法中比较复杂的一个了，但是找到核心之后，也就只是比较复杂一些罢了，多练习一下即可。那核心是什么呢？要回答这个问题，就要深刻理解“平衡”和“排序”两个词的含义。顾名思义，平衡二叉树加上排序二叉树即是所要建的树。1.平衡二叉树要求每一个节点的左子树深度减去右子树的深度的绝对值要小于1。2.排序二叉树要求按照中序遍历该二叉树得到从小到大排序的序列。因此在每插入一个结点的时候都要判断是否平衡，1.若平衡则按照排序二叉树的方法插入之，然后刷新平衡因子即可。2.重要是不平衡的时候就要从最接近的不平衡的地方旋转的让它平衡，这样继续下去，不断插入就可以得到排序平衡二叉树。
下面主要解释一下旋转方法：旋转共有4种方式，其实，最核心的只有两种基本操作即是L_Rotate( )和R_Rotate( )，分别是左旋和右旋。
对于LL型，即是最先出错的节点平衡因子是2，左儿子平衡因子是1，运用一次右旋操作再刷新平衡因子即可。根据镜像对称原则，RR型与此是对应的，如法炮制即可。
重要的并且复杂的是LR和RL操作，这两个操作也是镜像对称的只讲一个即可。就比如LR吧，最先出错的节点的平衡因子是2，该节点的左孩子的平衡因子是-1.则要对左孩子为根的子树进行左旋，然后对该最近节点进行右旋，刷新平衡因子即可。具体算法如下：
/**************************两个基本操作*****************************/
void L_Rotate(BSTree &p)
{
//对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点
//和R_Rotate()镜像对称
BSTree rc;
rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
void R_Rotate(BSTree &p)
{
//对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点
//注意此处引用的好处就是不用再出现双亲指针
BSTree lc;
lc=p->lchild; //指向B的位置
p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性
lc->rchild=p; //更改a的指针位置
p=lc; //lc变成新的a
}
/**********************四个旋转操作，每两个在一起*****************/
//包含LL和LR
void LeftBalance(BSTree &T)
{ //对已*T为根的二叉排序树做左平衡旋转处理
BSTree lc,rd;
lc = T->lchild; //lc调整左边
switch(lc->bf)
{
case LH://若是左边高则为LL型，只需旋转即可
T->bf = lc->bf = EH; //旋转后平衡因子均为0
R_Rotate(T); //LL型需要右旋转
break;
case RH://若是右边高，则为LR型，需分两步调整
rd = lc->rchild; //找到不确定因子rd
switch(rd->bf)//对不确定因子进行讨论
{
case LH://左边高调整后
T->bf = RH;//根节点右边变高
lc->bf = EH; //lc变平衡
break;
case EH://rd有左右节点
T->bf = lc->bf = EH; //调整后持平
break;
case RH://右边高
T->bf = EH;//根节点平衡
lc->bf = LH;//lc节点变成左边高
break;
}
rd->bf=EH; //调整后rd节点一定平衡，且变成新的头节点
L_Rotate(T->lchild); //1.先左旋
R_Rotate(T); //2.再右旋
}
}
/*************右平衡操作，包含RR和RL*******************************/
void RightBalance(BSTree &T)
{
//对已*T为根的二叉排序树做右平衡旋转处理
//因为为LeftBalance(BSTree &T)的镜像，注释则省略
BSTree lc,rd;
lc = T->rchild;
switch(lc->bf)
{
case RH://右边高，RR型
T->bf = lc->bf = EH;
L_Rotate(T);
break;
case LH://左边高，RL型，分两步旋转
rd = lc->lchild;
switch(rd->bf)
{
case RH:
T->bf = LH;
lc->bf = EH;
break;
case LH:
T->bf = EH;
lc->bf = RH;
break;
case EH:
T->bf = lc->bf = EH;
break;
}
rd->bf = EH;
R_Rotate(T->rchild); //1.先右旋
L_Rotate(T); //2.再左旋
}
}
至于插入操作主要就是判断树是不是平衡，若不平衡是左边还是右边，对于添加的新节点改变了树的平衡了没有，改变了左边的还是右边的，然后进行相应的旋转处理。具体算法如下：
int InsertAVL(BSTree &T, int key, bool &taller)
{
//若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中
//布尔变量taller表示树是否“长高”
if(T==NULL)
{
T = (BSTree)malloc(sizeof(BSTNode));
T->data = key;
T->bf = EH;//叶子结点其平衡因子肯定为0
T->lchild = T->rchild = NULL;
taller = ;//树长高了
}
else
{
if(key==T->data)
{//如果树中已存放此关键字则不予插入
taller = ;
return ;
}
if(key<T->data)
{//关键字小于根结点则插入其左子树中
if(!InsertAVL(T->lchild,key,taller))
return ;
if(taller)
{//如果树长高了，判断是否平衡
switch(T->bf)
{
case LH://若左边高，这次又加上一个左边的节点，则肯定变为2，即需要调整
LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡
taller = ;
break;
case EH://若相等，在左边加一个节点，则变为左边高
T->bf = LH;
taller = ; //树变高
break;
case RH://若右边高，在左边加一个节点，则持平
T->bf = EH;
taller = ;
break;
}
}
}
else
{//插入右子树中
if(!InsertAVL(T->rchild,key,taller))
return ;
if(taller)
{
switch(T->bf)
{
case LH://同理，本来左边高，在右边加一个节点则持平
T->bf = EH;
taller = ;
break;
case EH://右边变高
T->bf = RH;
taller = ;
break;
case RH://右边不平衡了，需要调整
RightBalance(T);
taller = ;
break;
}
}
}
}
return ;
}
4.4．理论与测试
理论：如图，给定一个序列的节点数组，按照几种变换规则得到了图示的排序二叉树，可以得到三序遍历和平衡因子。（由于图形比较多，暂时为手工画图）
该序列为：47, 63, 54,28,31,14,26,53,99,81
先序遍历：31，26，14，28，54，47，53，81，63，99
中序遍历：14，26，28，31，47，53，54，63，81，99
平衡因子：31和47的平衡因子为-1，其他的都为0
测试：运行程序之后输出为：
由先序和中序序列可以还原出树的原型，对照可知结果是正确的。
4.5．讨论与体会
排序二叉树的中序遍历结果即为升序排列，但是运算速率不是最高的，为了寻找更好的方法，平衡排序二叉树便诞生了。对于开创者而言这是令人称赞的，但是对于后学者来说，在学习算法的核心思想的同时，更重要的是别人是怎样想到的，当一个现实生活的需要放在眼前是，我们要有开创的眼光，具有创新能力，这点是非常重要的，因为对于应用上来说有了第一个其他的就不再令人惊奇了。同时，递归，引用，开关、选择分支语句的运用也要引起注意。学习图的最好方法，就是数形结合，一定要多画图。
4.6．附录（源代码）
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define LH 1//左边高
#define EH 0//一样高
#define RH -1//右边高
typedef struct BSTNode
{
int data;//信息
int bf;//平衡因子
struct BSTNode *lchild,*rchild; //平衡树左右儿子指针
}BSTNode,*BSTree;//平衡二叉排序树结构的定义 void R_Rotate(BSTree &p)
{
//对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点
//注意此处引用的好处就是不用再出现双亲指针
BSTree lc;
lc=p->lchild; //指向B的位置
p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性
lc->rchild=p; //更改a的指针位置
p=lc; //lc变成新的a
}
void L_Rotate(BSTree &p)
{
//对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点
//和R_Rotate()镜像对称
BSTree rc;
rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}
//包含LL和LR
void LeftBalance(BSTree &T)
{ //对已*T为根的二叉排序树做左平衡旋转处理
BSTree lc,rd;
lc = T->lchild; //lc调整左边
switch(lc->bf)
{
case LH://若是左边高则为LL型，只需旋转即可
T->bf = lc->bf = EH; //旋转后平衡因子均为0
R_Rotate(T); //LL型需要右旋转
break;
case RH://若是右边高，则为LR型，需分两步调整
rd = lc->rchild; //找到不确定因子rd
switch(rd->bf)//对不确定因子进行讨论
{
case LH://左边高调整后
T->bf = RH;//根节点右边变高
lc->bf = EH; //lc变平衡
break;
case EH://rd有左右节点
T->bf = lc->bf = EH; //调整后持平
break;
case RH://右边高
T->bf = EH;//根节点平衡
lc->bf = LH;//lc节点变成左边高
break;
}
rd->bf=EH; //调整后rd节点一定平衡，且变成新的头节点
L_Rotate(T->lchild); //1.先左旋
R_Rotate(T); //2.再右旋
}
}
/*************右平衡操作，包含RR和RL*******************************/
void RightBalance(BSTree &T)
{
//对已*T为根的二叉排序树做右平衡旋转处理
//因为为LeftBalance(BSTree &T)的镜像，注释则省略
BSTree lc,rd;
lc = T->rchild;
switch(lc->bf)
{
case RH://右边高，RR型
T->bf = lc->bf = EH;
L_Rotate(T);
break;
case LH://左边高，RL型，分两步旋转
rd = lc->lchild;
switch(rd->bf)
{
case RH:
T->bf = LH;
lc->bf = EH;
break;
case LH:
T->bf = EH;
lc->bf = RH;
break;
case EH:
T->bf = lc->bf = EH;
break;
}
rd->bf = EH;
R_Rotate(T->rchild); //1.先右旋
L_Rotate(T); //2.再左旋
}
} int InsertAVL(BSTree &T, int key, bool &taller)
{
//若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中
//布尔变量taller表示树是否“长高”
if(T==NULL)
{
T = (BSTree)malloc(sizeof(BSTNode));
T->data = key;
T->bf = EH;//叶子结点其平衡因子肯定为0
T->lchild = T->rchild = NULL;
taller = ;//树长高了
}
else
{
if(key==T->data)
{//如果树中已存放此关键字则不予插入
taller = ;
return ;
}
if(key<T->data)
{//关键字小于根结点则插入其左子树中
if(!InsertAVL(T->lchild,key,taller))
return ;
if(taller)
{//如果树长高了，判断是否平衡
switch(T->bf)
{
case LH://若左边高，这次又加上一个左边的节点，则肯定变为2，即需要调整
LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡
taller = ;
break;
case EH://若相等，在左边加一个节点，则变为左边高
T->bf = LH;
taller = ; //树变高
break;
case RH://若右边高，在左边加一个节点，则持平
T->bf = EH;
taller = ;
break;
}
}
}
else
{//插入右子树中
if(!InsertAVL(T->rchild,key,taller))
return ;
if(taller)
{
switch(T->bf)
{
case LH://同理，本来左边高，在右边加一个节点则持平
T->bf = EH;
taller = ;
break;
case EH://右边变高
T->bf = RH;
taller = ;
break;
case RH://右边不平衡了，需要调整
RightBalance(T);
taller = ;
break;
}
}
}
}
return ;
}
//访问函数，输出节点以及相应平衡因子
void VisitTree(BSTree &T)
{ //输出结点
if(T!=NULL)
{
printf("%d ",T->data);
printf("平衡因子: %d\n",T->bf);
}
} void PreOrderTraverse(BSTree &T)
{//递归实现先序遍历
if(T!=NULL)
VisitTree(T);
if(T->lchild)
PreOrderTraverse(T->lchild);
if(T->rchild)
PreOrderTraverse(T->rchild);
} void InOrderTraverse(BSTree &T)
{//递归实现中序遍历
if(T->lchild)
InOrderTraverse(T->lchild);
if(T!=NULL)
VisitTree(T);
if(T->rchild)
InOrderTraverse(T->rchild);
}
int main( )
{
BSTree T;
bool taller=;
int i;
T=NULL;
int a[]={,,,,,,,,,};
for(i=;i<;i++)
{
InsertAVL(T,a[i],taller);
}
printf("先序遍历:\n");
PreOrderTraverse(T);
printf("\n中序遍历:\n");
InOrderTraverse(T);
printf("\n");
return ;
}