二叉树结构

二叉树结构（精选9篇）

二叉树结构 篇1

数据结构是计算机科学与技术学科的16门核心课程之一[1],它对培养学生的两项专业能力:算法设计与分析的能力、程序设计能力[1]是非常重要的。数据结构也是全国硕士研究生入学统一考试计算机科学与技术学科综合专业的重要部分,其分数占总分的近三分之一。二叉树是数据结构中非常基础的非线性结构,对学好其它非线性结构具有重要的作用。非线性结构的算法与程序设计对于初学者来说是比较抽象的,即使象二叉树这样简单与基础的非线性结构,要掌握它也不是一件容易的事;学好它离不开动脑与动手,上机编程和调试相关算法非常重要,但是学生不易直观检查计算结果,这会影响调试的效率。

检查二叉树结果可以通过输出二叉树的遍历结果来进行,尤其是层序遍历[2];也可以在集成开发环境中通过监视(Watch)追踪左右子树,这不直观也非常繁琐。图形显示二叉树是比较直观和形象的[3],因此在教学中可以采用图形显示[4,5],比如图1;但是它的缺点也很明显,要求学生掌握一定的图形编程,而不少学生在学习数据结构的时候图形编程基础比较弱,因此教与学往往是在命令行的方式下进行输出,即通过printf或cout进行输出(C/C++语言),所以采用图形输出进行数据结构教学有一定的局限性。

叶品菊等开发了在文本方式下显示二叉树的方法[2],该方法用层序进行输出,每一层输出在一行中,但该方法父结点与子结点之间没有任何东西相连(如图2),因而输出的图形不像一颗树,而是结点的有规律的排列,显示的直观性略差。任燕在其编著的教材《数据结构C++语言描述》[6]中,二叉树的示例图是屏幕截图的,从图中可以看出它利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,显示效果非常直观与形象,与图形模式下的显示方式基本相同,只是链式存储二叉树需要转换成顺序存储二叉树,“以便使链式存储二叉树能以树状形式显示”[6]。该文给出了一种文本模式的二叉树结构显示方法,该方法利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,使用队列对链式存储二叉树进行层序输出,该方法进行较小的改动可以应用于顺序存储二叉树的显示,加入特殊字符’|’经适当修改也可顺利地显示3阶B_树。由于该方法直观形象且是文本模式,因而可以作为数据结构教与学的有效手段之一。

1 显示方法

文本模式下的二叉树显示主要的是计算结点的输出位置,输出位置是由空格的多少来决定的,父结点与子结点之间的连接由三种特殊字符’_’、’/’和’’构成。倒数第一层和倒数第二层之间只需’/’和’’就可连接,左子树由’/’连接,右子树由’’连接。其它层数之间的结点连接由两行构成,第一行连接线由一个或多个’_’与’/’或’’构成,左子树的连接线形如“_____/”,右子树的连接线形如“_____”;第二行的连接只需’/’和’’,左子树是’/’,右子树是’’。其它非连接线位置由空格填充。为了让斜线(/或)指向结点位置,结点不在斜线(/或)的正下方(文献[6]是在正下方),而是偏一格,这样底层结点相邻3个空格,这样的显示效果比文献[6]中的显示效果更为自然和美观。输出的具体编排见图4。

为了计算空格的个数,需要知道二叉树的显示宽度。由于底层结点相隔3个空格,因此二叉树的显示宽度为满二叉树的底层结点数乘4,高度为5的二叉树显示宽度是64个字符长度,高度为6的二叉树显示宽度是128个字符长度。而在文本模式下,由于文本模式每行80个字符(缺省属性)的限制,该文的显示方法只能显示高度不超过5的二叉树。如果要显示高度为6的二叉树,有两种方法,一是修改文本模式每行显示宽度的属性,只要每行可显示超过128个字符即可;二是显示时采用紧凑格式,结点在斜线的正下方[6],这样底层相邻结点之间只有一个空格,高度为6的二叉树显示宽度为64,显示效果见图5,与图3相比美观性略差。文献[2]采用分页的方式来显示高度超过6的二叉树。考虑到该文的方法主要用于教与学,高度为5的满二叉树有31个结点,对于教学来说高度与结点数都足够,因此该文方法不需其它的改动完全满足正常的教学要求。

空格的具体个数依赖于结点所处的层数,计算时分数据域行、第一行连接符和第二行连接符,倒数第一层和倒数第二层之间只有第一行连接符。具体计算公式如下:

数据域:(2n-2个□)a(2n+1个□)(n为树高,□代表空格,a为数据)

第一行连接符:(2n-1个□)(2n-1-3个_)/□(2n-1-3个_)(2n-1+3个□)

第二行连接符:(2n-1-1个□)/(2n-3个□)(2n-1+2个□)

计算第一行连接符时,n=2将导致2n-1-3=-1,因此前面的空格需要减少一个,即2n-1个空格变为2n-1-1个空格。第二行连接符计算时,不会出现这种问题,因为n=2时没有第二行连接符。

2 程序实施

根据以上方法采用C++进行编程,二叉树的类定义如下:

二叉树的输出是从根结点开始,一层一层地输出。每一层分3行输出,第一行输出结点数据,简单起见结点数据类型为字符型;第二行和第三行为连接符,第一行连接符包括三种字符’_’、’/’和’’,第二行只包括’/’和’’两种字符。如果不用字符’_’而用字符’~’也可以,此时第一行连接符包括’/’和’’,第二行包括’~’、’/’和’’三种字符。倒数第一层没有连接符,倒数第二层没有第二行连接符。每一行输出时一个结点一个结点地输出,空结点也需输出,只是结点数据和连接符全部用空格替代。

