搜档网
当前位置:搜档网 › 二叉树的遍历

二叉树的遍历

二叉树的遍历
二叉树的遍历

二叉树的三种遍历方式:先序遍历、中序遍历、后序遍历

先序:

始终执行以下步骤,

1、访问根节点

2、遍历左子树

3、遍历右子树

中序:

始终执行以下步骤,

1、遍历左子树

2、访问根节点

3、遍历右子树

后序:

始终执行以下步骤,

1、遍历左子树

2、遍历右子树

3、访问根节点

“始终”:为什么要说“始终”执行呢?因为二叉树的每一个子树又可以看成是一个新的二叉树,遍历步骤、方式都保持一样,所以应该“始终”执行同样的操作,我们也应该始终把它看成一棵新的二叉树。

一些技巧:

1、先序遍历第一个元素一定是根节点

2、中序遍历中,任何一个元素的前一个元素一定在二叉树中它的左边,比如D在G前面,则D在G左边

3、后序遍历最后一个元素一定是根节点

4、先、中、后意思是说访问根节点的先后顺序,而且始终从左往右,从上往下

先序遍历为:ABC

中序遍历为:BAC

后序遍历为:BCA

先序遍历为:ABDECFG

中序遍历为:DBEAFCG

后序遍历为:AEBFGCA

前序遍历:abcdef 中序遍历:cbdaef 后序遍历:cdbfea

先序遍历为:ABDGCEF 中序遍历为:DGBAECF 后序遍历为:

GDBEFCA

前序遍历结果为 a b d e h i c f g 中序遍历结果为 d b h e i a f c g 后序遍历结果为 d h i e b f g c a

前序遍历结果为 FCADBEGHP 中序遍历结果为 ACBDFEHGP 后序遍历结果为 ABDCHPGEF

前序遍历为:—+ a * b — c d / e f 中序遍历为: a + b * c — d — e / f

后序遍历为: a b c d — * + e f / —

前序遍历结果为ABDHEICFG

中序遍历结果为HDBEIACGF

后序遍历结果为HDIEBGFCA

由先序序列ABCDEFGH 和中序序列CBEDAGHF 恢复二叉树: 方法: 先序序列ABCDEFGH (注:A 是根) 中序序列CBEDAGHF

由左子树先序序列:BCDE 和左子树中序序列:CBED 构造A 的左子树 同理,由右子树先序序列:FGH 和右子树中序序列GHF 构造A 的右子树:

1. 已知某二叉树的其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,求后序遍历序列(4275631)。

2、已知二叉树前序12453,中序42513。求后序。答案(45231)

这样的题怎么解?我们首先得牢记三种递归规则:

1、前根遍历:根—左—右

2、中根遍历:左—根—右

2、后根遍历:左—右—根

从规则可以看出:前根序列的第一个值肯定是整个二叉树的根。后根序列的最后一个值肯定是整个二叉树的根。而知道中根序列和前、后根的一个序列后,必然中根序列将分以根分为两个部分:左子树和右子树。这样,在子树里面找到做子树根的那个值,继续分左右子树,这样下去即可确定二叉树的形态。同时,我们可以看到,如果只知道前、后根遍历。不知道中根,则二叉树形态无法唯一确定。这样,我们来解答第一道题:前序为1243576中序为4215736.由前序可得1为二叉树的根。将中序分为左右两子树。左子树为42,右子树为5736。左子树前序序列中2在4的前面,中序2在4的后面,可知2为这个左子树的根,4为这个左子树的左节点。右子树中序5736,前序3576,可得3为右子树的根,以3为根的子树左边为57,右边为节点6。57这个子树5为根,7为右节点。这样我们就得到了这个二叉树的结构图形。后序遍历为4275631。

已知二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序遍历的序列是:

由后序(左子树,右子树,根节点)dabec知道根节点为c,再通过中序(左子树,根节点,右子树)知道右子树为空

接着由dabe知道其根节点为e,所以在中序deba中左子树为d右子树为ba

