数据结构课程设计之树与二叉树的转换大学论文

数据结构——树、森林和⼆叉树之间的转换树转换⼆叉树（1）加线。

在所有兄弟结点之间加⼀条连线。

（2）去线。

树中的每个结点，只保留它与第⼀个孩⼦结点的连线，删除它与其它孩⼦结点之间的连线。

（3）层次调整。

以树的根节点为轴⼼，将整棵树顺时针旋转⼀定⾓度，使之结构层次分明。

（注意第⼀个孩⼦是结点的左孩⼦，兄弟转换过来的孩⼦是结点的右孩⼦）⼝诀：兄弟相连，长兄为⽗，孩⼦靠左。

核⼼：左孩⼦，右兄弟森林转换⼆叉树（1）把每棵树转换为⼆叉树。

（2）第⼀棵⼆叉树不动，从第⼆棵⼆叉树开始，依次把后⼀棵⼆叉树的根结点作为前⼀棵⼆叉树的根结点的右⼦树，⽤线连接起来。

⼆叉树转树是树转换为⼆叉树的逆过程。

还原结点A的孩⼦，结点A的左孩⼦开始，⼀直向右⾛，这些结点就是结点A的孩⼦，遇见顺序就是它们作为结点A孩⼦的顺序。

（1）加线。

若某结点X的左孩⼦结点存在，则将这个左孩⼦的右孩⼦结点、右孩⼦的右孩⼦结点、右孩⼦的右孩⼦的右孩⼦结点…，都作为结点X的孩⼦。

将结点X与这些右孩⼦结点⽤线连接起来。

（2）去线。

删除原⼆叉树中所有结点与其右孩⼦结点的连线。

（3）层次调整。

⼆叉树转森林假如⼀棵⼆叉树的根结点有右孩⼦，则这棵⼆叉树能够转换为森林，否则将转换为⼀棵树。

在⼆叉树种A有右⼦树上向右的⼀连串结点都是A的兄弟，那么就把兄弟分离，A的每个兄弟结点作为森林中树的根结点。

（1）从根结点开始，若右孩⼦存在，则把与右孩⼦结点的连线删除。

再查看分离后的⼆叉树，若其根结点的右孩⼦存在，则连线删除…。

直到所有这些根结点与右孩⼦的连线都删除为⽌。

（2）将每棵分离后的⼆叉树转换为树。

数据结构学院：班级：学号：姓名：一、摘要数据结构是计算机专业最基础也是最重要的学科之一。

它和程序设计一起未计算科学其他后继课程的学习奠定了基础。

在计算机广泛普及的今天，其应用几乎涵盖了人类社会的所有领域，而且在航空航天、军事、科学计算、信息检索、生产线控制等一些关键领域已经高度依赖计算机系统，而数据结构在其中起着无可替代的应用。

其实生活中也有好多应用数据结构的小事，只要留心观察，它无处不在。

例如：我们的家族图谱，遗传病图谱，公司成员职位一览表都应用到了数据结构中的树；还有我们小的时候玩的丢手绢游戏其实也用到了数据结构中的循环列表，而且在换人时用到了循环列表的插入和删除。

所以说，数据结构与我们的生活息息相关，学习和掌握好数据结构对我们处理日常生活中遇到的问题一定会有很大的帮助。

关键字数据结构，计算机专业，学科，应用,逻辑结构,存储结构,算法优化。

二、什么是数据结构数据结构在计算机科学界至今没有标准的定义。

个人根据各自的理解的不同而有不同的表述方法：Satartia Sahibah在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。

这些联系可以通过定义相关的函数来给出。

”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。

Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。

”Robert L.Ruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。

其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。

数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。

目录1 问题描述 (1)2 需求分析 (1)3 概要设计 (1)3．1模块划分……………………………………………………….错误!未定义书签。