由于整体输出顺序是层序,因此用结点指针型的队列来处理层序输出;每一层的结点需重复3次进行输出处理,每个结点处理完后需要放回到队列以便重复提取。每一层的3行输出结束后队列需要更新,即下一行的结点进入队列。由于空结点也需处理,队列一直不空,为了充分利用队列,用一个临时结点来表示一层结点的处理结束,否则需要计数处理。加了注释的代码如下:

由于空结点也需要处理,因此代码中有大量的分支语句;为了压缩代码长度,程序编制时大量使用了三目运算符?:。即使这样程序仍有70余行,如果希望进一步压缩代码,三行输出的循环控制压缩到一个循环,此时第一行和第二行的连接符需要存储在两串字符串中,循环结束再输出。这样处理后代码压缩到50余行,压缩量不大且可读性略有下降,不建议这样处理。

3 实例应用

二叉树是数据结构中的基础数据类型,因此应用的地方较多,该文举几个简单的例子。二排序叉树是有利于搜索的数据类型,采用该文方法把搜索的结果用特定字符’*’标识出来如图6。哈夫曼树是一种最优二叉树,带权的初始结点都在叶子上,构造过程中新建的结点都是分支结点;哈夫曼树可以采用顺序存储[6],该文方法略作修改即可应用于顺序存储,用特殊字符’@’标识分支结点显示的哈夫曼树如图7。平衡二叉树是一种优化后的二叉排序树,它的左右子树的高度不超过1,每个结点有一个平衡因子表示左右子树的平衡情况,可以用更为直观的符号表示平衡因子,即’>’代表1、’=’代表0和’<’代表-1,显示时把数据域后面的空格减少一个,用于输出平衡因子的代表符号,显示结果如图8。B_树是一种多路平衡查找树,可用于外部文件的动态查找,B_树的插入与删除算法比较复杂,非常适合学生的编程技能训练,在调试过程中如何快速有效地检查结果比较麻烦,采用该文的方法经适当地修改可以方便地显示3阶B_树。为了显示3阶B_树,增加一个符号’|’指向中间的子树,最重要的修改是显示起始位置的计算,另外用字符’~’替代了字符’_’,此时第一行连接符包括’/’、’|’和’’,第二行包括’~’、’/’、’|’和’’四种字符,这样显示的效果也非常好,如图9。

4 结论

二叉树结构的文本模式显示方法使用了’_’、’/’和’’三种字符来显示二叉树的结构,由于不涉及图形操作,该方法有很强的可移植性,不论TC环境或者VS环境,该文提供的代码都可直接使用。该文的方法也可方便地改为独立的函数,也方便其它的语言实现。该方法方便了树型数据结构程序的调试,不仅可以应用于各种二叉树,也可应用于三叉树,比如3阶B_树。由于直观地显示了二叉树的结构,因而可以提高教与学的效率。同时,算法也使用了队列,对学生巩固已学过的数据结构知识非常有帮助。

参考文献

[1]中国计算机科学与技术学科教程2002研究组.中国计算机科学与技术学科教程2002[M].北京:清华大学出版社,2002.

[2]叶品菊,吴斌,胡远望,等.直观显示二叉树结构的算法[J].江南大学学报:自然科学版,2008,7(1):60-63.

[3]刘福君,李华,王玉森,等.基于二叉树的故障树画树算法研究[J].计算机技术与发展,2006,16(7):117-118.

[4]刘惠敏,董毅.动态模拟二叉树的建立[J].黄冈职业技术学院学报,2004,6(1):75-76.

[5]白雪峰,李沛.二叉排序树的建立及对其中序遍历的动态模拟[J].电脑知识与技术,2005,12(8):84-86.

[6]任燕.数据结构C++语言描述[M].北京:清华大学出版社,2010.

二叉树结构 篇2

课程名称 数据结构课程设计 题 目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学 院 计算机学院 专 业

软件工程 学生姓名

班级/学号------------成 绩 _________________

一． 需求分析

1、建立平衡二叉树并进行创建、增加、删除、调平等操作。

2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。

3、测试数据：自选数据

二． 概要设计

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：

⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；

⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；

⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。

三． 详细设计

树的内部变量

typedef struct BTNode { — 2 —

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

进行左平衡处理;

{

检查*T的左子树的平衡度，并作相应平衡处理

{

case +1:

令根及其左孩子的平衡因子为0;

做右平衡处理;

{

BTree lc;

lc指向的结点左子树根结点;

rc的右子树挂接为结点的左子树;

lc的右孩子为原结点;

原结点指向新的结点lc;

}

break;

case-1:

rd指向*T的左孩子的右子树根

switch(查看右孩子平衡因子)

{

case +1:

根的平衡因子为-1;

根左孩子的平衡因子为0;

break;

case 0:

令根和根左孩子的平衡因子为0;

break;

case-1:

}

}

}

}

根平衡因子为0;根左孩子平衡因子为1;break;

根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0:

case-1:

四．调试分析

在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。

对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。

五．使用说明和测试结果

测试数据：

创建二叉树

— 4 —

增加二叉树

直接创建平衡二叉树

平衡二叉树加入新节点并调平

删除结点

— 6 —

六．心得体会

了解了建立树的方法；

学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法；

学会了向一个已知树插入或删除结点的方法。七．附录 源代码

#include “stdafx.h” #include #include #define EQ(a,b)((a)==(b))#define LT(a,b)((a)<(b))#define LQ(a,b)((a)>(b))#define LH +1 //左高 #define EH 0 //等高 #define RH-1 //右高 typedef struct BTNode { int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;