再来,后序ab,中序ba,b为节点,a为右子树

前序遍历序列为cedba

(2)若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是

A)bdgcefha

B)gdbecfha

C)bdgaechf

D)gdbehfca

正确答案: D

二叉树的建立,查找,删除,遍历

#include #include # define max 100 # define null 0 struct node *inserttree(struct node *tree); struct node *findtree(struct node *tree, int x); void correct(struct node *findi); struct node * deltree(struct node *tree); void preorder(struct node *tree); void midorder(struct node *tree); void postorder(struct node *tree); struct node { int data; struct node *llink; struct node *rlink; }; int main() { int choose; struct node *tree, *findi; int flag, x; flag=1; tree=null; do { printf("*************************\n"); printf("Please choose your choice\n1----------creattree\n2----------findtree\n3----------correct\n4----------deltree\n"); printf("5----------preorder\n6----------midorder\n7----------postorder\n"); printf("*************************\n"); scanf("%d",&choose); switch(choose) { case 1:tree=inserttree(tree); break; case 2:printf("Please input the number you want find!\n"); scanf("%d",&x); findi=findtree(tree,x); if(findi==null) printf("There is not a number in dinary tree \n"); else printf("The number you want to find=%d\n",findi->data); break; case 3:printf("Please input the number you want to replace:"); scanf("%d",&x); findi=findtree(tree,x); correct(findi); break; case 4:tree=deltree(tree);

二叉树遍历方法技巧

二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态,是否能根据此图快速地得出其中序遍历的序列?回答是肯定的。具体做法是:首先按照二叉树的标准绘制二叉树形态,即将所有左子树都严格绘于根结点的左边;将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来,那么所有结点在地平线上一定会有相应的投影,从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列: D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态,可在图形基础上,采用填空法迅速写出该二叉树的先序遍历序列。具体做法是:我们知道,对于每个结点都由三个要素组成,即根结点,左子树、右子树;又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么,我们按层分别展开,逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下: (1)根结点左子树右子树 A( )( ) (2)A (根结点(左子树)(右子树))(根结点(左子树)(右子树)) A B C (3)A(B(根结点(左)(右))(根结点(左)(右)))(C(……)(……)) A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注:后序遍历的序列亦可以此方法类推,请读者自己尝试。

3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列,则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的,那么首先从给定的先序遍历序列入手,该先序序列的第一个元素一定是该二叉树的根;再分析这个根结点在中序遍历序列中的位置,中序遍历序列中根结点的左边即为左子树的全部元素,而根结点的右边即为右子树的全部元素;然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分,并在这两部分中分别找出左、右子树的根结点。依此类推,即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为: 先序: A B C I D E F H G 中序: C I B E D A H F G 请构造这棵二叉树。 按前述分析,这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述,树(或森林)的存储结构及其操作算法的实现,由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间,因而,定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则,用二叉树来表示树和森林的话,就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道,一棵树中每个结点的孩子是无序的,而二叉树中各结点的孩子必须有左右之分。在此,为避免概念混淆,首先约定树中每个结点的孩子按从左至右的顺序升序编号,即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是: (1)在树中同层兄弟间加一连线; (2)对树中每个结点仅保留其与长兄(左边第一个孩子)的连线,擦去其与其它孩子的连线; (3)以树(或子树)的根作为轴心,将所有的水平连线顺时针旋转45度,即可得到与该树完全等价的一棵二叉树。

二叉树的遍历和应用

内蒙古科技大学 本科生课程设计说明书 题目:数据结构课程设计 ——二叉树的遍历和应用 学生姓名: 学号: 专业: 班级: 指导教师: 2013年5月29日

内蒙古科技大学课程设计说明书 内蒙古科技大学课程设计任务书 I

