数据结构课程设计
设计说明书
线索二叉树的实现
学生姓名
学号
班级
成绩
指导教师曹记东
计算机科学与技术系
2010年9月10日
数据结构课程设计评阅书
题目线索二叉树的实现
学生姓名学号
指导教师评语及成绩
指导教师签名：
年月日答辩评语及成绩
答辩教师签名：
年月日教研室意见
总成绩：
室主任签名：
年月日
课程设计任务书
2010—2011学年第1学期
专业：计算机科学与技术学号：姓名：
课程设计名称：数据结构课程设计
设计题目：线索二叉树的实现
完成期限：自2010 年8 月30 日至2010 年9 月10 日共 2 周
设计内容：
n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉树称为线索二叉树(Threaded BinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
运用VC++编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。
要求:
1）阐述设计思想，画出流程图；
2）任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树；
3）说明测试方法，写出完整的运行结果；
4）从时间、空间对算法分析；
5）较好的界面设计；
6）编写课程设计报告。
以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。
指导教师（签字）：教研室主任（签字）：
批准日期：年月日
摘要
设计了一个对线索二叉树实现遍历的软件，该软件可以实现对线索二叉树分别进行先序遍历、中序遍历、后序遍历。这种遍历方法是以线索为根本，利用该软件，用户可以方便的查找树中任意结点的前驱和后继，给用户带来了方便。该软件采用了VC6.0作为软件开发环境，实现对线索二叉树的遍历。操作简单，界面清晰，易于用户接受。
关键词：线索；先序遍历；中序遍历；后序遍历
目录
1 课题描述 (1)
2 设计过程 (2)
2.1任务分析及课题分析 (2)
2.2 流程图 (2)
2.4算法分析 (11)
2.5 测试结果 (12)
3 总结 (14)
参考文献 (15)
1 课题描述
本次课程设计的题目是线索二叉树的实现，该二叉树是以线索链表的存储方式来存储的，该结点有五个域：数据域、左孩子、右孩子、前驱、后继，其中指向其前驱和后继的指针叫做线索，这三种遍历（先序遍历、中序遍历、后序遍历）是根据线索来遍历二叉树的，对二叉树以某种次序的遍历使其成为线索二叉树的过程叫做线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。
2 设计过程
2.1任务分析及课题分析
此任务设计了一个对线索二叉树进行先序遍历、中序遍历、后序遍历这三种遍历，先序遍历是按（先根再左后右），中序遍历（先左再中后右），后序遍历（先左再右后中），这种遍历方法是以线索为根本，该二叉树是以二叉链表为存储结构，在遍历的过程实质是修改空指针的过程，把空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到。
2.2 流程图
线索二叉树的实现主菜单
先序建立二叉树先
序
遍
历
线
索
二
叉
树
中
序
遍
历
线
索
二
叉
树
后
序
遍
历
线
索
二
叉
树
图2.1线索二叉树的实现总流程图
开始
P!=T
输出p-
>data
p=p->lchild
p->ltag==0
输出p-
>data
p->rtag=1&&p-
>rchild!=T
p=p->rchild;输出（p-
>data）
p=p->rchild N
return OK N
Y
N
Y
Y
图2.2先序遍历线索二叉树流程图
开始
P!=T
P->ltag==0
Y
p=p->lchild
输出p=p-
data
p->rtag=1&&p->rchild!=T
p=p->rchild,输出（p->data)
p=p->rchild N
Y N
return
OK
N
Y
图2.3中序遍历线索二叉树流程图
开始
P=T
p->ltag==link||p->rtag==link
p->ltag==link
p=p->lchild
p->rtag==link
p=p->rchild
输出P->data
结束
N
Y
Y
Y
N
N
图2.4 后序遍历线索二叉树流程图
p->rtag==link
P!=T
开始
pre->rtag==th read||p=pre->rchild
Y
p=pre->rchild
N
p=pre
Y
p->ltag==link ||p->rtag==li nk
p->ltag==link
Y
p=p->lchild
Y p->rtag==link
p=p->rchild
Y
N
输出p->data
N
p=p->rchild,输出p->data
N
输出p->data
N
return OK
图2.5 后序遍历线索二叉树流程图
2.3 程序实现代码
#include
#include
#include
typedef enum PointerTag{link,thread}; //link==0:指针，thread==1：线索// typedef struct BiThrNode
{
char data;
BiThrNode *rchild, *lchild;
PointerTag ltag,rtag;
}BiThrNode, *BiThrTree;
BiThrTree CreateTree() //先序创建二叉树//
{
BiThrTree T;
char ch;
T=(BiThrNode *)malloc(sizeof(BiThrNode));
ch=getchar();
if( ch == '#' )
T = NULL;
else
{
T= ( BiThrTree )malloc( sizeof( BiThrNode ) );
if( T)
{
T->data = ch;
T->ltag=link;
T->rtag=link;
T->lchild = CreateTree(); // 创建左子树//
T->rchild= CreateTree(); // 创建右子树//
}
}
return T;
}
BiThrTree pre;
void preThreading(BiThrTree p) //先序线索化//
{
if(p){ //访问根节点//
if(!p->lchild){
p->ltag=thread;
p->lchild=pre;
}
if(!p->rchild) //右孩子为空
p->rtag=thread;
if(pre && pre->rtag==thread)
pre->rchild=p; //结点存在且无右孩子
pre=p;
if(p->ltag==link)
preThreading(p->lchild); //左子树存在，访问左子树if(p->rtag==link)
preThreading(p->rchild); //右子树存在，访问右子树}
}
BiThrTree preorderthreading(BiThrTree Thrt,BiThrTree T) //先序遍历二叉树,并将其先序线索化// {
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) //建立头结点//
exit(0);
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 Thrt;
}
void preTraverse(BiThrTree T) //先序遍历线索二叉树//
{
BiThrTree p;
p=T->lchild; //指向左孩子//
printf("%c",p->data);
while (p->rchild!=T)//根左右
{
if (p->ltag==link)
p=p->lchild;
else
p=p->rchild;
printf("%c",p->data);
}
}
void midThreading(BiThrTree p) //中序线索化//
{
if(p){
midThreading(p->lchild); //左子树线索化//
if(!p->lchild){
p->ltag=thread;
p->lchild=pre;
}
if(!pre->rchild){
pre->rtag=thread;
pre->rchild=p;
}
pre=p;
midThreading(p->rchild); //右子树线索化//
}
}
BiThrTree midorderthreading(BiThrTree &Thrt,BiThrTree T) //中序遍历，并将其中序线索化// {
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
exit(0);
Thrt->ltag=link;
Thrt->rtag=thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else{
Thrt->lchild=T;pre=Thrt; //中序遍历进行中序线索化//
midThreading(T);
pre->rchild=Thrt;
pre->rtag=thread;
Thrt->rchild=pre;
}
return Thrt;
}
void midpreTraverse(BiThrTree T) //中序遍历线索二叉树//
{
BiThrTree p;
p=T->lchild;
while(p!=T){ //空树或遍历结束时，P==T//
while(p->ltag==link)
p=p->lchild;
printf("%c",p->data); //访问左子树为空的节点//
while(p->rtag==thread&&p->rchild!=T){
p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
void postThreading(BiThrTree p) //后序线索化//
{
if(p){
postThreading(p->lchild); //左子树线索化//
postThreading(p->rchild); //右子树线索化//
if(!p->lchild){
p->ltag=thread;
p->lchild=pre;
}
if(!pre->rchild){
pre->rtag=thread;
pre->rchild=p;
}
pre=p;
}
}
BiThrTree postorderthreading(BiThrTree &Thrt,BiThrTree T)//后序遍历，并将其后序线索化，// {
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
exit(0);
Thrt->ltag=link;
Thrt->rtag=thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else{
Thrt->lchild=T;pre=Thrt; //后序遍历进行后序线索化//
postThreading(T);
pre->rchild=Thrt;
pre->rtag=thread;
Thrt->rchild=pre;
}
return Thrt;
}
void postTraverse(BiThrTree T) //后序遍历后序线索化二叉树
{
BiThrTree p;
p=T;
while(p->ltag==link||p->rtag==link) //有左孩子先访问左孩子,没有左孩子先访问右孩子
{
while(p->ltag==link)
p=p->lchild;
if(p->rtag==link) //访问左孩子为空的结点的右孩子
p=p->rchild;
}
printf("%c",p->data);
while(p!=T) //p不为根结点
{
if(p->rtag==link) //若p是有兄弟的左孩子
{
if(pre->rtag==thread||p==pre->rchild) //若p是双亲的右孩子或是独生左孩子，则后继为双亲p=pre;
else
{
p=pre->rchild; //后继为双亲的右子树上按照后序遍历访问的第一个结点。
while(p->ltag==link||p->rtag==link)
{
while(p->ltag==link)
p=p->lchild;
if(p->rtag==link)
p=p->rchild;
}
}
}
else
p=p->rchild; //p指向后继
printf("%c",p->data);
}
}
void main() //主函数//
{
BiThrTree T=NULL,pre;
BiThrTree Thrt,p=0;
int b;
while(1)
{
printf("线索二叉树的实现\n");
printf( "1.先序遍历线索化二叉树\n");
printf( "2.中序遍历线索化二叉树\n");
printf( "3.后序遍历线索二叉树\n");
printf( "0.退出程序\n");
printf("输入你的选择：");
scanf("%d",&b);
switch(b){
case 1:
fflush(stdin);
printf("先序建立二叉树:");
T=CreateTree();
printf("先序遍历线索化二叉树:");
pre=preorderthreading(Thrt,T);
preTraverse(pre);
printf("\n");
break;
case 2:
fflush(stdin);
printf("先序建立二叉树:");
T=CreateTree();
printf("中序遍历线索化二叉树:");
pre=midorderthreading(Thrt,T);
midpreTraverse(pre);
printf("\n");
break;
case 3:
fflush(stdin);
printf("先序建立二叉树:");
T=CreateTree();
printf("后序遍历线索化二叉树:");
pre=postorderthreading(Thrt,T);
postTraverse(pre);
printf("\n");
break;
case 0:
printf("退出程序!");
exit(0);
break;
}
}
}
2.4算法分析
遍历二叉树的算法中的基本操作是访问结点，无论是按哪种次序进行遍历，对含有N 个结点的二叉树，其时间复杂度均为O（n）,所需辅助空间微微遍历过程中栈的最大容量，及树的深度，最坏情况下为n,则空间复杂度也为O（n）。若在程序中采用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则采用线索链表作存储结构。
2.5 测试结果
调试和运行各个函数的结果如图2.6、2.7、2.8、2.9
图2.6 先序遍历线索二叉树运行结果
图2.7中序遍历线索二叉树运行结果
图2.8后序遍历线索二叉树运行结果
图2.9 结束标志
3 总结
课程设计的过程是艰辛的，但是收获确实很大的。这次课程设计我主要使用所学的C 语言和数据结构的一些知识，综合起来才完成了这个软件的设计。
首先，综合课程设计让我把以前学习到的知识得到了进一步的巩固和进一步的提高认识，对已有的知识有了进一步的理解，再次，我在课程设计碰到了一些问题，我通过查阅相关书籍资料，通过自己专研和老师的指导，特别是得到了老师的指导，才让我认识到了自己对以前所学知识的不足。
最后，通过这次课程设计，让我在以后的学习中明白了自己的弱点，掌握那些不足之处，锻炼自己的思维能力，开拓自己的思维，进一步提高自己的编程能力。
再次衷心感谢曹老师对我的指导和同学对我的帮助!
参考文献
[1] 何钦铭, 颜辉. C语言程序设计.北京. 高等教育出版社.2008
[2] 严蔚敏，数据结构（C语言版）.清华大学出版社.2009
[3] 李春葆.数据结构(C语言版)习题与解析[M]. 北京：清华大学出版社.2002
[4] 钱能.C++程序设计教程[M]. 北京：清华大学出版社.2003
专业基础综合课程设计 设计说明书 线索二叉树的实现 学生姓名xxx 学号 班级 成绩 指导教师 数学与计算机科学学院 2012 年 6月 29日 专业基础综合课程设计评阅书
题目线索二叉树的实现 学生姓名学号 指导教师评语及成绩 成绩：教师签名：年月日答辩教师评语及成绩 成绩：教师签名：年月日教研室意见 总成绩：室主任签名：年月日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。
课程设计任务书 2011—2012学年第2学期 专业：计算机应用技术学号：姓名： 课程设计名称：专业基础综合课程设计 设计题目：线索二叉树的实现 完成期限：自2012 年 6 月18 日至2012 年6月29 日共 2 周 设计内容： n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉树称为线索二叉树(Threaded BinaryTree)。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 运用VC++编写一个程序实现前序线索二叉树、中序线索二叉树和后序线索二叉树，其中遍历要求用先左后右的递归或非递归算法来实现。 要求: 1）阐述设计思想，画出流程图； 2）任意建立一棵二叉树，采用前序、中序、后序三种方法线索化二叉树； 3）说明测试方法，写出完整的运行结果； 4）从时间、空间对算法分析； 5）较好的界面设计； 6）编写课程设计报告。 以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师（签字）：教研室主任（签字）： 批准日期：2012年 6 月18 日 摘要
/* *题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。 * 编写前序遍历、中序遍历、后序遍历、层次遍历程序。 * 编写求二叉树的叶结点数、总结点数和深度的程序。 * 设计一个选择式菜单，以菜单方式选择下列操作。 * 二叉树子系统 * *************************** **** * * 1 -- 建二叉树* * * 2 -- 凹入显示* * * 3 -- 先序遍历* * * 4 -- 中序遍历* * * 5 -- 后序遍历* * * 6 -- 层次遍历* * *7 -- 求叶子数* * *8 -- 求结点数* * *9 -- 求树深度* * *0 -- 返回* * *************************** **** * 请选择菜单号（0--9） */ #include
课程设计说明书 （数据结构课程设计） 专业:网络工程 课程名称: 数据结构课程设计班级: 网络B11-1 设计题目: 线索二叉树的应用 设计时间: 2013-2-25 至2013-3-8 评语:_________________________________ _________________________________________ _________________________________________ _________________________________________ _________________________________________ 评阅成绩:＿＿＿＿评阅教师:＿＿ 一、问题描述与需求分析 1、问题描述 本实验的问题是建立一个线索二叉树，并实现线索二叉树的插
入、删除、恢复线索等功能。 2、功能需求分析 本程序要实现的功能是： 1. 线索二叉树的建立。 2.线索二叉树的插入。 3.线索二叉树的删除。 4.线索二叉树的恢复。 想要完成上面的功能，我们首先是要知道上面是线索二叉树。我们可以从数据结构的书上找到答案，利用二叉链表的空指针域将空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继。这种改变指向的指针称为线索，加上了线索的二叉链表称为线索链表。 N个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点的在某种遍历次序下的前驱和后继结点的指针，这种加上了线索的二叉链表称为线索链表。相应的二叉树称为线线索二叉树。根据线索二叉树性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树和后续线索二叉树三种，此次课程设计中使用的是中序线索二叉树。 二、概要设计 1、总体设计思路 首先就是要建立一个二叉树，然后再对二叉树进行线索化。
摘要 Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB 对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。 关键词：Matlab；二叉树；数据结构；
ABSTRACT Matlab is used for algorithm development, data visualization, data analysis and numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction；
数据结构课程设计 题目: 线索二叉树的生成及其遍历 学院： 班级： 学生姓名： 学生学号： 指导教师： 2012 年12月5日
课程设计任务书
摘要 针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。 关键词二叉树，中序线索二叉树，中序线索二叉树的遍历
目录 摘要 ............................................ 错误！未定义书签。第一章,需求分析................................. 错误！未定义书签。第二章,概要设计 (1) 第三章,详细设计 (2) 第四章,调试分析 (5) 第五章,用户使用说明 (5) 第六章,测试结果 (5) 第七章,绪论 (6) 第八章,附录参考文献 (7)
线索二叉树的生成及其遍历 第一章需求分析 以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。主要任务： 1.建立二叉树； 2.将二叉树进行中序线索化； 3.编写程序，运行并修改； 4.利用中序线索遍历二叉树 5.书写课程设计论文并将所编写的程序完善。 第二章概要设计 下面是建立中序二叉树的递归算法，其中pre为全局变量。 BiThrNodeType *pre; BiThrTree InOrderThr(BiThrTree T) { /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/ BiThrTree head; head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/ head->ltag=0;head->rtag=1;/*建立头结点*/ head->rchild=head;/*右指针回指*/ if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/ else{head->lchild=T;pre=head; InThreading(T);/*中序遍历进行中序线索化*/ pre->rchild=head; pre->rtag=1;/*最后一个结点线索化*/ head->rchild=pre; }; return head; } void InThreading(BiThrTree p) {/*通过中序遍历进行中序线索化*/ if(p)
线索二叉树 一目的 程序从文件中读取每个结点的信息，然后建立一个二叉树。通过菜单的形式，选择不同的线索化方式，然后再对线索化的二叉树经行遍历并输出对应的结果。 二需求分析 1、文件的读入 程序首先要从一个文件中读入结点的信息。故需建立一个文件，在文件中，给出每个结点的信息。 2、菜单的实现 由于需要建立两种不同的线索二叉树，故需要一个菜单，来选择需要进行的操作，并输出操作的结果。 3、树的建立 从文件中，读入每个结点的信息。然后建立起树，然后再对已建立的树进行相应的线索化。 4、树的线索化 根据菜单的选择，对已建立的树经行相对应的线索化。 5、输出遍历的结果 对每种不同的线索化的的树，给出相对应的算法。然后，根据算法把每种遍历的结果输出。 三概要设计 1、主程序模块 (1)主程序模块 int main() { welcome(); //通过welcome（）模块来让用户控制，做线索化的工作。 return 0; }
(2)可线索化单元模块—实现各种线索化的抽象数据类型；通过welcome（）模块来调用每个线索化模块。 2、建立二叉树的模块 bool CreatBinTree(); 函数会根据用户输入的文件名，打开一个存储了树中每个结点的文件，且是用广义表的形式给出结点信息的文件。 操作结果：根据文件中广义表的形式，建立相对应的二叉树，该树的根节点为root。 3、线索化的抽象数据类型 void CreatInThread(); void CreatInThread(Node *current,Node *&front) current是中序遍历下，当前遍历的结点的指针。front是中序遍历下，current结点的前驱的指针。 操作结果：对建立的二叉树完成中序线索化。 void CreatPostThread(); void CreatPostThread(Node *current,Node *&front) current是后续遍历下，当前遍历的结点的指针。front是后续遍历下，current结点的前驱的指针。 操作结果：对已建立的二叉树完成后续线索化。 4、输出结果的抽象数据类型 void InOrder() 操作结果：输出中序线索二叉树的中序遍历的结果。 Node* InFirst(Node *current) current是中序线索二叉树中指向一个结点的指针。 操作结果：返回以current为根的树的中序遍历下的第一个结点的指针。 Node* InNext(Node *current) current是中序线索二叉树中指向一个结点的指针。 操作结果：返回中序遍历下，current结点的后继结点的指针。 void PostOrder() 操作结果：输出后续线索二叉树的后续遍历结果。
中序线索化二叉树数据结构. 当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指针，所以从任一结点出发只能直接找到该结点的左、右孩子。在一般情况下靠它无法直接找到该结点在某种遍历次序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。 与此同时，我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有2n-(n-1)=n+1个空指针。 因此，可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其孩子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为： Lchild Ltag Data Rtag Rchild 其中： 1. Ltag=0时，表示Lchild指向该结点的左孩子； 2. Ltag=1时，表示Lchild指向该结点的线性前驱结点； 3. Rtag=0时，表示Rchild指向该结点的右孩子； 4. Rtag=1时，表示Rchild指向该结点的线性后继结点；
以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树；对二叉树以某种次序遍历将其变为线索二叉树的过程叫做线索化。 中序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索。 例如有如上图所示二叉树，则中序遍历的顺序是：O / J * I + H A G 【参考程序】 #include
数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 题目: 线索二叉树的应用 年级/专业/班: 2010级软件1班 学生姓名: 学号: 1127 开始时间:2011 年12 月9 日完成时间:2011 年12 月23 日课程设计成绩： 1
指导教师签名：年月日 摘要 首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：线索化；先序遍历；中序遍历；后续遍历
线索二叉树的运用 引言 数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树的操作。本课程设计采用的编程环境为Microsoft Visual Stdio 2008。
目录 1需求分析 (3) 2开发及运行平台 (4) 3 概要设计 (5) 4 详细设计 (7) 5 调试分析 (12) 6 测试结果 (13) 7 结论 (18) 致谢 (19) 参考文献 (20) 附录 (21)
平衡二叉树构造方法 平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1) 一、平衡二叉树的构造 在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树 1.调整方法 （1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点 （2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。 2.调整方式 （1）LL型 LL型：插入位置为左子树的左结点，进行向右旋转
由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。 （2）RR型 RR型：插入位置为右子树的右孩子，进行向左旋转 由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。 （3）LR型 LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。 由于在A的左子树B的右子树上插入了结点F，A的平衡因子由1变为了2，成为不平衡的最小二叉树根结点。第一次旋转A结点不动，先将B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。 （4）RL型 RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转；处理情况与LR 类似。
数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include
实验二二叉树的存储结构及各种运算的实现第一题： #include "stdio.h" #include "malloc.h" #define maxsize 66 typedef int datatype; typedef struct node { datatype data ; struct node *lchild,*rchild; } bitree; bitree *Q[maxsize]; bitree *creatree() { char ch; int front,rear; bitree *root,*s; root=NULL; front=1;rear=0; ch=getchar(); while (ch!='#') { s=NULL; if(ch!='@') { s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else { if (s&&Q[front]) if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)
front++; } ch=getchar(); } return root; } preorder(bitree *t) //前{ if (t) { printf(" %c ",t->data); preorder(t->lchild); preorder(t->rchild); } } inorder(bitree *t) //中{ if (t) { inorder(t->lchild); printf(" %c ",t->data); inorder(t->rchild); } } postorder(bitree *t) //后{ if (t) { postorder(t->lchild); postorder(t->rchild); printf(" %c ",t->data); } } int height(bitree *t) //高度{ int hl,hr; if(!t) return 0; else { hl=height(t->lchild); hr=height(t->rchild); return ((hl>hr?hl:hr)+1); } }
二叉树的线索化： 以二叉链表作为存储结构时，只能找到结点的左、右孩子信 息，而不能直接得到结点在任一序列（先序、中序或后序序列） 中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得 到。为了保存这种在遍历过程中得到的信 息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树）， 来存放结点的前驱和后继信息。 作如下规定： ①若结点有左子树，则其lchild 域指示其左孩子，否则令 lchild 域指示其前驱； ②若结点有右子树，则其rchild 域指示其右孩子，否则令 rchild 域指示其后继。 （1）线索链表的结点结构 lchild LTag data RTag rchild 其中： data：数据域； lchild ：左指针域，指向该结点的左孩子； rchild ：右指针域，指向该结点的右孩子； 0lchild域指示结点的左孩子 LTag = 1lchild域指示结点的前驱 0rchild域指示结点的右孩子 RTag = 1rchild域指示结点的后继 请将根据图 1 所示编写一个程序实现构建线索二叉树。 thrt 0 1 bt 0 A 0 0 B 0 0 C 0 1 D 1 0 E 0 1 F 1 1 G 1 1 H 1 0 I 0 1 J 1 1 k 1 图1
#include
青岛理工大学数据结构课程实验报告
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ Visit(T->data);//首先访问根结点 PreOrderTraverse(T->lchild,Visit);//然后递归遍历左子树 PreOrderTraverse(T->rchild,Visit);//最后递归遍历右子树}} //中序遍历时先递归遍历左子树，然后访问根结点，最后递归遍历右子树；后序遍历时先递归遍历左子树，然后递归遍历右子树，最后 访问根结点 3、//先把栈及队列相关操作的头文件包括进来 1）根指针入栈， 2）向左走到左尽头（入栈操作） 3）出栈，访问结点 4）向右走一步，入栈，循环到第二步，直到栈空 //层次遍历时，若树不空，则首先访问根结点，然后，依照其双亲结 点访问的顺序，依次访问它们的左、右孩子结点; 4.首先建立二叉线索存储：包含数据域，左右孩子指针以及左右标志 typedef enum { Link=0,Thread=1 } PointerTag; typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild;//左右孩子指针 PointerTag LTag,RTag;//左右标志 }BiThrNode, *BiThrTree; 建立前驱线索和后继线索，并用中序遍历进行中序线索化，然后最 后一个结点线索化 调 试 过 程 及 实 验 结 果 把测试数据放在f:\\file\\data.txt里，测试数据为：1 2 4 0 0 0 3 5 0 0 0 总访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型
线索二叉树应用实验 实验报告 实验目的 （1）掌握线索二叉树的有关知识。 （2）掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法。 （3）掌握二叉树的线索化算法的设计。 实验运行环境 Visual C++ 实验任务 线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继，而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构，反映了运算对数据结构的设计的影响。因此，首先要了解线索二叉树的结构特点，其中原本为空的指针被修改为前驱和后继指针，使得对左右子树和线索的判断发生了变化。利用线索可以实现某些次序下的前驱和后继。本实验期望能理解线索二叉树的结构特点，实现各前驱和后接算法的求解，并掌握将二叉树转换为线索二叉树的算法，即线索化算法。为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序"btrechar.h"中的函数的形式给出，并假设该库函数中定义了线索二叉树的相关功能，如显示线索二叉树等。 实验内容 第一题： 按先序次序遍历先序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：将二叉树的根结点的指针传给函数。 2：判断当前结点是否为先序遍历的最后一个结点，若是则访问完该结点后结束，否则进入3。
2：判断当前结点是否有左子树，若有的话访问完该结点后访问它的左子树，否则访问它的右子树，返回2。 第二题： 按中序次序遍历中序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：将二叉树的根结点的指针传给函数。 2：判断当前结点是否为中序遍历的最后一个结点，若是则访问完该结点后结束，否则进入3。 3：对于当前结点，先访问该结点的前驱结点并进入第二步，其次访问该结点并进入第二步最后访问该结点的后继结点并进入2。 第三题： 将值为x的结点作为先序线索二叉树T的左子树的（先序）最后一个结点的右孩子插入进去。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：将先序线索二叉树的根结点的指针传给函数。 2：判断当前结点是否为要找的结点P，若是则建立一个新的结点，将新结点作为P的右孩子，并根据新建的结点修改前驱后继关系，否则进入3。 3：指针指向该结点先序遍历的后继，返回2。 第四题： 按中序次序线索化二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt
实验6：二叉树的线索化 一、实验目的 1．掌握线索二叉树的存储结构。 2．掌握将一棵二叉树线索化算法。 3．掌握线索二叉树的遍历算法，理解算法在效率上的改进。 4.将算法用C语言编写完整程序并上机运行，记录实验过程与数据。 二、实验仪器： 1.硬件：Lenovo通用PC机， 2.软件：WINDOWS7，WORD，GCC编译器 三、实验原理： 1.线索化算法
四、实验步骤： 1.设计一个实验样本，取二叉树为： 2.定义一个线索二叉树的结点； 此处填写具体代码 3.按先序的方式建立一棵普通的二叉树；此处填写具体代码 4.将普通二叉树线索化 此处填写具体代码 5.按线性方式遍历线索二叉树 此处填写具体代码 五、数据处理及结论 1.输入：
A↙B↙D↙#↙#↙E↙#↙#↙C↙F↙#↙#↙G↙#↙# 注:每个↙符号代表输入确定，即回车 2.输出： C B E A F C G C B E A F C G 七、思考题： 1.为什么要将一棵二叉树线索化？ 2.为什么在线索化的过程中preNode要使用全局变量？附： #include
按照某种遍历方式对二叉树进行遍历时，可以把该二叉树中所有节点排列为一个线性序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱；除最后一个节点外，每个结点都有且仅有一个直接后继。但是，当以二叉链表作为存储结构时，只能得到结点的左右孩子的信息，而不能直接得到节点在某种遍历序列中的前驱和后继结点，这种信息只有在对二叉树遍历的动态过程中才能得到。 typedef struct ThBiNode { char data; ThBiNode *lchild,*rchild; int ltag,rtag; }ThBiNode,*ThBiTree; 线索二叉树的基本操作 下面以中序线索二叉树为例。 1.建立中序线索二叉树
这也是对二叉树进行线索化的过程，即在遍历过程中，判断当前顶点的左右指针是否为空。若为空，则改为相应的前驱或者后继的线索。基本思路：设指针pre始终指向刚刚访问过的结点，即pre是当前访问结点的前驱。线索化过程中，访问p所指向的结点时，应作如下处理： 1）建立p的前驱线索。 若p->lchild为空，则将其左标志域置为1，并令p->lchild指向其中序前驱pre。 2）建立pre的后继线索。 若pre->rchild为空，则将其右标志域置为1，并令pre->rchild指向p。3）将pre指向p刚刚访问过的结点，即pre=p。这样，在p访问一个新结点时，pre为其前驱结点。 算法代码如下： void InThreading(ThBiNode *p) { if(p) { InThreading(p->lchild); if(!p->lchild) { p->lchild=pre; p->ltag=1;
1在线索二叉树中如何求先序、中序的前驱、后继，为什么后续线索二叉树是不完备的？先序前驱：若左标志为1，则左链为线索，指示其前驱；否则 a) 若该结点是二叉树的根，则其前驱为空； b) 若该结点是其双亲的左孩子或是其双亲的右孩子且其双亲没有左子树，则其前驱为其双亲； c) 若该结点是其双亲的右孩子且其双亲有左子树，则其前驱为其双亲的左子树中的先序遍历列出的最后一个结点。 先序后继：若右标志为1，则右链为线索，指示其后继；否则，如果有左子树则遍历左子树第一个访问的结点，为其后继；如果没有左子树则遍历右子树第一个访问的结点，为其后继； 中序前驱：若左标志为1，则左链为线索，指示其前驱；否则，遍历其左子树最后访问
的结点，为其前驱 中序后继：若右标志为1，则右链为线索，指示其后继；否则，遍历其右子树第一个访问的结点，为其后继 后续后继： a) 若该结点是二叉树的根，则其后继为空； b) 若该结点是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继为其双亲； c) 若该结点是其双亲的左孩子且其双亲有右子树，则其后继为其双亲的右子树中的后序遍历列出的第一个结点。 求后续后继需要知道双亲结点，而二叉链表无法找到双亲，因此不完备：
5如果只想得到一个序列中前k（k>=5）个最小元素的部分排序序列,可以采用哪些排序方法，最好采用哪种排序方法？ 1插入、快速、归并需要全体排序不合适 2起泡、简单选择、堆可以。 堆完成查找总时间：4n+klogn,起泡和简单选择总时间kn,因此堆较好。 5荷兰国旗
问题分析： 这个问题我们可以将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在[0,1]的区域里，由于三色小球之间数量的比不同（此处假设1:2:2），可能前部为[0,0.2)，中部为[0.2,0.6)，后部为[0.6,1]。我们的思路如下：将前部和后部各排在数组的前边和后边，中部自然就排好了。具体的： 设置两个标志位begin和end分别指向这个数组的开始和末尾，然后用一个标志位current从头开始进行遍历： 1）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。