/*需要的函数声明*/ void Right_Balance(BTree &p);void Left_Balance(BTree &p);void Left_Root_Balance(BTree &T);void Right_Root_Balance(BTree &T);bool InsertAVL(BTree &T,int i,bool &taller);void PrintBT(BTree T,int m);void CreatBT(BTree &T);void Left_Root_Balance_det(BTree &p,int &shorter);void Right_Root_Balance_det(BTree &p,int &shorter);void Delete(BTree q,BTree &r,int &shorter);int DeleteAVL(BTree &p,int x,int &shorter);void Adj_balance(BTree &T);bool SetAVL(BTree &T,int i,bool &taller);bool Insert_Balance_AVL(BTree &T,int i,bool &taller);/*主函数*/ void main(){

int input,search,m;bool taller=false;int shorter=0;BTree T;T=(BTree)malloc(sizeof(BTNode));T=NULL;while(1){

printf(“n请选择需要的二叉树操作n”);printf(“1.创建二叉树2.增加新结点3.直接创建平衡二叉树4.在平衡二叉树上增加新结点并调平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1:

CreatBT(T);break;printf(”请输入你要增加的关键字“);scanf(”%d“,&search);getchar();InsertAVL(T,search,taller);m = 0;PrintBT(T,m);break;Adj_balance(T);删除0.退出n”);case 2: case 3: — 8 —

break;

case 4:

printf(“请输入你要增加的关键字”);

scanf(“%d”,&search);

getchar();

SetAVL(T,search,taller);

m = 0;

PrintBT(T,m);

break;

case 5:

printf(“请输入你要删除的关键字”);

scanf(“%d”,&search);

getchar();

DeleteAVL(T,search,shorter);

m=0;

PrintBT(T,m);

break;

case 0:

break;

default:

printf(“输入错误，请重新选择。”);

break;

}

if(input == 0)

break;

printf(“按任意键继续.”);

getchar();} } /*对以*p为根的二叉排序树作右旋处理*/ void Right_Balance(BTree &p){ BTree lc;lc = p->lchild;//lc指向的*p左子树根结点

p->lchild = lc->rchild;//rc的右子树挂接为*p的左子树 lc->rchild = p;p = lc;//p指向新的结点

} /*对以*p为根的二叉排序树作左旋处理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子树根结点

p->rchild = rc->lchild;//rc左子树挂接到*p的右子树

rc->lchild = p;p = rc;//p指向新的结点

— 9 — } /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree &T){

} /*对以指针T所指结点为根的二叉树作右平衡旋转处理*/ void Right_Root_Balance(BTree &T){

BTree rc,ld;rc = T->rchild;//指向*T的左子树根结点

switch(rc->bf)//检查*T的右子树的平衡度，并作相应平衡处理 { case RH: //新结点插入在*T的右孩子的右子树上，要作单左旋处理

T->bf = rc->bf =EH;Left_Balance(T);break;ld = rc->lchild;//ld指向*T的右孩子的左子树根 switch(ld->bf)//修改*T及其右孩子的平衡因子 BTree lc,rd;lc = T->lchild;//指向*T的左子树根结点

switch(lc->bf)//检查*T的左子树的平衡度，并作相应平衡处理 { case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理

} T->bf = lc->bf = EH;Right_Balance(T);break;rd = lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf)//修改*T及其左孩子的平衡因子 { case LH:

} rd->bf = EH;Left_Balance(T->lchild);//对*T的左子树作左旋平衡处理 Right_Balance(T);//对*T作右旋平衡处理 T->bf = RH;lc->bf = EH;break;T->bf = lc->bf = EH;break;T->bf = EH;lc->bf = LH;break;case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理

case EH: case RH: case LH: //新结点插入在*T的右孩子的左子树上，要作双旋处理

— 10 —

}

} { case LH:

} ld->bf = EH;Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理 Left_Balance(T);//对*T作左旋平衡处理 T->bf = EH;rc->bf = RH;break;T->bf = rc->bf =EH;break;T->bf = LH;rc->bf = EH;break;case EH: case RH: /*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){

if(!T)//插入新结点，树“长高”，置taller为true {

} else {

if(EQ(i,T->data))//树中已存在和有相同关键字的结点 {

} if(LT(i,T->data))//应继续在*T的左子树中进行搜索 taller = false;printf(“已存在相同关键字的结点n”);return 0;T =(BTree)malloc(sizeof(BTNode));T->data = i;T->lchild = T->rchild =NULL;T->bf = EH;taller = true;{ if(!InsertAVL(T->lchild,i,taller))return 0;} else //应继续在*T的右子树中进行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0;

— 11 — } } return 1;} /*按树状打印输出二叉树的元素,m表示结点所在层次*/ void PrintBT(BTree T,int m){

} /*创建二叉树，以输入-32767为建立的结束*/ void CreatBT(BTree &T){

} int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();while(i!=-32767){

} m=0;printf(“您创建的二叉树为：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();taller=false;if(T){

} else {

} printf(“这是一棵空树！n”);getchar();int i;if(T->rchild)PrintBT(T->rchild,m+1);printf(“ ”);//打印i 个空格以表示出层次 for(i = 1;i<=m;i++)printf(“%dn”,T->data);//打印T 元素,换行 if(T->lchild)PrintBT(T->lchild,m+1);— 12 — /*删除结点时左平衡旋转处理*/ void Left_Root_Balance_det(BTree &p,int &shorter){

BTree p1,p2;if(p->bf==1)//p结点的左子树高，删除结点后p的bf减,树变矮 {

} else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 {

} else //p结点的右子树高 {

p1=p->rchild;//p1指向p的右子树