内蒙古科技大学课程设计说明书 目录 内蒙古科技大学课程设计任务书..............................................................错误!未定义书签。目录....................................................................................................................................II 第一章需求分析 (3) 1.1课程设计目的 (3) 1.2任务概述 (3) 1.3课程设计内容 (3) 第二章概要设计 (5) 2.1设计思想 (5) 2.2二叉树的遍历 (5) 2.3运行界面设计 (6) 第三章详细设计 (7) 3.1二叉树的生成 (7) 3.2二叉树的先序遍历 (7) 3.3 二叉树的中序遍历 (8) 3.4二叉树的后续遍历 (8) 3.5主程序的设计 (8) 第四章测试分析 (11) 4.1二叉树的建立 (11) 4.2二叉树的先序、中序、后序遍历 (11) 第五章课程设计总结 (12) 附录:程序代码 (13) 致谢 ···········································································································错误!未定义书签。 II

二叉树实验报告

实验题目:实验九——二叉树实验 算法设计(3) 问题分析: 1、题目要求:编写算法交换二叉树中所有结点的左右子树 2、设计思路:首先定义一个二叉树的数据类型,使用先序遍历建立该二叉树,遍历二叉树,设计左右子树交换的函数,再次遍历交换之后的二叉树,与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据: A、输入:1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历:4 2 5 1 3 交换后中序遍历:3 1 5 2 4 交换前:交换后: B、输入:3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历:11 7 17 18 19 3 13 6 16 交换后中序遍历:16 6 13 3 19 18 17 7 11 概要设计: 1、为了实现上述功能:①构造一个空的二叉树;②应用先序遍历输入,建立二叉树;③中序遍历二叉树;④调用左右子树交换函数;⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数: ①主函数main() ②先序遍历二叉树建立函数creat_bt() ③中序遍历二叉树函数inorder() ④左右子树交换函数 exchange()

各函数间关系如下: 详细设计: 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据; 判断是否为0{ 若是,为空; 不是,递归;} 返回二叉树; } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否,交换左右子树; 递归;} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树; 输出; 递归右子树;} } main () creat_bt () inorder () exchange ()

二叉树的遍历(非递归)

实验三:二叉树的遍历问题 题目:编制一个遍历二叉树的程序 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及二叉树的操作的算法都是以二叉树的遍历操作为基础的。编写程序,对一棵给定的二叉树进行先、中、后三种次序的遍历。 2.基本要求:以二叉链表为存储结构,实现二叉树的先、中、后三种次序的递归和非递归遍历。 3.测试数据:以教科书图6.9的二叉树为例。 4.实现提示: (1).设二叉树的结点不超过30个,且每个结点的数据均为字符,这样可利用先序遍历序列作为输入顺序创建二叉树链表存储结构。 (2.)也可利用完全二叉树在顺序存储中的特性,创建二叉树的存储结构,此时,二叉树中结点数据的类型不受限制。 二.概要设计 1.为实现上述功能,应先建立二叉树。为此,需要有一个二叉树的抽象数据类型。该抽象数据类型的定义为: ADT BinaryTree { 数据对象D:D是具有相同特性的数据元素的集合 termset中每个元素包含编号,密码,和一个指向下一节点的指针数据关系R: 若D=?,则R=?,称BinaryTree为空二叉树; 若D≠?,则R={H},H是如下二元关系: (1).在R中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2).若D-(root) ≠?, 则存在D-(root)={D1,D2},且D1∩D2=?; (3). D1≠?,则D1中存在唯一的元素x1,∈H,且存在D1上的关系 H1?H;若Dr≠?,则Dr中存在唯一的元素Xr, ∈H,且存在Dr上的关 系Hr?H;H={,,H1,Hr}; (4).(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树,(Dr,{Hr})是一棵 符合本定义的二叉树,称为根的右子树。 基本操作P: createbt(BiTree& T) 操作结果:构造一棵空二叉树 PreOrder(BiTree T) 初始条件:二叉树T存在

二叉树的建立和遍历的实验报告doc

二叉树的建立和遍历的实验报告 篇一:二叉树的建立及遍历实验报告 实验三:二叉树的建立及遍历 【实验目的】 (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))))

二叉树的建立及几种简单的遍历方法

#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); //***************************************************

二叉树遍历