4 详细设计.................................................................................... (6)4．1主要模块流程图 (7)4．2 数据类型的定义 (8)4．3 主要模块的算法描述 (8)5 测试分析 (14)6 课程设计总结 (17)参考文献 (18)附录（源程序清单） (19)1 问题描述建立一棵二叉树；再以广义表表示法输出这棵二叉树；然后对该树进行先序、中序、后序遍历及层次遍历。

要求：（1）采用二叉链表存储二叉树；（2）先序、中序、后序遍历设计非递归算法。

2 需求分析二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。

他的应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二叉树在排序、查找、大规模数据索引方面有很多很多应用。

而且二叉树排序是简单算法排序中速度最快的。

在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点逐一进行某种处理。

这就提出了遍历二叉树。

根据遍历的方向的选择，就有了前序遍历，中序遍历和后序遍历以及层次遍历二叉树。

因此掌握二叉树的各种遍历二叉树算法非常重要，而且高效的遍历算法能够节省很多成本。

3 概要设计3．1模块划分本程序包括七个模块：（1）主程序模块void main(){初始化；以广义表表示法输出；建立二叉树；非递归先序遍历二叉树并输出；非递归中序遍历二叉树并输出；非递归后序遍历二叉树并输出；层次遍历二叉树并输出；}（2）以广义表表示法输出——实现对二叉树的输出（3）二叉树建立模块——建立一个二叉树并对二叉树进行初始化（4）非递归先序遍历模块——实现对二叉树的递归先序遍历并输出（5）非递归中序遍历模块——实现对二叉树的递归中序遍历并输出（6）非递归后序遍历模块——实现对二叉树的递归后序遍历并输出（7）层次遍历模块——实现对二叉树的层次遍历并输出4 详细设计4．1主要模块流程图主流程图建立一棵二叉树以广义表表示法输出一棵二叉树非递归先序遍历非递归中序遍历非递归后序遍历层次遍历4．2数据类型的定义（1）二叉树的二叉链表存储类型typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;（2）栈类型的定义typedef struct SqStack/*定义一个顺序栈*/{BiTNode *base;BiTNode *top;int stacksize;}SqStack;void InitStack(SqStack *S)/*栈的初始化*/{S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));S->top=S->base;S->stacksize=STACK_INIT_SIZE;}void Push(SqStack *S,BiTNode e)/*入栈算法*/{if(S->top-S->base>=S->stacksize){S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)=e;S->top++;}BiTNode Pop(SqStack *S)/*出栈算法*/{S->top --;return *S->top;}int StackEmpty(SqStack *S)/*判栈空*/{if(S->top == S->base )return 1;elsereturn 0;}4．3主要模块的算法描述（1）主函数void main(){BiTree Ta;int a=1;printf("请创建树\n");Ta=CreateBiTree();printf("广义表表示法输出二叉树\n");printfBTree(Ta);printf("\n");printf(" 请选择：\n");printf(" （1）先序遍历\n");printf(" （2）中序遍历\n");printf(" （3）后序遍历\n");printf(" （4）层次遍历\n");printf(" （0）结束程序\n");while(a){scanf("%d",&a);if(a==1){（2）建立二叉树BiTree CreateBiTree()/*以二叉链表的存储方式建立一棵二叉树*/ {char p;BiTree T;scanf("%c",&p);if(p=='#')T=NULL;else{T=(BiTNode *)malloc(sizeof(BiTNode));T->data=p;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}return (T);}（3）用广义表表示法输出二叉树void printfbitree(t)/*用广义表表示法输出二叉树*/{if(t!=NULL){printf("%c",t->data);if(t->lchild!=NULL||t->rchild!=NULL){printf("(");printfbitree(t->lchild);if(t->rchild!=NULL)printf(",");printfbirree(t->rchild);printf(")");}}}（4）非递归先序遍历二叉树void PreOrder(BiTree T)/*非递归先序遍历二叉树*/ {SqStack S;BiTree p=T;InitStack(&S);if(p)Push(&S,*p);while(!StackEmpty(&S)){p=(BiTNode *)malloc(sizeof(BiTNode));*p=Pop(&S);printf("%c",p->data);if(p->rchild)Push(&S,*p->rchild);if(p->lchild)Push(&S,*p->lchild);}}（5）非递归中序遍历二叉树void InOrder(BiTree T)/* 非递归中序遍历二叉树*/ {SqStack S;BiTree p=T;InitStack(&S);while(p||!StackEmpty(&S)){if(p){Push(&S,*p);p=p->lchild;}else{p=(BiTNode *)malloc(sizeof(BiTNode));*p=Pop(&S);printf("%c",p->data);p=p->rchild;}}}（6）非递归后序遍历二叉树void PostOrder(BiTree T)/ *非递归后序遍历二叉树*/ SqStack S;BiTNode p, *l, *r;InitStack(&S);Push(&S, *T);while(!StackEmpty(&S)){p = Pop(&S);l = p.lchild;r = p.rchild;if (l == NULL && r == NULL){printf("%c", p.data);}else{p.lchild = NULL;p.rchild = NULL;Push(&S, p);if (r != NULL) Push(&S, *r);if (l != NULL) Push(&S, *l);}}}（7）层次遍历void LevelOrderTraverse(BiTree T) /*层序遍历*/ {BiTree Q[STACK_INIT_SIZE];int front=0,rear=0;BiTree p;if(T){ //根结点入队Q[rear]=T;rear=(rear+1)%STACK_INIT_SIZE;}while(front!=rear){p=Q[front]; //队头元素出队front=(front+1)%STACK_INIT_SIZE;printf("%c",p->data);if(p->lchild){ //左孩子不为空，入队Q[rear]=p->lchild;rear=(rear+1)%STACK_INIT_SIZE;}if(p->rchild){ //右孩子不为空，入队Q[rear]=p->rchild;rear=(rear+1)%STACK_INIT_SIZE;}}}5 测试分析6 课程设计总结通过这次课程设计使我充分的理解了从建立二叉树到输出二叉树再遍历二叉树的基本原理与算法，尤其是深刻的学习了二叉树遍历的非递归实现的算法。

数据结构课程设计课程名称：平衡二叉树的生成院系：信息工程学院年级专业：10级计科学号：学生姓名：指导教师：开题时间： 2010 年 12 月 01 日完成时间： 2010 年 12 月 31 日信息工程学院X X X X X X X数据结构课程设计成绩评定表院系：信息工程学院年级专业：学号：姓名：摘要本篇论文系计科专业10年末课程设计论文，按照相应要求写作而成。

主要讨论的是平衡二叉树的生成问题，借助本程序可以由用户输入数值，并生成平衡二叉树，并可以对数据进行方便的修改和删除添加，任意插入或删除一个结点后仍然要求任然构成平衡二叉树，并按中序遍历输出这棵平衡二叉树。

·本论文共由五个章构成，每个内容独立成章，各章下设相应子章节。

各个章节逐渐递进，分别是：第一章：需求分析第二章系统设计第三章编码第四章测试第五章维护本论文特点：1.论述清楚，目录详尽，可以方便的查询相应章节，方便使用。

2.图文结合，几乎没一个子程序模块都有相应的流程图与之对应，有利于读者理解每个子程序的设计思路。

3.模块分化清晰，每个模块独立成节，又彼此联系，深化了C语言模块化编程的特点。

4.测试模块配合对应的运行截图，真实可信，对读者理解程序的运行情况起到了很大作用。

5.程序清单完整详细，解释详细。

目录第一章需求分析 (1)1.1功能描述­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­11.2数据词典­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­1第二章系统设计 (3)2.1 基本概念介绍­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­3 2.2 总体设计­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­8 2.3 插入结点­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­10 2.4 删除结点­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­11 2.5 中序遍历­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­11 第三章编码 (12)3.1 总体编码­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­123.2 总流程图­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­153.3 以指针T所指结点为根的二叉树作右平衡旋转处理­­­­­­­­­­­­16 第四章测试 (17)4.1 创建二叉树测试­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­174.2 插入结点测试­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­194.3 删除结点测试­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­204.4中序遍历结点测试­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­214.5 先序遍历测试­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­21 第五章维护 (22)5.1维护­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­22第一章需求分析1.1功能描述平衡二叉树是数据结构中一个非常重要的概念。

树与二叉树的转换逻辑设计思路
在树和二叉树之间进行转换时，需要设计一个逻辑思路，以确保正确地转换数据结构。

以下是一个简单的设计思路：
1. 从树到二叉树的转换：
- 创建一个指向树的根节点的指针，并将其作为二叉树的根节点。

- 对于树中的每个节点，将其作为二叉树的左子节点，并将其右子节点设置为null。

如果该节点有多个子节点，则将其后续子节点作为二叉树节点的兄弟节点。

- 对于树中的每个节点及其子节点，递归地执行上述步骤，直到将树完全转换为二叉树。

- 返回转换后的二叉树。

2. 从二叉树到树的转换：
- 创建一个指向二叉树的根节点的指针，并将其作为树的根节点。

- 对于二叉树中的每个节点，将其作为树中的节点，并将其所有兄弟节点设置为二叉树节点的右子节点。

- 对于二叉树中的每个节点及其子节点，递归地执行上述步骤，直到将二叉树完全转换为树。

- 返回转换后的树。

注意事项：
- 在转换过程中，需要考虑到树和二叉树的节点结构，并正确地设置节点之间的连接关系。

- 转换过程中可能需要使用递归算法来处理节点及其子节点。

- 转换后的树和二叉树应该具有相同的数据内容，只是数据结构不同。

- 在转换后，树和二叉树的遍历结果可能具有不同的顺序。

请根据具体的应用场景和要求，对以上的逻辑设计思路进行适当的修改和调整。

数据结构课程设计报告_遍历⼆叉树XXXX⼤学《数据结构》课程设计报告课题名称: 遍历⼆叉树系（院）:专业:班级:组员姓名:学号:指导教师:开课时间: 学年学期摘要树结构在客观世界中⼴泛存在, 如⼈类社会的族谱和各种社会组织机构都可⽤树形象表⽰. 树在计算机领域中也得到⼴泛应⽤,如在编译源程序时, 可⽤树表⽰源程序的语法结构. ⼜如在数据库系统中, 树型结构也是信息的重要组织形式之⼀. ⼀切具有层次关系的问题都可⽤树来描述.针对这样的问题, 我选择了⼆叉树的遍历作为我的课程设计主题, 编写程序, 实现对⼆叉树的遍历. 在本次课程设计中, ⼆叉树的建⽴使⽤了递归算法；在前序、中序和后续遍历的算法中则同时使⽤了递归与⾮递归的算法, 即在这些遍历算法的实现中使⽤了栈结构与队列结构, 提供了6种不同的遍历⽅式, 供使⽤者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使⽤了⾮递归算法. 该程序基本实现了对⼆叉树的遍历, 对于递归与⾮递归算法, 我们应从实际应⽤中体验这些算法的优越性.关键词: 层次关系, ⼆叉树建⽴, 递归与⾮递归, 遍历, 栈, 队列⽬录⼀、问题描述 (1)⼆、需求分析 (1)2.1主功能模块 (1)2.2创建树模块 (1)2.3遍历树模块 (1)三、概要设计 (2)3.1主界⾯设计思想流程图 (2)3.2. 创建⼆叉树 (2)3.2.1⼆叉树创建的思想 (2)3.2.2⼆叉树创建的算法流程图 (2)3.3.先序递归遍历 (3)3.3.1先序递归遍历思想 (3)3.3.2先序递归遍历的算法流程图 (3)3.4.中序递归遍历 (3)3.4.1中序递归遍历思想 (3)3.4.2中序递归遍历的算法流程图 (4) 3.5.后序递归遍历 (4)3.5.1后序递归遍历思想 (4)3.5.2后序递归遍历的算法流程图 (5) 3.6.先序⾮递归遍历 (5)3.6.1先序⾮递归遍历思想 (5)3.6.2先序⾮递归遍历的算法流程图 (6) 3.7.中序⾮递归遍历 (6)3.7.1中序⾮递归遍历思想 (6)3.7.2中序⾮递归遍历的算法流程图 (7) 3.8.后序⾮递归遍历 (7)3.8.1后序⾮递归遍历思想 (7)3.8.2后序⾮递归遍历的算法流程图 (8) 3.9.层序⾮递归遍历 (8)3.9.1层序⾮递归遍历思想 (8)3.9.2层序⾮递归遍历的算法流程图 (9)四、详细设计 (10)4.1界⾯设计 (10)4.2.详细代码分析 (11)4.2.1主模块 (11)4.2.2创建树模块 (12)4.2.3遍历树模块 (13)五、调试分析 (13)5.1.调试结果 (13)5.1.1实验数据 (13)5.1.2创建树界⾯ (14)5.1.3输出结果界⾯ (14)5.2.算法分析 (16)5.2.1时间复杂度 (16)5.2.2空间复杂度 (16)5.3.程序的不⾜ (16)5.3.1程序不⾜之处 (16)六、⼼得体会 (17)七、参考⽂献 (17)⼀、问题描述建⽴⼆叉树, 层序、先序、中序、后序遍历.(⽤递归或⾮递归的⽅法都可以)要求能够输⼊树的各个结点, 并能够输出⽤不同⽅法遍历的遍历序列；分别建⽴⼆叉树存储结构的的输⼊函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数.⼆、需求分析在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系⽆法使⽤简单的线性结构表⽰清楚, ⽐如祖先与后代的关系、整体与部分的关系等. 于是⼈们借鉴⾃然界中树的形象创造了⼀种强⼤的⾮线性结构——树. 树形结构的具体形式有很多种, 其中最常⽤的就是⼆叉树. ⽽⼆叉树的多层次遍历遍历则是⼆叉树的重要内容.本程序⽤Microsoft Visual C++ 6.0编写, 可以实现对⼆叉树的创建、采⽤递归和⾮递归等两种⽅式先序、中序、后序进⾏遍历.2.1主功能模块通过合理的界⾯设计, 根据提⽰信息, 使⽤者可以⽅便快捷地运⾏本程序来完成创建、遍历⼆叉树等操作. 界⾯美观, ⼈性化, 程序智能, 安全性⾼.2.2创建树模块当进⼊程序运⾏界⾯后, 根据提⽰输⼊需要建⽴的⼆叉树, 按照先序次序输⼊各个结点的值, 完成⼆叉树的建⽴.2.3遍历树模块实现对该⼆叉树的先序递归遍历、先序⾮递归遍历、中序递归遍历、中序⾮递归遍历、后序递归遍历、后序⾮递归遍历、层序⾮递归遍历等⽅式的遍历操作, 并输出各遍历序列.三、概要设计3.1主界⾯设计思想流程图3.2. 创建⼆叉树3.2.1⼆叉树创建的思想(1)定义⼆叉树结点值的类型为字符型.(2)结点个数不超过10个.(3)按先序次序输⼊, 构造⼆叉链表表⽰的⼆叉树T, 空格表⽰空树. 相关函数如下:void CreateBiTree(BiTree &T)3.2.2⼆叉树创建的算法流程图3.3.先序递归遍历3.3.1先序递归遍历思想若⼆叉树为空, 则空操作；否则(1)访问根结点；(2)先序遍历左⼦树；(3)先序遍历右⼦树. 相关函数如下: void PreOrderTraverse(BiTree T) 3.3.2先序递归遍历的算法流程图3.4.中序递归遍历3.4.1中序递归遍历思想若⼆叉树为空, 则空操作；否则(1)中序遍历左⼦树；(2)访问根结点；(3)中序遍历右⼦树. 相关函数如下: void InOrderTraverse(BiTree T) 3.4.2中序递归遍历的算法流程图3.5.后序递归遍历3.5.1后序递归遍历思想若⼆叉树为空, 则空操作；否则(1)后序遍历左⼦树；(2)后序遍历右⼦树；(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)3.6.先序⾮递归遍历3.6.1先序⾮递归遍历思想(1)访问结点的数据域；(2)指针指向p的左孩⼦结点；(3)从栈中弹出栈顶元素；(4)指针指向p的右孩⼦结点. 相关函数如下: void NRPreOrder(BiTree bt)3.7.中序⾮递归遍历3.7.1中序⾮递归遍历思想(1)指针指向p的左孩⼦结点；(2)从栈中弹出栈顶元素；(3)访问结点的数据域；(4)指针指向p的右孩⼦结点. 相关函数如下: void NRInOrder(BiTree bt)3.7.2中序⾮递归遍历的算法流程图3.8.后序⾮递归遍历3.8.1后序⾮递归遍历思想若⼆叉树为空, 则空操作；否则引⼊栈和标记模拟递归⼯作栈, 初始时栈为空. 相关函数如下: void NRPostOrder(BiTree bt);3.8.2后序⾮递归遍历的算法流程图3.9.层序⾮递归遍历3.9.1层序⾮递归遍历思想(1)访问该元素所指结点.(2)若该元素所指结点的左右孩⼦结点⾮空, 则该元素所指结点的左孩⼦指针和右孩⼦指针顺序⼊队. 相关函数如下: void LevelOrderTraverse(BiTree T)3.9.2层序⾮递归遍历的算法流程图四、详细设计4.1界⾯设计图4-1 系统运⾏主界⾯图4-2 创建⼆叉树界⾯图4-3 ⼆叉树递归遍历界⾯4.2.详细代码分析4.2.1主模块本模块定义了系统运⾏主界⾯的相关内容和相关操作函数, 源代码如下: void main(){BiTree T;T=NULL;int select;//cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"< while(1){cout<<"\n\n请选择要执⾏的操作:\n";cout<<"1.创建⼆叉树\n";cout<<"2.⼆叉树的递归遍历算法（前、中、后）\n";cout<<"3.⼆叉树的层次遍历算法\n";cout<<"4.⼆叉树的⾮递归遍历算法（前、中、后）\n";cout<<"0.退出\n";cin>>select;switch(select){case 0:return;case 1:cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"< CreateBiTree(T);break;case 2:if(!T) cout<<"未建⽴树, 请先建树！";else{cout<<"\n先序遍历:\n";PreOrderTraverse(T);cout<<"\n中序遍历:\n";InOrderTraverse(T);cout<<"\n后序遍历:\n";PostOrderTraverse(T);}break;case 3:cout<<"\n层序遍历:\n";LevelOrderTraverse(T);break;case 4:if(!T) cout<<"未建⽴树, 请先建树！";else{cout<<"\n先序遍历:\n";NRPreOrder(T);cout<<"\n中序遍历:\n";NRInOrder(T);cout<<"\n后序遍历:\n";NRPostOrder(T);}break;default:cout<<"请确认选择项:\n";}//end switch}//end while}4.2.2创建树模块源代码如下:void CreateBiTree(BiTree &T){//按先序次序输⼊, 构造⼆叉链表表⽰的⼆叉树T, 空格表⽰空树// if(T) return;char ch;ch=getchar(); //不能⽤cin来输⼊, 在cin中不能识别空格.if(ch==' ') T=NULL;else{if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}4.2.3遍历树模块本模块包括了各种遍历⼆叉树的函数, 源代码如下:void PreOrderTraverse(BiTree T) //⼆叉树的先序遍历(递归)成员函数声明void InOrderTraverse(BiTree T) //⼆叉树的中序遍历(递归)成员函数声明void PostOrderTraverse(BiTree T) //⼆叉树的后序遍历(递归)成员函数声明void LevelOrderTraverse(BiTree T) // ⼆叉树的层序遍历(⾮递归)成员函数声明void NRPreOrder(BiTree bt) // ⼆叉树的先序遍历(⾮递归)成员函数声明void NRInOrder(BiTree bt) //⼆叉树的中序遍历(⾮递归)成员函数声明void NRPostOrder(BiTree bt) //⼆叉树的后序遍历(⾮递归)成员函数声明五、调试分析5.1.调试结果5.1.1实验数据这棵树是随机画的, 由数据结构知识, 按照先序次序输⼊各个节点的值为: ABD###CEG###F#H##(此处#代表空格). 在程序中输⼊这些节点, 创建树, 如下图:5.1.2创建树界⾯图5-1 创建树界⾯5.1.3输出结果界⾯输⼊2, 输出该⼆叉树递归遍历算法的遍历结果, 结果如下:输⼊3, 输出该⼆叉树层序遍历算法的遍历结果, 结果如下:输⼊4, 输出该⼆叉树⾮递归遍历算法的遍历结果, 结果如下:。

《数据结构》课程设计--二叉排序树调整为平衡二叉树2013-2014学年第一学期《数据结构》课程设计报告题目：二叉排序树调整为平衡二叉树专业：网络工程班级：二姓名：汪杰指导教师：刘义红成绩：计算机与信息工程系2013年 1 月 2日目录1、问题描述………………………………………2、设计思路(数学模型的选择) ……………3、二叉排序树和平衡二叉树定义…………………………4、程序清单……………………………5.程序功能说明……………………………5.运行与调试分析………………………6.总结…………………………………1.问题描述输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树，运行并进行调试。

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

具体步骤如下：⑴每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；⑵若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；⑶判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；⑷如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；3.二叉排序树和平衡二叉树定义二叉排序树二叉排序树（Binary Sort Tree）又称二叉查找树。

二叉树和树的转换算法二叉树和树之间的转换算法涉及将一个数据结构转换为另一个数据结构的过程。

在这里，我们将讨论将树转换为二叉树和将二叉树转换为树的算法。

首先，让我们来讨论将树转换为二叉树的算法。

树是一种非线性数据结构，它包含一个根节点以及零个或多个子树，每个子树也是一棵树。

而二叉树是一种特殊的树，每个节点最多有两个子节点。

因此，将树转换为二叉树的算法需要考虑如何安排节点的子节点，以便符合二叉树的定义。

一种常见的将树转换为二叉树的算法是使用前序遍历。

具体步骤如下：1. 从树的根节点开始，将其作为二叉树的根节点。

2. 对于树的每个子树，将其第一个子节点作为二叉树的左子节点，将其余的子节点作为左子节点的右子节点。

3. 递归地对每个子树执行上述步骤，直到整棵树都被转换为二叉树。

接下来，让我们来讨论将二叉树转换为树的算法。

二叉树是一种特殊的树，每个节点最多有两个子节点。

而树是一种非线性数据结构，每个节点可以有任意数量的子节点。

因此，将二叉树转换为树的算法需要考虑如何将二叉树的节点重新组织成树的节点。

一种常见的将二叉树转换为树的算法是使用后序遍历。

具体步骤如下：1. 从二叉树的根节点开始，将其作为树的根节点。

2. 对于二叉树的每个节点，如果该节点有右子节点，将其右子节点作为树节点的子节点。

3. 递归地对每个节点执行上述步骤，直到整棵二叉树都被转换为树。

需要注意的是，在进行树和二叉树的转换时，可能会涉及到节点的重新连接和指针的调整，需要仔细处理节点之间的关系，确保转换后的数据结构仍然保持原始树或二叉树的结构特点。

总之，树和二叉树之间的转换算法涉及到对节点的重新组织和连接，需要根据具体的数据结构特点来设计相应的算法。

希望这些信息能够帮助你理解树和二叉树之间的转换过程。