摘 要

本次课程设计以二叉树为基础，重点讨论二叉树的存储表示以及如何建立一任意二叉树，阐述如何对二叉树进行线索化及利用线索进行对二叉树遍历的过程，并按中序遍历和先序遍历的顺序线索化以上二叉树，实现在一已经中序线索化后的二叉树上插入和删除结点，并保证索引不破坏。

关键词：线索化；二叉树；先序；中序；后序，遍历

 

目 录

1课题描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2需求分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

3概要设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

4详细设计. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

5程序编码. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

6程序调试与结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7算法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

8总结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1 课题描述

本次试验通过对二叉树进行线索化后三种遍历的实现，三种遍历的过程必须找到序列中的第一个结点，然后依次找出结点后继直至其后继为空时为结束。

构建二叉树的过程中，通过先序构建，在构建初，对于线索的初值都赋值0，然后进行线索化的过程分别应用了三种对应的先、中、后的线索，然后在其三种的线索的基础上进行三种遍历，进而完成二叉树线索遍历的实现。输出三种遍历后的不同结果，从而完成本次试验。

2需求分析

必须确定本次实验的目的，即完成二叉树的线索化、完成二叉树的一般操作。完成本次实验，必须确定该树的存储对象，即值域、左子树、右子树、还有控制线索的rtag、ltag。

在线索化的实现过程中，要进行三个部分：

首先，保证该树已经存在，必须在树存在的基础上进行线索化。

再次，确定线索化需要三种不同的线索化，先序、中序、后序线索化。

最后，完成三种不同的遍历——先序、中序、后序遍历，输出二叉树。

3 概要设计

这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块流程图如图3.1所示。

 

主函数

建立二叉树

先序线索化

中序线索化

后序线索化

先序线索化遍历

中序线索化遍历

后序线索化遍历

图 3.1 模块流程图

4 详细设计

线索二叉树的主要函数设置如下：

树的存储的类型为：typedef struct bithrnode

{

char data;

struct bithrnode *lchild,*rchild;

int ltag,rtag;

}bithrnode,*bithrtree;

主程序：

bithrtree T, p,T1;

int k;

Do

{

switch(k)

{

case 1:

creat(T); ——–建立二叉树

T1=copy(T); ———复制建立后的二叉树

case 2:

T=copy(T1); ———复制建立后的二叉树

PreOrderThreading(p,T); ———先序线索化

first(p); ————–先序遍历

case 3: T=copy(T1); ———复制建立后的二叉树

InOrderThreading(p,T); ———-中序线索化

mid(p); —————中序遍历

case 4: T=copy(T1); ———复制建立后的二叉树

backorderThreading(p,T); ————-后序线索化

last(p); ————–后序遍历

}

}while(k!=0);

子程序：

bithrtree creat(bithrtree &T) ——–建立二叉树

Status PreOrderThreading(bithrtree &thrt,bithrtree T) ———先序线索化

{void PreThreading(bithrtree p)} ———先序线索化子函数

Status InOrderThreading(bithrtree &thrt,bithrtree T) ———-中序线索化

{void inthreading(bithrtree &p)} ———-中序线索化子函数

Status backorderThreading(bithrtree &thrt,bithrtree T) ————-后序线索化

{void backthreading(bithrtree p)} ————-后序线索化子函数

void first(bithrtree thrt) ————–先序遍历

void mid(bithrtree thrt) —————中序遍历

void last(bithrtree t) ————–后序遍历

bithrtree copy(bithrtree &r) ———复制建立后的二叉树

bithrtree creat(bithrtree &T)

1. 创建二叉树（ CreateBiTree(T)）

设计思想：在用户需要创建二叉树时，屏幕提醒输入树的各个结点，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据。设计流程如图4.1所示。

图4.1 CreateBiTree(T )

创建二叉树

 

1. 先序线索化二叉树

设计思想：由于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过程，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前结点，则pre指向他的前驱。由此可得先序遍历建立先序线索化的设计流程如图4.2所示。

图4.2先序线索化