江苏大学京江学院 实验报告 课程名称:二叉树操作 课程类型:必修 课程题目:二叉树的建立,二叉树的遍历。 姓名:吴江 班级:J计算机1002班 学号:3101110038 导师:王新宇

一、实验内容 二叉树的建立,二叉树的遍历。 二、实验目的 1.进一步掌握指针变量的使用; 2.掌握二叉树的结构特征以及各种存储结构的特点及使用范围。 3.掌握用指针类型描述、访问和处理二叉树的运算; 4.掌握栈或队列的使用。 三、实验题目 本实验要求实现以下功能: 1.按前序次序建立一颗二叉树,以‘#’表示空。 2.中序、后序遍历该二叉树,输出遍历序列。 3.求出该二叉树的深度并输出,或求出该二叉树的叶子数目并输出。 [测试数据]: 输入以下字符串,建立二叉树:ABC##DE#G##F### 输出中序遍历序列应为:CBEGDFA 输出后序遍历序列应为:CGEFDBA 输出二叉树的深度应为:5 输出二叉树的叶子数目应为:3

四、实验源程序 # include # include # define OK 1 # define ERROR -1 # define overflow -1 typedef int ElemType; typedef int Status; typedef struct BiTNode { ElemType data;//此处Elem Type 根据数据类型实际情况而定struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; Status CreateTree(BiTree &T)//按先序输入二叉树中节点的值{ char ch; ch=getchar(); if(ch=='#') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(overflow); T->data=ch; CreateTree(T->lchild); CreateTree(T->rchild); } return OK; } Status MidTraverse(BiTree T) { if(T) { MidTraverse(T->lchild); printf("%c",T->data); MidTraverse(T->rchild); } return OK;

实验四 二叉树的遍历和应用04

江南大学通信与控制工程学院标准实验报告 (实验)课程名称:计算机软件技术基础实验名称:二叉树的遍历和应用 班级:自动化 姓名:李玉书 学号:03 指导教师:卢先领 江南大学通信与控制学院

江南大学 实验报告 学生姓名:张晓蔚学号:0704090304 实验地点:信控机房实验时间:90分钟 一、实验室名称:信控学院计算中心 二、实验项目名称:二叉树的遍历和应用 三、实验学时:4学时 四、实验原理: 二叉树的遍历和应用 五、实验目的: 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构(二叉链表)的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容: 阅读后面的程序,并将其输入到计算机中,通过调试为下面的二叉树建立二叉链表,并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材(设备、元器件): 计算机 八、实验步骤: 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并,编译,调试 5、测试,查错,修改

6、生成可执行文件,通过综合测试,完成实验 九、实验数据及结果分析: 测试用例 初始数据:ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论: 该程序可以完成线性表的常规功能,且增加了异常处理,在异常情况下,例如: 表空,删除结点号不合法或出界,删除数值未找到等,这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议: 对书中程序的几点错误做了改正,见源程序。 附:源程序 #include typedef struct bitree { char data ; bitree *lchild; bitree *rchild;

二叉树遍历课程设计心得【模版】

目录 一.选题背景 (1) 二.问题描述 (1) 三.概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四.详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五.测试数据与分析 (6) 六.源代码 (6) 总结 (10) 参考文献: (11)

一.选题背景 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域,分别是数据域,左孩子指针域,右孩子指针域。因此每个结点为 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。 然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例,它要求首先要访问根节点,然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中,最后访问结点的左子树的根结点将最先被访问,这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。 二.问题描述 对任意给定的二叉树(顶点数自定)建立它的二叉链表存贮结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。画出搜索顺序示意图。

三.概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图 图3.3二叉树中序遍历示意图

实验八:二叉树的遍历与应用

