数据结构课程设计报告之线索二叉树

数据结构课程设计题目: 线索二叉树的生成及其遍历学院：班级：学生姓名：学生学号：指导教师：2012 年12月5日课程设计任务书摘要针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。

增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。

同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。

由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。

实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。

关键词二叉树，中序线索二叉树，中序线索二叉树的遍历目录摘要 ............................................. 错误!未定义书签。

第一章,需求分析.................................. 错误!未定义书签。

第二章,概要设计.. (1)第三章,详细设计 (2)第四章,调试分析 (5)第五章,用户使用说明 (5)第六章,测试结果 (5)第七章,绪论 (6)第八章,附录参考文献 (7)线索二叉树的生成及其遍历第一章需求分析以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。

增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。

同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre指向它的前驱。

由此得到中序遍历建立中序线索化链表的算法本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。

数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。

实验目的1、掌握用递归方法实现二叉树的遍历。

2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。

题目：(1)编写二叉树的遍历操作函数。

①先序遍历，递归方法re_preOrder(TREE *tree)②中序遍历，递归方法re_midOrder(TREE *tree)③后序遍历，递归方法re_postOrder(TREE *tree)(2)调用上述函数实现先序、中序和后序遍历二叉树操作。

算法设计分析（一）数据结构的定义要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。