if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 {

} else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮 {

} else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 {

p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){

} else if(p2->bf==-1){ p->bf=1;p1->bf=0;p->bf=0;p1->bf=0;Left_Balance(p);p1->bf=p->bf=0;shorter=1;Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;p->bf=-1;shorter=0;p->bf=0;shorter=1;

}

}

} } else {

} p2->bf=0;p=p2;shorter=1;p->bf=0;p1->bf=-1;/*删除结点时右平衡旋转处理*/ void Right_Root_Balance_det(BTree &p,int &shorter){

BTree p1,p2;if(p->bf==-1){

} else if(p->bf==0){

} else {

p1=p->lchild;if(p1->bf==0){

} else if(p1->bf==1){

} else { p2=p1->rchild;Right_Balance(p);p1->bf=p->bf=0;shorter=1;Right_Balance(p);p1->bf=-1;p->bf=1;shorter=0;p->bf=1;shorter=0;p->bf=0;shorter=1;— 14 —

p1->rchild=p2->lchild;

p2->lchild=p1;

p->lchild=p2->rchild;

p2->rchild=p;

if(p2->bf==0)

{

p->bf=0;

p1->bf=0;

}

else if(p2->bf==1)

{

p->bf=-1;

p1->bf=0;

}

else

{

p->bf=0;

p1->bf=1;

}

p2->bf=0;

p=p2;

shorter=1;

} } } /*删除结点*/ void Delete(BTree q,BTree &r,int &shorter){ if(r->rchild==NULL){

q->data=r->data;

q=r;

r=r->lchild;

free(q);

shorter=1;} else {

Delete(q,r->rchild,shorter);

if(shorter==1)

Right_Root_Balance_det(r,shorter);} } /*二叉树的删除操作*/ int DeleteAVL(BTree &p,int x,int &shorter){

} int k;BTree q;if(p==NULL){

} else if(x

data)//在p的左子树中进行删除 {

} else if(x>p->data)//在p的右子树中进行删除 {

} else {

} q=p;if(p->rchild==NULL)//右子树空则只需重接它的左子树 {

} else if(p->lchild==NULL)//左子树空则只需重接它的右子树 {

} else//左右子树均不空 {

} return 1;Delete(q,q->lchild,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);p=q;p=p->rchild;free(q);shorter=1;p=p->lchild;free(q);shorter=1;k=DeleteAVL(p->rchild,x,shorter);if(shorter==1)Right_Root_Balance_det(p,shorter);return k;k=DeleteAVL(p->lchild,x,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);return k;printf(“不存在要删除的关键字！n”);return 0;— 16 — /*二叉树调平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立平衡二叉树):”);scanf(“%d”,&i);getchar();while(i!=-32767){

SetAVL(T,i,taller);

printf(“n请输入关键字(以-32767结束建立平衡二叉树):”);

scanf(“%d”,&i);

getchar();

taller=false;} m=0;printf(“平衡二叉树创建结束.n”);if(T)

PrintBT(T,m);else

printf(“这是一棵空树.n”);} /*调平二叉树具体方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新结点，树“长高”，置taller为true {

T =(BTree)malloc(sizeof(BTNode));

T->data = i;

T->lchild = T->rchild =NULL;

T->bf = EH;

taller = true;} else {

if(EQ(i,T->data))//树中已存在和有相同关键字的结点

{

taller = false;

printf(“已存在相同关键字的结点n”);

return 0;

}

if(LT(i,T->data))//应继续在*T的左子树中进行搜索 {

}

}

} if(!SetAVL(T->lchild,i,taller))

{

} case LH: //原本左子树比右子树高，需要作左平衡处理

Left_Root_Balance(T);taller = false;break;T->bf = LH;taller = true;break;T->bf = EH;taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的左子树中且左子树“长高”

case EH: //原本左子树、右子等高，现因左子树增高而使树增高

case RH: //原本右子树比左子树高，现左、右子树等高

else //应继续在*T的右子树中进行搜索 {

} return 1;if(!SetAVL(T->rchild,i,taller))

{

} case LH: //原本左子树比右子树高，现左、右子树等高

T->bf = EH;taller = false;break;T->bf = RH;taller = true;break;Right_Root_Balance(T);taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的右子树中且右子树“长高”

case EH: //原本左子树、右子等高，现因右子树增高而使树增高

case RH: //原本右子树比左子树高，需要作右平衡处理

二叉树的遍历 篇3

关键词：二叉树,遍历二叉树,搜索路径

遍历是二叉树最重要的运算之一,是对二叉树进行其他运算的基础。

1 遍历方案

遍历(Traverse)是指沿着某条搜索路线,依次对树中每个节点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

从二叉树的递归定义可知,一个非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:

1)访问根结点(D);

2)遍历该结点的左子树(L);

3)遍历该结点的右子树(R)

以上三种操作有六种执行次序:DLR、LDR、LRD、DRL、RDL、RLD。

2 遍历的命名

根据访问根结点操作发生位置命名:

DLR:先序遍历(Preorder Traverse,亦称前序遍历)访问根结点的操作发生在其左右子树之前。

LDR:中序遍历(Inorder Traverse)访问根结点的操作发生在其遍历左右子树之中(间)。

LRD:后序遍历(Postorder Traverse)访问根结点的操作发生在遍历其左右子树之后。

注意:由于访问是根据根结点D操作位置命名,所以DLR、LDR、LRD分别又称为先根遍历、中根遍历、后根遍历。

3 遍历方法

第一,如何通过给定的二叉树,写出三种遍历序列;

第二,如何通过给定的其中两中遍历序列,求出另一种序列以及画出对应的二叉树图。

下面通过具体的例题给出具体的解答:

如:假设一棵二叉树的先序序列为124536,中序序列为425136。请写出该二叉树的后序序列及其画出对应二叉树

解答过程如下:

1)由先序序列124536,可以得出根结点为1;

2)结合1),由中序序列425136,可以得出425为左子树(中序遍历),36为右子树(中序遍历);

3)结合2),根据先序序列124536,可以得出左子树245采取先序遍历根结点为2(即根结点1的左子树为2);右子树36采取先序遍历根结点为3(即根结点1的右子树为3);再由2),根据425采取中序遍历得出2的左子树为4,右子树为5;再由2,根据36采取中序遍历得出3的右子树为6

所以可以得出:1为根结点,2、3为1的左右子树,4、5为2的左右子树,6为3的右子树;

对应的二叉树如下:

4)根据二叉树图,结合后序遍历的规则LR1,L为根据L也是采取后序遍历为452,R也是采取后序遍历63,代入LR1,得出后序序列为452631。

同理,根据给出的二叉树,采取相同的方法,可以得出先序序列为124536,中序序列为425136。

参考文献

[1]安训国.数据结构[M].4版.大连:大连理工大学出版社,2009:96-101.

二叉树结构 篇4

题目名称： 二叉树的应用问题 专业班级： 计算机科学与技术

学生姓名：

学生学号：

指导教师：

目录

一、题目要求..............................................二、需求分析..............................................三、概要设计..............................................四、详细设计..............................................五、调试分析.............................................六、心得体会.............................................一、题目要求

实现二叉树，求解若干二叉树应用问题

 实现二叉链表表示的二叉树，包括下列运算：

 建立一棵二叉树；

 按先序、中序和后序遍历二叉树；  按层次遍历；

 求一棵二叉树的高度；

 交换一棵二叉树的左右子树；

 设计一个菜单驱动程序，测试上述算法

二、需求分析

建立一棵二叉树：

int CreateBiTree(BiTree &T)按先序遍历二叉树：

void PreOrder(BiTree &T)按中序遍历二叉树：

void InOrder(BiTree &T)按后序遍历二叉树：

void PostOrder(BiTree &T)按层次遍历：

void LevelOrder(BiTree &T)求一棵二叉树的高度：

int Depth(BiTree &T)交换一棵二叉树的左右子树：int PreOrderTraverse(BiTree T)菜单驱动程序：

void menu()

三、概要设计

定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树。

先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；

（3）中序遍历右子树。

后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

层次遍历二叉树的操作选用队列的存储结构。先建立一个长度为1的队列，利用while循环，将根结点放入队首，再将队列长度加一。然后依次遍历左子树和右子树，每遍历一次，2、先序遍历二叉树：

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

3、中序遍历二叉树：

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

4、后序遍历二叉树：

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

5、按层次遍历：

void LevelOrder(BiTree &T){ BiTree queue[100];int front,rear;if(T==NULL)return;front=-1;rear=0;queue[rear]=T;while(front!=rear){ front++;cout<data<<“ ”;if(queue[front]->left_child!=NULL){ rear++;queue[rear]=queue[front]->left_child;

cin>>a;if(a>=0||a<=7){ switch(a){ case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;case 3:

{

cout<<“该树以中序遍历输出为:n”;

InOrder(T);

cout<

}

system(“pause”);

break;case 4:

{

cout<<“该树以后序遍历输出为：n”;

PostOrder(T);

cout<

}

system(“pause”);

break;case 5:

{

cout<<“该树的层次遍历：n”;

LevelOrder(T);

cout<

（二）详细程序代码：{ if(!T){

cout<<“空树!n”;

return;} cout<data<<“ ”;if(T->left_child)Output(T->left_child);if(T->right_child)Output(T->right_child);}

int Depth(BiTree &T){ int i,j;if(!T)return 0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;}

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

void LevelOrder(BiTree &T)

cout<<“<<

1.二叉树树深

>>”<

cout<<“<<

2.二叉树的先序遍历

>>”<

cout<<“<<

3.二叉树的中序遍历

>>”<

cout<<“<<

4.二叉树的后序遍历

>>”<

cout<<“<<

5.二叉树的层次遍历

>>”<

cout<<“<<

6.左右孩子交换

>>”<

cout<<“<<

7.退出

>>”<

cout<<“*******************************************************************”<

void main(){

int br,a;BiTree T;br=CreateBiTree(T);

while(1){

menu();

cout<<“请输入选择的命令-->”;

cin>>a;

if(a>=0||a<=7)

{

switch(a)

{

case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;

case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;

case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;

case 3:

{

cout<<“该树以中序遍历输出为:n”;

（一）先序输入二叉树：

（二）建立一棵二叉树：

1后序遍历：

（四）按层次遍历：

3中序遍历交换后的二叉树：

六、心得体会

二叉树电子家谱设计 篇5

1 电子家谱系统简介

1.1 系统复杂性

李士勇认为复杂性是指系统在演化过程中和环境交互作用, 呈现出的复杂的动态行为特性和突出的整体特性。除此之外, 人们一般认为复杂系统是由众多存在复杂相互作用的组分 (或子系统) 组成的。家谱系统涉及众多子系统, 形成了规模庞大的多层次结构, 因此家谱系统具有多方面的复杂性。

1.2 系统结构

家谱是家族成员间相互联系组成一种体系结构。同家谱数据中由后代节点和父代节点分别组成家谱树的特点对应, 家谱系统通常采用树形结构。

2 二叉树家谱系统设计

2.1 家谱的体系结构

二叉树能够很好的反映家谱中成员之间的关系。本文系统中使用父子——兄弟结构, 即左子树第一个节点为父节点的儿子 (或兄弟) , 同理右子树第一节点表示父节点的兄弟 (或儿子) 。并且采用三叉链表的方式存储二叉树, 不仅便于对字节点进行查找, 还可以回溯查询关联节点确定成员间关系。

2.2 家谱成员及功能设计

2.2.1 数据单元设计

选定家族成员作为数据基本单元, 并在程序中定义为结构体Bi TNode。因为在一个家族中, 家谱中每个家族成员是最基本的组成部分。Bi TNode结构如下:

typedef struct Bi TNode{

标记、姓名、生日、住址、婚否、建在否、性别、妻子 (如已婚) 、死亡日期 (如已死亡) ;

struct Bi TNode*lc, *rc, *father;

}Bi TNode, *Bi Tree;

2.2.2 功能设计

系统设计了多种实用功能, 主要功能有:

3 设计实现的注意要点

建立树时, 由于新申请结点的孩子指针、兄弟指针等均未赋空值;但在函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用函数时出现系统保护异常 (使用了不安全的指针) 。因此在系统初始化时, 需要对以上几种属性赋予无影响初始值。

删除结点时, 只考虑到删除本身结点, 而其孩子结点的情况未考虑, 故在删除某些结点时会出现“断链”现象。故在删除某一结点时, 首先要判断此结点是否有孩子及兄弟, 然后进行相应操作。

4 结语

电子家谱系统是一种重要工具, 它使家谱得以充分保护和使用。笔者的二叉树电子家谱系统设计提高了家谱使用的实用性和易用性, 为家谱系统的电子信息化打下了一定基础。家谱电子信息化是一个庞大的系统工程, 今后我们将研究家谱便易搜索算法以及家谱成员流动模式。

参考文献

[1]王鹤鸣.中国家谱通论[M].上海:上海古籍出版社, 2010:4.

[2]司马贺.人工科学:复杂性面面观[M].上海:上海科技教育出版社, 2004:78-79.

[3]李士勇.非线性科学与复杂性科学[M].哈尔滨:哈尔滨工业大学出版社, 2006:23.

题解二叉树的构造 篇6

关键词：数据结构,二叉树遍历,二叉排序树

学习过数据结构的读者们都知道, 在二叉树的遍历章节中, 有一种比较典型的题型是: 给出一棵二叉树的先序遍历序列及中序遍历序列, 据此构造出这棵二叉树。 这个问题一般都是根据二叉树的前序遍历和中序遍历定义及二叉树的性质求解的。 笔者在学习过程中发现另一种解决方案, 即利用二叉排序树的定义来求解。 下面笔者将两种方案一一介绍如下。

一、利用二叉树遍历定义求解

一般书中的常见解法为:由二叉树的遍历定义得知, 二叉树的前序遍历是先访问二叉树的根结点, 然后遍历左子树, 最后再遍历右子树, 也就是根-左-右的顺序。 这样, 在遍历结点的前序序列中, 第一个结点一定是根;而用中序遍历时, 是先遍历左子树, 再访问根结点, 最后遍历右子树, 是左-根-右的顺序, 由此知道, 根结点将中序遍历序列分割成两个部分:在根结点前是左子树的中序遍历序列, 在根结点之后则是右子树的中序遍历序列。 反之, 根据左子树的中序遍历序列中结点的个数, 又可将前序序列除根以外分成左子树的前序序列和右子树的前序序列两部分。 依次类推, 我们就得到了整棵二叉树。

如下例:

例1: 已知二叉树结点的前序序列为:ABCDEFG, 中序序列为:CBDAFEG, 试绘出这棵二叉树。

解1: 首先由前序序列得知二叉树的根为A, 则由中序遍历序列得出其左子树的中序遍历序列为 (CBD) , 右子树的中序遍历序列为 (FEG) 。 反过来, 又由前序序列得知其左子树的前序序列必为 (BCD) , 右子树的前序序列为 (EFG) 。 由左子树的前序序列 (BCD) 得出左子树的根结点为B, 又由左子树的中序序列 (CBD) 得出以B为根的左子树的左边叶子结点为C, 右边叶子结点为D。 同理, 可构造得出右子树。

构造过程图示如下:

二、利用二叉排序树的定义求解问题

二叉排序树是一种特殊的二叉树, 它的每一个结点数据中都有一个关键值, 并且对于每个结点, 如果其左子树非空, 则左子树的所有结点的关键值都小于该结点的关键值, 如果其右子树非空, 则右子树的所有结点的关键值都大于该结点的关键值。 根据其定义可知, 对二叉排序树进行中序遍历, 将得到一个按结点关键值递增有序的线性序列。若从一棵空树出发, 构造一棵二叉排序树, 则每次插入的新结点都是二叉排序树上新的叶子结点, 我们可以假设为:从一棵空树出发, 构造一棵二叉排序树, 每次插入的新结点序列即为这棵二叉排序树的前序序列。由此我们得出文中问题的第二种解决方案:

1.将给出的中序序列中每个结点按升序依次赋一关键值;

2. 根据第一步中所赋之值得到前序序列的关键值序列;

3. 以前序序列所得到的关键字序列构造一棵二叉排序树;

4. 将构造出的二叉排序中的关键字用原结点值换回。

下面我就以第二种解决方案来解上文中的例1。

解2:将题中中序序列 ( CBDAFEG) 中每个结点按升序依次赋一关键值, 如结点C对应关键值为1, 结点B对应关键值为2, 结点D对应的关键值为3, 结点A对应的关键值为4, 结点F对应关键值为5, 结点E对应关键值为6, 结点G对应关键值为7。

然后按前序序列 (ABCDEFG) 的关键字序列 (4, 2, 1, 3, 6, 5, 7) 构造一棵二叉排序树, 构造过程如下:

最后将所构造成的二叉排序树中的各关键值用原结点值换回, 所得出二叉树如下所示:

问题即得解。

比较这两种问题的解决方法, 各有优劣。用第一种方法, 不需掌握二叉排序树的相关知识, 但如果此二叉树结构较复杂, 结点较多时, 使用此种方案, 易造成思路混乱, 速度较慢的后果, 而使用第二种解法较简便快捷。

参考文献

[1]严尉敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997.

[2]蔡子经, 施伯乐.数据结构教程[M].上海:复旦大学出版社, 1994.

[3]刘清, 王琼.数据结构[M].北京:电子工业出版社, 2001.

C语言递归生成二叉树探讨 篇7

叉树是一种基本的非线性数据结构, 二叉链表是其常用的存储形式。用二叉链表实现生成二叉树的算法比较多, 其中递归生成及递归遍历二叉树属于二叉树的基本操作。目前无论在教学或实用使用中, 大都采用C、C++或C#编程实现, 其中用面向过程基本C语言编程属于重要的基本实现方法。该文在基于基本C语言环境下对实现生成二叉树及遍历进行一些探讨。

该文二叉链表数据结构用C语言表示为:

2.二叉树递归生成

可以利用二叉树基本性质, 即从根结点开始, 不断给当前叶子结点添加左、右新的子结点, 生成整棵完整的二叉树。这里, 以前序递归方法为例来介绍。需要注意的是输入时按先序遍历次序输入二叉树中结点的字符值, 同时要把左右子树为空的结点也要表示出来, 该文用`#`表示空树。

下面给出几种C语言实现方案:

使用的宏定义:

方法2:

方法3:

对上面几种方法, 若有下面一颗二叉树 (图1) , 从键盘输入的字符为:abc##de#g##f###, 则都可得到正确的二叉树。

一种常见的错误方法:

错误的原因:形参不能把执行结果带出函数体外, 因此创建不了二叉树。如果是C++语言, 可以把函数首都定义为:void Create (BTree&a) , 可以得到正确的结果。但是, 基本C语言形参不支持地址 (&) 引用。这一点, 在编程时应格外注意。

3.二叉树递归遍历

遍历时从根结点开始, 依先访问根节点, 再访左结点和右结点的顺序递归往下访问所有的结点。对上面给定的二叉树, 前序遍历的顺序如图2所示。

有两种递归实现遍历的方法, 同样以前序遍历为例:

方法1:

方法2:

main主程序调用语句为:

其中, my＿tree为先前生成的二叉树。

说明:方法1程序较简单, 而方法2更通用一些。对于上面实验数据, 遍历输出的序列为:abcdegf。

4.结语

从上面分析可知, 用C语言实现生成二叉树时, 生成函数是否设置形参, 以及是否设置函数的返回值, 对执行的结果都有很重要的影响。遍历时, 也给出了两种递归实现方法。对于中序、后序生成及遍历, 应该调整根结点相对应左、右结点的顺序即可。在编程时应仔细考虑提到的问题, 注意细节, 避免出错。

参考文献

[1]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社, 2002

[2]盛魁.二叉树的遍历探究与应用[J].电脑知识与技术, 2008, 3 (5) :1014-1015

二叉树结构 篇8

关键词：电路结构优化,二叉树优化法,CVSL电路,互补CMOS逻辑

0 引 言

CVSL电路适合于整个系统或模块的高速设计中。在单端式逻辑(Single- ended logic)和差动式逻辑间需要提供互补信号的反相器[1]。对于复杂逻辑,由于两个NMOS Tree有共同项,电路可进一步化简,减少MOS管数量。传统的方法是用卡诺图法,但卡诺图并不能显示出电路的连接关系,若改用二叉树算法,则可以很明了的反映出电路的连接关系。

1 CVSL电路的特点

互补静态CMOS特点电路的特点是P管阵列的逻辑结构正好是N管阵列的对偶,若一阵列是串联,则另一阵列必定是并联。NMOS阵列是原量控制,PMOS阵列是非量控制, 因而,N型阵列和P型阵列可以接同一个输入信号[2]。电路中PMOS管的数目与NMOS管的数目相同。如果输入变量共有k个,则总共需要2k个晶体管,形成一种全互补电路。但管子数量多,版图可能比较复杂。只有设计得当, 版图才会有规则。

虽然CMOS电路有许多优点,但一般认为其与伪NMOS相比有两大缺点:

(1) CMOS电路的速度比伪NMOS低。任何一级CMOS倒相器至少有两只管子,一只P管和一只N管,它们的栅极是连接在一起的,输入电容加倍,前级的充放电就比较慢。

(2) CMOS电路所需的器件数多。一个逻辑电路需要设计两套逻辑函数,分别传送原函数和其补函数。因而,CMOS电路的 逻辑冗余度较高。不仅浪费硅片面积,而且增加互联任务,使性能降低[3]。伪NMOS电路只采用一个P管作为上拉负载,以代替全互补标准CMOS电路中的P阵列逻辑。但增加了静态功耗,提高了输出低电平,降低了噪声容限。为克服功耗提出电路的改进方案即CVSL电路[4],如图1所示。

由于电路同时接收差动式的输入(Differential Input)且提供差动式的输出(Differential Outputs),所以又称为DCVSL(Differential Cascade Voltage Switch Logic)电路。并且原量反量同时输出。虽然比CMOS所用MOS管数量多,但提供互补输出且由于电子迁移率高于空穴,相同面积下速度比CMOS高(是一种高速设计)。由于存在正反馈,完全消除了Pseudo-NMOS中的静态电流,使输出达到rail to rail(低功耗高噪声容限),进一步提高了翻转速度。

该电路适合于整个系统或模块都用DCVSL的设计,在单端式逻辑(Single- ended Logic)和差动式逻辑间需要提供互补信号的反相器。对于复杂逻辑,由于两个NMOS Tree有共同项,所以电路可进一步化简,减少了MOS管数量。

2 用二叉树优化CVSL电路

任何一个逻辑表达式F可表示为一些简单函数的和,也即它的展开对应着一个递归的二叉树,以一位二进制全加器为例,其和S的真值表和逻辑表达式如下所表1所示。

本位和S=A′B′C1+A′BC1"+AB′C1′+ABC1,构造其所对应的二叉树如图2所示。

实际上,二叉树中的一些节点是重复的,在该图2中,最后一层的0和1节点它们可以合并,对二叉树有缩减规则,其一是当两个节点传输到下一个节点的传输路径完全相同时,两个节点可以缩减为一个;当一个节点的所有传输路径都归结到同一个下一级节点时,这个节点可以省略。如图3所示。

合并0项和1项,通过缩减规则最终可得一位二进制全加器的二叉树如图4所示。将所有节点转化为NMOS的连接点,将路径有相应的NMOS管来代替,即可得到最终的CVSL电路,如图5所示,这样用二叉树转化为MOS电路的过程就完成了。

3 结 语

本文对比了CMOS电路与CVSL电路的特点,针对CVSL电路速度快功耗低的优点,在高速电路和VLSI设计中通常采用该电路,但由于CVSL电路共享的NMOS管较多,为提高利于率,对比互补的特点,提出了优化电路的二叉树算法。它比传统的真值表优化法,其直观性更强,很好地解决了CVSL电路的设计问题。

由遍历结果还原二叉树的递归算法 篇9

1 二叉树创建的常规方法

对于二叉树的创建,常规的方法是将二叉树补充成完全二叉树,如图1和图2所示,然后,自上而下,从左到右输入各结点值,假定,第一个结点(根结点)编号为1,第二个结点编号为2,…,依此类推,则第i个结点如果有左孩子,其左孩子结点编号为2i,如果有右孩子,右孩子结点的编号为2i+1,根据这个性质就能建立起结点间的联系,达到创建二叉树的目的。但是,由于补充的虚拟结点太多,在输入相关信息时,容易因少输或多输虚拟结点而出错。

2 由遍历结果生成二叉树

2.1 由中序后序遍历结果生成二叉树的算法实现

2.1.1基本思想

二叉树的遍历通常有前序、中序及后序三种,由二叉树的一种遍历结果是无法唯一确定一棵二叉树,但由二叉树中序及后序的遍历结果可以唯一确定二叉树[2]。这个性质可由如下归纳法证明:

证明:设n为结点个数。(1)当n=0时,此时,后序遍历序列和中序遍历序列都是空,该二叉树是空树,而空二叉树是唯一的,命题成立。

(2)设n<=k-1时,命题成立则

(3)当n=k时,对于有k个结点的二叉树,后序遍历序列中的最后一个结点必然是该二叉树的根结点,所以,根结点是唯一的。

不妨设根结点在中序序列中处于第i个(i>0),则中序序列中,前i-1个为左子树,后k-i个为右子树。后序序列是由左子树序列、右子树序列及根结点构成,所以,后序的前i-1个所包含的元素必然与中序的i-1个一样,后序从第i个往后的k-i个元素必为右子树的元素。

而i-1

也就是说,当n=k时命题成立。

由(1)、(2)、(3)可知对于任意个结点的二叉树都可由后序遍历序列和中序遍历序列唯一确定。

下面举例说明,设二叉树中序遍历结果为d b e a g f h i c,后序遍历结果为d e b g i h f c a则可以完全确定二叉树如图1所示。

其基本思想是:

1)由后序结果的最后一个结点为a可知,该二叉树的根结点必然是a

2)由于根点为a,从中序遍历结果中找到a所在住置,如此,便能断定其左子树必然由d b e三个结点构成,右子树必然由g f h i c构成。

3)由后序遍历的定义可知,在后序遍历结果中,左子树的三结点d b e必然在右子树的五个结点g f h i c之前,于是,根据左子树、右子树的结点个数把后序遍历结果准确分为左子树、右子树及根结点三部分。

4)利用得到的左右子树的中序及后序结果,重复上述步骤,直到某一子树为空为止,如此便完成二叉树的建立。整个过程如图3,图4,图5……

2.1.2算法实现

根据以上的分析,我们可以得到由中序后序的遍历结果构造二叉树的递归方法。

1)二叉树的结点定义

2.2 由前序序列和中序序列生成二叉树的递归算法

基于同样的分析,可以得到由前序和中序的遍历结果还原二叉树的方法,同样可以用递归方法实现。

TREENODE*createTree(int m1,int n1,int len)//m1参与建树结点在中序遍历中的起始位置

2.3 由层次遍历序列和中序遍历序列生成二叉树的递归算法

首先说明中序遍历序列的含义,如图6,中序结果为d b e a g f h i c,二叉树严格按左子树靠左,根结点居中,右子树靠右画法,则中序遍历的结果即为结点从左到右的排列。

利用数学归纳法同样可以证明,由层次遍历结果与中序遍历结果可以唯一确定二叉树。在此,不再作证明,仅用图例说明创建二叉树过程。

设:中序遍历结果为d b e a g f h i c层次遍历结果a b c d e f g h i则

1)结点的左右顺序如图7;

2)层次遍历的第一个结点为a,可知a为根结点,左子树为d b e,左右子树g f h i c,如图8;

3)对于左子树d b e,由层次遍历的次序可知b为根结点,对于右子树g f h i c,由层次遍历的次序可知c为根结点如图9;

4)对于子树的子树,同样按照上述的方法确定结点位置,直到结点个数为0为止。

利用层次遍历结果和中序遍历结果还原二叉树的算法

中序序列中的每个元素,在层次序列的都有相应的序号,序号最小者即为根结点,为计算方便,用数组inOrderValue[]存储每个中序元素在层次序列中的位置(即序号)。方法是:

3 结束语

由二叉树的遍历结果还原二叉树的递归算法,可以省去输入众多虚拟结点的麻烦,减少输入错误的可能性,这样,可以把更多的精力专注于二叉树相关操作算法的实现。

参考文献

[1]耿国华.数据结构――C语言描述[M].西安:西安电子科技大学出版社,2006.