实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征,理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法,领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果,并结合程序进行分析。 三、实验题目 1.编写算法,按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include #define VirNode 0 /*虚结点值*/ #define MAXSIZE 100 /*一维数组的容量*/ typedef int TElemType; /*二叉树结点值的类型*/ typedef TElemType SqBitTree[MAXSIZE]; /*SqBitTree:顺序存储的二叉树类型名*/ void leveltree(SqBitTree bt) { } void main() {SqBitTree bb={15,1,2,3,4,5,0,0,8,0,0,11,0,0,0,0}; ; } 2.以二叉链表为存储结构实现二叉树的三种遍历(先序、中序、后序)的递归算法。将tree.h 和tree.c文件补充完整。 3.编写算法,按层次遍历一棵二叉链表。 4.编写算法,输出二叉树中所有度为2的结点。 void printdata(BitTree bt) 5.编写算法,求二叉树中结点的最大值。假设结点为整型。 int maxvalue(BitTree bt) 6.编写递归算法,求二叉树中以元素值为x的结点为根的子树的深度。(首先在遍历过程中找到值为x结点,然后调用Get_Depth(),求得值为x的结点为根的子树的深度)。 注意:后面有算法的过程与步骤,请填空。 7.编写算法,实现二叉链表的先序非递归遍历。 void PreOrderBiTree(BitTree T)

二叉树的层次遍历算法

二叉树层次遍历算法实现 问题描述 对任意输入的表示某二叉树的字符序列,完成二叉树的层次遍历算法,并输出其遍历结果。 注:所需Queue ADT的实现见附录。 输入描述 从键盘上输入一串字符串,该字符串为二叉树的先序遍历结果,其中如果遍历到空树时用字符”#”代替。 输出描述 从显示器上输出二叉树的按层次遍历结果。 输入与输出示例 输入: +A##/*B##C##D## 输出: +A/*DBC 输入: ABD##GJ###CFH##I### 输出: ABCDGFJHI 附录(仅供参考): #include #include #define TRUE 1 #define FALSE 0 #define MAX_QUEUE_SIZE 100

//注:需要定义ElementType类型,如果是二叉树, // 则应定义为指向二叉树中结点的指针类型 //格式如: // typedef Tree ElementType; // 队列存储结构采用循环队列 struct QueueRecord; typedef struct QueueRecord *Queue; int IsEmpty(Queue Q); int IsFull(Queue Q); Queue CreateQueue(int MaxElements); void DisposeQueue(Queue Q); void MakeEmpty(Queue Q); int Enqueue(ElementType X, Queue Q); ElementType Front(Queue Q); int Dequeue(Queue Q, ElementType &X); #define MinQueueSize ( 5 ) struct QueueRecord { int Capacity; int Front; int Rear; ElementType *Array; }; int IsEmpty(Queue Q) { return ((Q->Rear + 1)% Q->Capacity == Q->Front); } int IsFull(Queue Q) { return ((Q->Rear + 2) % Q->Capacity == Q->Front); } Queue CreateQueue(int MaxElements) { Queue Q; if (MaxElements < MinQueueSize) return NULL; Q = (Queue)malloc(sizeof(struct QueueRecord));

二叉树的遍历算法实验报告

二叉树实验报告 09信管石旭琳 20091004418 一、实验目的: 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容: 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法(中序、前序、后序) 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序: #include #include typedef int ElemType; struct BiTNode { ElemType data; struct BiTNode *lch,*rch; }BiTNode,*BiTree; struct BiTNode *creat_bt1(); struct BiTNode *creat_bt2(); void preorder (struct BiTNode *t); void inorder (struct BiTNode *t); void postorder (struct BiTNode *t); void numbt (struct BiTNode *t); int n,n0,n1,n2; void main() { int k; printf("\n\n\n"); printf("\n\n 1.建立二叉树方法1(借助一维数组建立)"); printf("\n\n 2.建立二叉树方法2(先序递归遍历建立)"); printf("\n\n 3.先序递归遍历二叉树"); printf("\n\n 4.中序递归遍历二叉树"); printf("\n\n 5.后序递归遍历二叉树"); printf("\n\n 6.计算二叉树结点个数"); printf("\n\n 7.结束程序运行");

二叉树遍历算法的实现

