2007-04-25 12:18749人阅读(0) #include
#include
typedef struct bnode
{
char data;
struct bnode*left,*right;
}btree;
btree*creat()
{
btree*t;
char p;
p=getchar();
if(p=='#')
return NULL;
else
{
t=(btree*)malloc(sizeof(btree));
t->data=p;
t->left=creat();
t->right=creat();
return t;
}
}
void preorder(btree*t)
{
if(t!=NULL)
{
printf("%3c", t->data);
preorder(t->left);
preorder(t->right);
}
}
void inorder(btree*t)
{
if(t!=NULL)
{
inorder(t->left);
printf("%3c", t->data);
inorder(t->right);
}
}
void postorder(btree*t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf("%3c", t->data);
}
}
int m=0;
int leaves(btree*t)
{
if(t!=NULL)
{
if(t->left==NULL&&t->right==NULL)
m++;
else
{
leaves(t->left);
leaves(t->right);
}
}
return m;
}
int depth(btree*t)
{
int dep1, dep2;
if(t==NULL)
return0;
else
{
dep1=depth(t->left);
dep2=depth(t->right);
return(dep1>dep2?dep1+1: dep2+1); }
}
int main()
{
printf("输入创建二叉树的字符");
btree*tree_1=creat();
printf("先序遍历");
preorder(tree_1);
printf("");
printf("中序遍历");
inorder(tree_1);
printf("");
printf("后序遍历");
postorder(tree_1);
printf("");
int num=leaves(tree_1);
printf("叶节点的个数:%d", num);
printf("二叉树的深度:%d", depth(tree_1)); }
实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师
实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型
(提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include
课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能： （1）建立二叉排序树； （2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 排序二叉树的建立及其遍历的实现
摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据 组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言 我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归 调用，这将极大的方便算法设计。 1．需求分析 建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。 该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。
/*实验三：二叉树遍历操作验证*/ #include
if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue
数据结构课程设计 题目: 线索二叉树的生成及其遍历 学院： 班级： 学生姓名： 学生学号： 指导教师： 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、检验输入的数据是否可以构成一颗二叉树 二、实验的描述和算法 1、实验描述 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。 2、算法 #include
{ scanf("%c",&e); if(e==' ') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=e; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } /************************前序遍历***********************/ char PreOrderTraverse(BiTree T,char (* Visit)(char e)) { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK; } char Visit(char e) { printf("%5c",e); return OK; } main() {
叉树的随机生成及其遍历 张 zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生50个(不大于1 00且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树 进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。 程序设计 (一) 需求分析： ?问题的定义与要求： 1 、产生50个不大于100且各不相同的随机整数 (由系统的随机函数生成并 对100取模)；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；按层次浏览二叉树结 5、点； 6、退出程序。 ?俞入：所需功能，选项为1?6。 ?输出：按照用户功能选择输出结果。 ?限制：输入的功能选择在1?6之间，否则无回应。 ?模块功能及要求： RandDif(): 生成50个随机不大于100的整数，每次生成不同随机整数。 CreateBitree(): 给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。 NRPreOrder(): 非递归算法的先根遍历。 inOrderTraverse(): 递归算法的中根遍历。 P ostOrderTraverseO：递归算法的后根遍历。 Welcome(): 欢迎窗口。 Menu()：菜单。 Goodbye()：再见窗口。 (二) 概要设计：
首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。生成的二叉树是完全二叉树。 先根遍历的非递归算法： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行2、3 ，至栈空为止。 先根遍历的算法流程图：根结点进栈( a[0]=T->boot,p=a[0] ) 访问结点printf(*p) 右儿子存在则进栈a[i]=(*p).rchild; i++; 左儿子存在则进栈a[i]=(*p).rchild; i++; 栈顶降低top--：i--;p=a[i]; 栈非空while(i>-1) 返回 中根遍历的递归算法流程图： T为空 Return; inOrderTraverse(T->lchild) Printf(T->data) inOrderTraverse(T->rchild) 返回
#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************
课程名称：数据结构实验 实验项目：二叉树的创建及遍历 姓名： 专业：计算机科学与技术 班级： 学号： 计算机科学与技术学院 20 17年11 月22 日
哈尔滨理工大学计算机科学与技术学院实验报告 实验项目名称：二叉树的建立及遍历 一、实验目的 1.熟悉掌握课本二叉树相关理论知识 2.实践与理论相结合，掌握二叉树的应用程序 3.学会二叉树的创建，遍历等其他基本操作的代码实现 二、实验内容 1.二叉树的创建代码实现 2.二叉树先序、中序、后序遍历代码实现 三、实验操作步骤 1.二叉树的建立 （1）树节点的定义 由于每个节点都由数据域和指左子树和右子树的指针，故结构体封装如下： typedef struct node { int data; struct node *left; struct node *right; }Tree,*bitree; （2）建立 采用递归的思想，先建立根再建立左子树，再建立右子树。递归截止条件子树为空，用-1代表树空 *T=(struct node *)malloc(sizeof(struct node));
(*T)->data=a; printf("%d的左节点",a); create(&(*T)->left); printf("%d的右节点",a); create(&(*T)->right); 2.三种遍历的实现 （1）先序遍历 依旧采用递归的思想，先遍历根后遍历左子树再遍历右子树。 printf("%d ",T->data); Pro(T->left); Pro(T->right); （2）中序遍历 先遍历左子树再遍历根最后遍历右子树 Mid(T->left); printf("%d ",T->data); Mid(T->right); （3）后序遍历 先遍历左子树再遍历右子树最后遍历根 Later(T->left); Later(T->right); printf("%d ",T->data); （4）按层遍历 按层遍历采用队列的思想，先将第一个节点入队然后在将其出队将其左右孩子入队。依
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
数据结构实验五 课程数据结构实验名称二叉树的建立及遍历第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 １．学会实现二叉树结点结构和对二叉树的基本操作。 ２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3.整理并上交实验报告。 三、实验内容 1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉 树进行遍历。 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的,发生的现象和中间结果) 第一题 #ｉnｃlude "sｔdafx.ｈ" #include＂ｉoｓtｒeam.h" #inclｕde"sｔｄliｂ.h"
＃incｌudｅ"ｓｔdiｏ.ｈ" #include
《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师
一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：
用C语言编写二叉树的建立与遍历 #include "stdio.h" #include "string.h" #define NULL 0 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create(BiTree T){ char ch; ch=getchar(); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("Error!"); T->data=ch; T->lchild=Create(T->lchild); T->rchild=Create(T->rchild); } return T;
} void Preorder(BiTree T){ if(T){ printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); } } int Sumleaf(BiTree T){ int sum=0,m,n; if(T){ if((!T->lchild)&&(!T->rchild)) sum++; m=Sumleaf(T->lchild); sum+=m; n=Sumleaf(T->rchild); sum+=n; } return sum; } void zhongxu(BiTree T){ if(T){
zhongxu(T->lchild); printf("%c",T->data); zhongxu(T->rchild); } } void houxu(BiTree T){ if(T){ houxu(T->lchild); houxu(T->rchild); printf("%c",T->data); } } int Depth(BiTree T){ int dep=0,depl,depr; if(!T) dep=0; else{ depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?depl:depr); } return dep; }
二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include
实验三二叉树建立及遍历操作 一、实验目的 1.熟悉二叉树的存贮结构遍历方式，掌握有关算法的实现。 2.能够利用二叉树解决具体问题。 二、实验环境 1.硬件：每个学生需配备计算机一台。 2.软件：windows操作系统+Turbo C。 三、实验要求 1.要求采用二叉链表作为存贮结构，完成二叉树的建立，先序，中序，后序遍历的操作。其中先序遍历和后序遍历采用递归算法，中序采用非递归算法。 2.输入数据：树中每个结点的数据类型设为零字符型。 四、实验内容 实现如下二叉树处理函数 建立子函数 先序遍历子函数 中序遍历子函数 后序遍历子函数 五、代码如下 #include
二叉树的随机生成及其遍历 张zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生50个(不大于100且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。 程序设计 (一)需求分析： ●问题的定义与要求：1、产生50个不大于100且各不相同的随机整数（由系统的随机函数生成并对100取模）；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；5、按层次浏览二叉树结点；6、退出程序。 ●输入：所需功能，选项为1～6。 ●输出：按照用户功能选择输出结果。 ●限制：输入的功能选择在1～6之间，否则无回应。 ●模块功能及要求： RandDif():生成50个随机不大于100的整数，每次生成不同随机整数。 CreateBitree():给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。NRPreOrder():非递归算法的先根遍历。 inOrderTraverse():递归算法的中根遍历。 PostOrderTraverse():递归算法的后根遍历。 Welcome():欢迎窗口。 Menu():菜单。 Goodbye():再见窗口。 (二)概要设计：
首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。生成的二叉树是完全二叉树。 先根遍历的非递归算法： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行2、3 ，至栈空为止。 先根遍历的算法流程图： 根结点进栈（a[0]=T->boot,p=a[0]） 访问结点printf(*p) 右儿子存在则进栈a[i]=(*p).rchild; i++; 左儿子存在则进栈a[i]=(*p).rchild; i++; 栈顶降低top--：i--;p=a[i]; 栈非空while(i>-1) 返回 中根遍历的递归算法流程图： T为空 Y N Return; inOrderTraverse(T->lchild) Printf(T->data) inOrderTraverse(T->rchild)
问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。
（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include
实验四二叉树的建立和遍历 学院专业班 学号姓名 一．实习目的 1.掌握二叉链表的存储结构； 2.掌握二叉链表的建立； 3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法； 4. 掌握二叉树遍历算法的应用； 二．实习内容 1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示） 2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。 3．统计二叉树中结点个数； 4. 求二叉树的高度； 三．实验步骤 1.定义二叉链表的存储结构 #include "stdio.h" #include "stdlib.h" typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode,*BiTree; 2.编写函数CreateBiTree，按先序序列建立二叉树的二叉链表; 测试的字符序列为abdg###e##c#f##; 程序代码为： void CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，构造二叉链表表示的二叉树T。以#表示空树 TElemType ch; scanf("%c",&ch); if(ch=='#') // 空 T=NULL; else { T=(BiTree )malloc(sizeof(BiTNode)); // 生成根结点 if(!T)
exit(-1); T->data=ch; CreateBiTree(T->lchild);// 递归构造左子树 CreateBiTree(T->rchild);// 构造右子树 } } 2. 编写二叉树的先序遍历、中序遍历、后序遍历的递归算法 int preOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，先序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 {printf("%5c",T->data); // 访问根结点preOrderTraverse(T->lchild);// 先序遍历左子树 preOrderTraverse(T->rchild);// 先序遍历右子树 } } int inOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，中序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { inOrderTraverse(T->lchild);// 中序遍历左子树 printf("%5c",T->data); // 访问根结点inOrderTraverse(T->rchild);// 中序遍历右子树 } } int postOrderTraverse(BiTree T) { // 初始条件：二叉树T存在， // 操作结果：后序递归遍历T； if(T==NULL) return 1; if(T!=NULL) // T不空 { postOrderTraverse(T->lchild);// 后序遍历左子树 postOrderTraverse(T->rchild);// 后序遍历右子树 printf("%5c",T->data); // 访问根结点
青岛理工大学数据结构课程实验报告
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 总访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型