PreOrderThreading(bithrtree &thrt,bithrtree T)

(3)中序线索化设计流程如图4.3所示

图4.3中序线索化

Status InOrderThreading(bithrtree &thrt,bithrtree T)

 

 

(4)后序线索化设计流程如图4.4所示

图4.4后序线索化

Status backorderThreading(bithrtree &thrt,bithrtree T)

5 程序编码

#include<stdio.h>

#include <string.h>

#include<malloc.h>

#include<stdlib.h>

#define OVERFLOW -2

#define OK 1

#define error 0

typedef int Status;

typedef enum pointertag{ link=0,thread=1 }; //link==0; 指针 thread==1；线索

typedef struct bithrnode

{ char data;

struct bithrnode *lchild,*rchild; //左右孩子指针

int ltag,rtag;

}bithrnode,*bithrtree;

bithrtree pre;

bithrtree creat(bithrtree &T) //构造二叉树

{ char ch;

fflush(stdin);

scanf(“%c”,&ch);

if(ch==’ ‘||ch==’#’)

T=NULL;

else

{ if(!(T=(bithrnode *)malloc(sizeof(bithrnode))))

return error;

T->data=ch;

T->ltag=0;

T->rtag=0;

printf(“输入父结点%c的左孩子：”,ch);

T->lchild=creat(T->lchild);

printf(“输入父结点%c的右孩子：”,ch);

T->rchild=creat(T->rchild);

}

return T;

}

void PreThreading(bithrtree p) //先序线索化

{ if(p)

{

if(!p->lchild)

{ p->ltag = thread;

p->lchild = pre;

} //前驱线索

if(!pre->rchild)

{ pre->rtag = thread;

pre->rchild = p;

} //后继线索

pre = p;

if(p->ltag==link)

PreThreading(p->lchild); //左子树线索化

if(p->rtag ==link)

PreThreading(p->rchild); //右子树线索化

}

}

Status PreOrderThreading(bithrtree &thrt,bithrtree T) //先序线索二叉树

{ if(!(thrt=(bithrtree)malloc(sizeof(bithrnode))))

return error;

thrt->ltag=link;

thrt->rtag=thread; //建头结点

thrt->rchild=thrt; //右指针回指

if(!T)

thrt->lchild=thrt; //空二叉树

else

{ thrt->lchild=T;

pre=thrt;

PreThreading(T); //先序遍历进行先序线索化

pre->rchild=thrt;pre->rtag=thread; //最后一个结点线索化

thrt->rchild=pre;

}

return OK;

}

void inthreading(bithrtree &p) //中序线索化

{

if (p)

{ inthreading(p->lchild); //左子树线索化

if (!p->lchild)

{ p->lchild=pre;

p->ltag=thread;

}

if (!pre->rchild)

{ pre->rchild=p;

pre->rtag=thread;

}

pre = p;

inthreading(p->rchild); //右子树线索化

}

}

Status InOrderThreading(bithrtree &thrt,bithrtree T) //中序线索化二叉树

{

if(!(thrt=(bithrtree)malloc(sizeof(bithrnode))))

exit(OVERFLOW);

thrt->ltag=link;

thrt->rtag=thread; //建头结点

thrt->rchild=thrt; //右指针回指

if(!T)

thrt->lchild=thrt; //若二叉树为空，则左指针回指

else

{ thrt->lchild=T;

pre=thrt;

inthreading(T); //中序遍历进行中序线索化

pre->rchild=thrt;

pre->rtag=thread; //最后一个结点线索化

thrt->rchild=pre;

}

return OK;

}

void backthreading(bithrtree p) //后序线索化

{

if(p)

{ backthreading(p->lchild);

backthreading(p->rchild);

if(!p->lchild)

{ p->ltag=thread;

p->lchild=pre; } //前驱线索

if(!pre->rchild)

{ pre->rtag=thread;

pre->rchild=p;} //后继线索

pre=p;

}

}

Status backorderThreading(bithrtree &thrt,bithrtree T) //后序线索化二叉树

{

if(!(thrt = (bithrtree)malloc(sizeof(bithrnode))))

exit(OVERFLOW);

thrt->ltag=link;

thrt->rtag=thread; //建头结点

thrt->rchild=thrt;

if(!T)

thrt->lchild=thrt; //若二叉树为空，则左指针回指

else

{ thrt->lchild=T;

pre=thrt;

backthreading(T); //中序遍历进行中序线索化

pre->rchild=thrt;

pre->rtag=thread; //最后一个结点线索化

thrt->rchild=pre;

}

return OK;

}

void first(bithrtree thrt) //先序遍历二叉树

{

bithrtree p;

printf(“先序遍历结果为： “);

p=thrt->lchild;

while(p!=thrt)

{ printf(“%c “,p->data);

while(p->ltag == link)

{

p=p->lchild;

printf(“%c “,p->data);

}

while((p->rtag==thread)&&(p->rchild!=thrt))

{ p = p->rchild;

printf(“%c “,p->data);

}

p = p->rchild;

}

printf(“\n”);

}

void mid(bithrtree thrt) //中序遍历二叉树

{

bithrtree p;

printf(“中序遍历结果为： “);

p=thrt->lchild;

while(p!=thrt)

{ while(p->ltag == link)

p=p->lchild;

printf(“%c “,p->data);

while((p->rtag==thread)&&(p->rchild!=thrt))

{ p = p->rchild;

printf(“%c “,p->data);

}

p = p->rchild;

}

printf(“\n”);

}

bithrtree parents(bithrtree &thrt,bithrtree &p){

bithrtree t;

t=thrt;

if(t->lchild==p)

return t; //父节点是头结点

else{

t=t->lchild;

while( t->lchild!=p && t->rchild!=p )

{ if(link==t->rtag)

t=t->rchild; //结点有右结点，往右

else

t=t->lchild;

} //如果结点没有右孩子，去左孩子，没有左孩子，去前驱

return t;}

}

void last(bithrtree t) { //后序遍历二叉树

bithrtree p,q;

p=t->lchild;

while(1)

{ while(p->ltag==link)

p=p->lchild;

if(p->rtag==link)

p=p->rchild; //p指向第一个被访问的结点

else break;

}

while(p!=t)

{ printf(“%c “,p->data);

q=parents(t,p); //parent是p的双亲:

if(t==q) p=t; //若parent是thrt，即p是根结点，则无后继

else

if(p==q->rchild||thread==q->rtag)

p=q; //若p是双亲的右孩子，或者是独生左孩子，则后继为双亲

else

{

while(q->rtag==link)

{ //若p是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。

q=q->rchild;

while(q->ltag==link)

{ q=q->lchild; }

}

p=q;

}

}

printf(“\n”);

}

bithrtree copy(bithrtree &r) //复制一棵二叉树

{

bithrtree tr;

if(r==NULL) tr=NULL;

else{ if(!(tr=(bithrtree)malloc(sizeof(bithrnode))))

return 0;

tr->data=r->data;

tr->ltag=r->ltag;

tr->rtag=r->rtag;

tr->lchild=copy(r->lchild);

tr->rchild=copy(r->rchild);

}

return tr;

}

void main() //主函数

{

bithrtree T, p,T1;

int k;

do{ printf(“\t————-线索二叉树—————\n\n”);

printf (“\t建二叉树 1 “);

printf (“\t\t\t先序遍历线索化二叉树 2 \n”);

printf (“\t中序遍历线索化二叉树 3 “);

printf (“\t后序遍历线索化二叉树 4 \n”);

printf (“\t结束输入 0\n”);

printf(“\n\t————————————\n\n”);

printf (“请输入您的选择:”);

scanf (“%d”,&k);

switch(k)

{

case 1:

printf(“\t——–结束为 ‘#’——————— \n”);

printf(“请输入树的根结点:”);

creat(T); T1=copy(T);

system(“cls”);

break;

case 2:

T=copy(T1);PreOrderThreading(p,T);

first(p);

system(“pause”);

system(“cls”);

break;

case 3:

T=copy(T1);InOrderThreading(p,T);

mid(p);system(“pause”);system(“cls”);

break;

case 4:

T=copy(T1);backorderThreading(p,T);

last(p);system(“pause”); system(“cls”);

default:

break;

}

}while(k!=0);

printf(“\n\t谢谢使用！\n”);

}

 

6 程序调试与结果

（1）如图6.1所示的二叉树线索化的理论结果：

先序遍历线索化二叉树结果为：abdefcg

中序遍历线索化二叉树结果为：edfbacg

后序遍历线索化二叉树结果为：efdba

a

b

c

g

d

f

e

图6.1创建的二叉树

（2）如图6.21所示的二叉树的实际结果：

1)创建二叉树的实际结果如图6.2：

图6.2 构建二叉树

2)先序遍历线索化二叉树的实际结果如图6.3所示：