二叉树遍历算法的实现 题目:编制二叉树遍历算法的实现的程序 一.需求分析 1.本演示程序中,二叉树的数据元素定义为非负的整型(unsigned int)数据,输 入-1表示该处没有节点 2.本演示程序输入二叉树数据均是按先序顺序依次输入 3.演示程序以用户和计算机对话方式执行,即在计算机终端上显示“提示信息” 之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据和运 算结果显示在其后 4.本实验一共包括三个主要程序,分别是:1)二叉树前序,中序,后序遍历递归 算法实现2)二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现 5.本程序执行命令包括:1)构建二叉树2)二叉树前序递归遍历3)二叉树中序 递归遍历4)二叉树后序递归遍历5)二叉树前序非递归遍历6)二叉树中序非 递归遍历7)二叉树层次遍历 6.测试数据 (1)7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1 (2)1 -1 -1 (3)7 8 -1 -1 9 -1 -1 二.概要设计 1.为实现二叉树的遍历算法,我们首先给出如下抽象数据类型 1)二叉树的抽象数据类型 ADT BiTree{ 数据对象D:D是具有相同特性的数据元素的集合 数据关系R: 若D=Φ,则R=Φ,称BiTree是空二叉树; 若D≠Φ,则R={H},H是如下二元关系: (1)在D中存在唯一的成为根的数据元素root,它在关系H下无前驱; (2)若D-{H}≠Φ,则存在D-{root}={D1,D r},且D1∩D r=Φ (3)若D1≠Φ,则D1中存在唯一的元素x1,∈H,且存在D1上的 关系H1?H;若Dτ≠Φ,则D r中存在唯一的元素x r,∈ H,且存在D r上的关系H r?H;H={,,H1,H r}; (4)(D1,{H1})是符合本定义的二叉树,成为根的左子树,(D r,{H r})是 一颗符合本定义的二叉树,成为根的右字树。 基本操作P: InitBiTree(&T); 操作结果:构造空二叉树 DestroyBiTree(&T) 初始条件;二叉树存在 操作结果:销毁二叉树 CreateBiTree(&T,definition);

数据结构实验二叉树的遍历

南昌大学实验报告 学生姓名:李木子学号:专业班级:软工 实验类型:□验证□综合□设计□创新实验日期:实验成绩:一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义,创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑, 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; };

************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">);

二叉树的遍历实验报告

二叉树的遍历实验报告 一、需求分析 在二叉树的应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理,这就是二叉树的遍历问题。 对二叉树的数据结构进行定义,建立一棵二叉树,然后进行各种实验操作。 二叉树是一个非线性结构,遍历时要先明确遍历的规则,先访问根结点还时先访问子树,然后先访问左子树还是先访问有右子树,这些要事先定好,因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义,以及遍历规则,本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图

三、各模块设计分析 (1)建立二叉树结构 建立二叉树时,要先明确是按哪一种遍历规则输入,该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现,因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成,两个指针域分别指向该结点的左、右孩子,若某结点没有左孩子或者右孩子时,对应的指针域就为空。最后,还需要一个链表的头指针指向根结点。 要注意的是,第一步的时候一定要先定义一个结束标志符号,例如空格键、#等。当它遇到该标志时,就指向为空。 建立左右子树时,仍然是调用create ()函数,依此递归进行下去,

直到遇到结束标志时停止操作。 (2)输入二叉树元素 输入二叉树时,是按上面所确定的遍历规则输入的。最后,用一个返回值来表示所需要的结果。 (3)先序遍历二叉树 当二叉树为非空时,执行以下三个操作:访问根结点、先序遍历左子树、先序遍历右子树。 (4)中序遍历二叉树 当二叉树为非空时,程序执行以下三个操作:访问根结点、先序遍历左子树、先序遍历右子树。 (5)后序遍历二叉树 当二叉树为非空时,程序执行以下三个操作:访问根结点、先序遍历左子树、先序遍历右子树。 (6)主程序 需列出各个函数,然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的,所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild;

创建一个二叉树并输出三种遍历结果