二叉树型存储结构定义为：typedef struct TNode{ char data;//字符型数据struct TNode *lchild,*rchild;//左右孩子指针}TNode,* Tree;（二）总体设计程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。

其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能。

int main()（2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。

int CreateBiTree(Tree &T)（3）先序遍历函数：将所建立的二叉树先序遍历输出。

void PreOrder(Tree T)（4）中序遍历函数：将所建立的二叉树中序遍历输出。

void InOrder(Tree T)（5）后序遍历函数：将所建立的二叉树后序遍历输出。

void PostOrder(Tree T)（三）各函数的详细设计：（1）建立一个二叉树，按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树。

对T动态分配存储空间，生成根节点，构造左、右子树（2）编写先序遍历函数，依次访问根节点、左子结点、右子节点（3）编写中序遍历函数，依次访问左子结点、根节点、右子节点（4）编写后序遍历函数，依次访问左子结点、右子节点、根节点（5）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。

线索二叉树一目的程序从文件中读取每个结点的信息，然后建立一个二叉树。

通过菜单的形式，选择不同的线索化方式，然后再对线索化的二叉树经行遍历并输出对应的结果。

二需求分析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是后续遍历下，当前遍历的结点的指针。

中序线索化二叉树数据结构线索化二叉树是一种针对二叉树的优化方法，通过在二叉树的每个节点上增加线索（即链接）来改善二叉树的遍历效率。

线索化二叉树的目的是在不增加额外空间的情况下，提供二叉树的前驱和后继节点的访问便利。

所谓线索，即指的是将原本为空的左右子节点域或指针改为指向该节点的前驱和后继节点。

根据线索的类型不同，线索化二叉树可分为中序线索二叉树、前序线索二叉树和后序线索二叉树。

中序线索二叉树的线索化过程如下：1.定义一个指向当前访问节点的指针，初始时指向二叉树的根节点。

2.从根节点出发，首先找到二叉树中序遍历的第一个节点（即最左侧叶子节点）。

最左侧节点没有左子节点，所以将其左指针指向该节点的前驱节点（即中序遍历的前一个节点）。

3.对于二叉树中的每个节点，如果其左子节点为空，则将其左指针指向该节点的前驱节点。

4.将节点的前驱节点（即中序遍历的前一个节点）的后继节点指针指向该节点。

5.如果节点的右子节点为空，则将其右指针指向该节点的后继节点。

6.最后一个节点的后继节点指针为空。

通过线索化，可以使得每个节点的左子节点指向它在中序遍历中的前驱节点，右子节点指向它在中序遍历中的后继节点。

这样，在遍历二叉树时，可以更加高效地找到前驱和后继节点。

```pythonclass ThreadedBinaryTreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = Noneself.is_left_thread = Falseself.is_right_thread = False```在线索化二叉树中，除了普通的左右子节点指针left和right外，还需增加字段is_left_thread和is_right_thread来指示左右指针是否为线索。

对于线索化二叉树，一个节点的线索是指它的左/右子节点为空时，指向中序遍历的前/后一个节点的指针。

数据结构课程设计报告题目：线索二叉树的应用院（系）：计算机工程学院专业：嵌入式系统软件设计方向班级：嵌入式109（1）学生：黄江彬指导教师：寇海洲殷路邱军林孙成富2010年12月目录1.设计目的 (3)2.总体设计 (3)2.1首先创建一个线索二叉树 (3)2.2功能函数的实现 (4)3.调试分析 (7)4.测试结果 (7)5课程设计小结. (10)1.设计目的线索二叉树的应用：创建线索二叉树，实现二叉树的建立，插入，删除，恢复线索的算法。

2.总体设计实现过程和步骤提示：2.1首先创建一个线索二叉树2.1.1功能说明：程序首先显示创建线索二叉树的界面，并等待用户输入命令(见图1-1所示)。

假如用户输入ABCE##F##D##G##，程序将在显示屏上输出运算结果（见图1-2所示）。

图1-1图1-22.1.2创建线索二叉树的程序代码：//创建二叉树ABD#GJ##K##E##C#FH##IL### ABCD##E###F#GH##I#J#K## void Creat(Bitree *p) //指向指针的指针{char ch=getchar();if(ch=='#')(*p)=NULL;else{//Bitree k;*p=(Bitreenode *)malloc(sizeof(Bitreenode));(*p)->data=ch;Creat(&(*p)->lchild);Creat(&(*p)->rchild);}//return 1;}2.1.3创建线索二叉树系统菜单实现提示：（1）.遇“#”则该结点为空；(2).直接从键盘获取字符串.2.2功能函数的实现2.2.1二叉树的遍历2.2.1.1功能说明：对用户输入的二叉树进行遍历2.2.1.2二叉树的遍历程序代码：//先序遍历void First(Bitree p){if(p){printf("%2c",p->data);First(p->lchild);First(p->rchild);}}//中序遍历void Middle(Bitree p){if(p){Middle(p->lchild);printf("%2c",p->data);Middle(p->child);}//后序遍历void Last(Bitree p){if(p){Last(p->lchild);Last(p->rchild);printf("%2c",p->data);}}2.2.1.3遍历二叉树功能实现提示：（1）.用户输入二叉树后函数自动对所输入二叉树进行遍历。

线索化二叉树遍历实验报告09040502班学号:052415 朱博凯一、需求分析（1）本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！（2）程序功能：遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。

（3）测试数据：ABC##DE#G##F###；二、概要设计为实现本程序功能，应以二叉树结构存储二叉树，而为了实现非递归遍历二叉树的功能，应以带头节点的栈存储二叉树。

1、二叉树的抽象数据类型定义ADT BinaryTree{数据对象D：D是具有相同特性的数据元素集合。

数据关系R：如D=Ф，则R=Ф，称BinaryTree为空二叉树；如D≠Ф，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；（2）如D-{root}≠Ф,则存在D-{root}={D1,Dr},且D1∩Dr=Ф;（3）如D1≠Ф,则D1中存在唯一元素x1,<ROOT,X< SPAN>1>∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，<ROOT,X< SPAN>r>∈H,且存在Dr上的关系Hr包含于H；H={<ROOT,X< SPAN>1>,<ROOT,X< SPAN>r>,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。

基本操作P：InitBiTree(&T);操作结果：构造空二叉树T.DestroyBiTree(&T);初始条件：二叉树T存在。

操作结果：销毁二叉树T.CreateBiThrTree(&T);操作结果：先序构造二叉树T,Ltag和RTag初始置为Link.PreOrderTraverse(T );初始条件：二叉树T存在。

操作结果：先序递归遍历T。

湖南涉外经济学院课程设计报告课程名称：数据构造报告题目：二叉树的基本操作学生姓名：肖琳桂、康政、张小东、张帆所在学院：信息科学与工程学院专业班级：软工本 1402学生学号： 1 、02、14、08指导教师：李春庭2015 年12月31日课程设计任务书报告题目二叉树的基本操作达成时间 2 周肖琳桂专业软工本学生姓名指导教师李春庭职称讲课老师康政班级1402整体设计要乞降主要功能设计一个程序，实现二叉树的创立以及二叉树的遍历（包含先序遍历、中序遍历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求：1．二叉树以二叉链表储存，结点数据种类采纳字符表示，按二叉树的先序遍历序列创立。

2．用文本编写器编写一个的文件, 包含 3 个以上创立按二叉树的先序遍历序列( 即序列中包含空树节点 ) ，每个序列长度许多于10 个，在运转程序时自动载入，也能够由键盘输入创立二叉树。

|3．菜单功能：创立二叉树（二级菜单说明选择文件中的第几个，输出创立二叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序和层次遍历结果），结点的孩子信息，退出系统。

工作内容实时间进度安排第 17周：周1--- 周2 ：立题、论证方案设计周3--- 周5 ：程序设计及程序编码第 18周：周1--- 周3 ：程序调试周 4--- 周 5 ：查收辩论摘要本课程设计主要说明怎样在C++编程环境下实现二叉树的遍历，遍历方式包括 : 二叉树的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。

同时，此次课程设计还包含了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的成立。

以经过此次课程设计，使学生充足掌握树的基本操作，以及对线性储存构造的理解。

同时，在对树的遍历的操作过程中，相同是运用递归的方式实现遍历，在对树实现层次操作的时候，要求用循环行列的操作方式来实现层次遍历。

此次课程设计对数据构造内容综合性的运用的要求较高。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

线索二叉树应用实验实验报告实验目的（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的左子树的（先序）最后一个结点的右孩子插入进去。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。