图 6.3 先序遍历

3)中序遍历线索化二叉树的实际结果如图6.4所示：

图 6.4 中序遍历

4)后序遍历线索化二叉树的实际结果如图6.5所示：

图6.5 后序遍历

5)结束界面如图6.6所示：

图6.6 结束

7 算法分析

当对树进行线索和遍历时，首先必须建立二叉树，没有建立二叉树、当遍历时树为空，其次遍历的过程必须在线索化的后面进行，这样才能够体现出本次试验的目的—线索化二叉树。遍历的实现还需要与其对应的线索化进行一 一对应，否则遍历的结果是错误的。线索和遍历的过程是本次试验重点，所以，本次就是通过这两部分的完成就能够完成本次试验的操作。

线索二叉树的时间复杂度和空间复杂度,因为在线索的过程都必须要申请存储空间，就是需要多少存储空间，就申请空间，但是在后面需要复制本二叉树的信息，所以也要求与建立的书的存储空间相同，即空间复杂度为（n）。

遍历和线索的时间复杂度都是O（n），因为在其过程中线索一个走其下一个节点，过程依次将所有节点线索完成。遍历同样是该过程进行的，所以遍历的时间复杂度同样为O（n）。

 

8 总结

在本次课程设计中，我遇到了一些难题，但也让我受益颇多。本系统是以VC++ 6.0为开发工具编的程序。本系统实现了对二叉树创建，先序和中序遍历以及线索化后先序和中序遍历的功能。当第一周结束的时候，我感觉自己收获挺大的，从一开始的迷茫，不知道从何下手到把程序中的几个模块编写出来，心里挺开心的。但是到了第二周，我不由得再次陷入困境，在整个程序的编写过程中，最难的就是遍历和线索化这两个模块，这也是我第二周要解决的重点问题。