实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别___ _计算机学院 _ ______ 专业___ ___ 班级/学号___________ 学生姓名 _________ 实验日期_ 成绩_______________________ 指导教师

实验题目:实验三------创建一个二叉树并输出三种遍历结果 一、实验目的 1)掌握二叉树存储结构; 2)掌握并实现二叉树遍历的递归算法和非递归算法; 3)理解树及森林对二叉树的转换; 4)理解二叉树的应用—哈夫曼编码及WPL计算。 二、实验内容 1)以广义表或遍历序列形式创建一个二叉树,存储结构自选; 2)输出先序、中序、后序遍历序列; 3)二选一应用题:1)树和森林向二叉树转换;2)哈夫曼编码的应用问题。(应用型 题目可替换上述前两项实验内容) 三、设计与编码 1)程序结构基本设计框架 (提示:请根据所选定题目,描述程序的基本框架,可以用流程图、界面描述图、框图等来表示) 2)本实验用到的理论知识 遍历二叉树,递归和非递归的方法

(提示:总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,要求结合自己的题目并阐述自己的理解和想法) 3)具体算法设计 (1)首先,定义二叉树的存储结构为二叉链表存储,每个元素的数据类型Elemtype,定义一棵二叉树,只需定义其根指针。 (2)然后以递归的先序遍历方法创建二叉树,函数为CreateTree(),在输入字符时要注意,当节点的左孩子或者右孩子为空的时候,应 当输入一个特殊的字符(本算法为“#”),表示左孩子或者右孩子为 空。 (3)下一步,创建利用递归方法先序遍历二叉树的函数,函数为PreOrderTree(),创建非递归方法中序遍历二叉树的函数,函数为 InOrderTree(),中序遍历过程是:从二叉树的根节点开始,沿左子树 向下搜索,在搜索过程将所遇到的节点进栈;左子树遍历完毕后, 从栈顶退出栈中的节点并访问;然后再用上述过程遍历右子树,依 次类推,指导整棵二叉树全部访问完毕。创建递归方法后序遍历二 叉树的函数,函数为LaOrderTree()。 (提示:该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作,可以用列表分步形式的自然语言描述,也可以利用流程图等描述) 4)编码 #include #include #include typedef char DataType; #define MaxSize 100 typedef struct Node { DataType data; struct Node *lchild; struct Node *rchild; } *BiTree,BitNode; void InitBitTree(BiTree *T); /*树的初始化*/ void CreateBitTree(BiTree *T); /*按照先序输入字符序列递归创建二叉树*/ void PreOrderTraverse(BiTree T); /*二叉树的先序遍历的递归函数声明*/ void InOrderTraverse(BiTree T); /*二叉树的中序遍历的递归函数声明*/ void PostOrderTraverse(BiTree T); /*二叉树的后序遍历的递归函数声明*/ void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的非递归函数声明*/ void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的非递归函数声明*/ void PostOrderTraverse2(BiTree T); /*二叉树的后序遍历的非递归函数声明*/

数据结构二叉树遍历实验报告

问题一:二叉树遍历 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 #include #include #define ElemType char struct BTreeNode { ElemType data; struct BTreeNode* left; struct BTreeNode* right; }; void CreateBTree(struct BTreeNode** T) { char ch; scanf_s("\n%c", &ch); if (ch == '#') *T = NULL;

二叉树遍历课程设计】

数据结构程序设计报告 学院: 班级: 学号: :

实验名称:二叉树的建立与遍历 一、实验目的: 1.掌握二叉树的二叉链表存储结构; 2.掌握二叉树创建方法; 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验容和要求: 创建二叉树,分别对该二叉树进行先序、中序、后序遍历,并输出遍历结果。 三、叉树的建立与遍历代码如下: #include #include struct tnode//结点结构体 { char data; struct tnode *lchild,*rchild; }; typedef struct tnode TNODE; TNODE *creat(void) { TNODE *root,*p; TNODE *queue[50];

int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树,请输入结点:(#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素,则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p;

相关主题