开始编写二叉树的线索化时，很头疼，去向其他人寻求帮助，在别人的帮助和提示下，我编完了线索化的程序，但编译时老出错，困难之时，在老师的帮助之下，完成了线索化这个模块，这样，整个程序基本上全部完成了，就剩下完善工作了。虽然设计是完了，但我觉得其中还是有一些不足之处，整个程序完成了，还有很多不完善的地方，希望自己以后遇到事情要认真，仔细，考虑周全。在准备过程中，我锻炼了自己解决问题的能力，在不懂的情况下通过到图书馆借阅图书，网上查看资料讨论请教，了解线索二叉树的相关知识和使用方法。

 

参考文献

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

[2] 罗建军,朱丹君,顾刚,刘路放.C++程序设计教程(第二版).北京：清华大学出版社,2007

[3] 谭浩强.C程序设计(第三版).北京:清华大学出版社,2005

[4] 何钦铭,严晖.C语言程序设计. 北京: 高等教育出版, 2008

[5] 徐翠霞 崔玲玲.《数据结构》. 北京：中国电力出版社：2006.

[6] 谭浩强. 《c++程序设计》. 北京：清华大学出版社，2004

[7] 李春葆.数据结构(C语言版)习题与解析[M]. 北京：清华大学出版社.2002

AI创作