二叉树 实验报告

1. 编写函数,输入字符序列,建立二叉树的二叉链表。2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法,输出各遍历序列;3. 编写函数,实现二叉树的中序非递归遍历算法。4. 编写函数,求二叉树的叶子个数。5. 编写函数,交换二叉树每个结点的左子树和右子树。6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

学号 3208006375 姓名 何绮珊 协作者_____________ 教师评定___________

实验题目 二叉树操作

一. 实验目的及要求

1.掌握二叉树的存储实现； 2.掌握二叉树的遍历思想；

3.掌握二叉树的常见算法的程序实现。

二. 实验内容

1. 编写函数,输入字符序列,建立二叉树的二叉链表。

2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法，输出各遍历序列；3. 编写函数,实现二叉树的中序非递归遍历算法。 4. 编写函数,求二叉树的叶子个数。

5. 编写函数,交换二叉树每个结点的左子树和右子树。

6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

三. 实验步骤

（1）认真阅读二叉树的内容，从而掌握二叉树的相关内容，为编写程序做好第一步；

（2）熟悉C语言编程环境（在本次实验中用了VC++6.0）,了解实验的注意事项，以便在实验时能很好地应付可能出现的问题；

（3

）通过前面两步，在实验前找到自己的问题，实验前好好思考，若不能自行

1. 编写函数,输入字符序列,建立二叉树的二叉链表。2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法,输出各遍历序列;3. 编写函数,实现二叉树的中序非递归遍历算法。4. 编写函数,求二叉树的叶子个数。5. 编写函数,交换二叉树每个结点的左子树和右子树。6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

解决，要问老师和同学解决该问题，做好实验前的充分准备；

（4）上机以前好好编写程序,这样可以利用在机房的时间问老师你所碰到的问题,从而有效解决你的问题;

（5）对该程序进行编译，调试等操作直至程序没有错误，同时可以美化你的程序，使得实验运行结构看上去十分清晰，美观。再运行该程序，从而得到所须结果，记录该结果；

（6）实验结束后，将自己的心得及对相关问题的体会都认真写在实验报告里，好好做好实验报告 。

四. 程序功能需求分析

本程序应具有以下功能：

建立二叉树：

进入程序运行界面后，提示我们输入需要建立的二叉树，并默认以先序序列输入。若第一个输入为“#”，则为空树。否则按照从左子树到右子树的顺序建立该二叉树。建立完二叉树后按“ENTER”键自动进入下一个功能模块的实现。

实现各个遍历递归算法：

实现该二叉树的先序遍历、中序遍历和后序遍历递归算法，逐个访问该二叉树的左右子树，并输出各遍历序列。

实现该二叉树的中序遍历非递归算法：

利用顺序栈的结构实现对该二叉树进行中序遍历，且在实现这个子函数前必须完成对栈的结构的定义、创建空栈、判栈空、判栈满、进栈、退栈、当栈非空时取栈顶元素等函数的建立。最后并能输出其中序遍历非递归结果。

统计出该二叉树中叶子结点个数：

只要该二叉树的移动指针t所指向的结点非空，刚进一步判断其左右子树是否也都为空，让表示叶子结点的变量能够记录叶子结点个数。

实现交换该二叉树所有结点左右子女的操作。

该二叉树非空，刚实现对其交换所有结点左右子女的操作。并分别按照先序遍历、中序遍历和后序遍历递归算法对该交换后的二叉树进行输出。

1. 编写函数,输入字符序列,建立二叉树的二叉链表。2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法,输出各遍历序列;3. 编写函数,实现二叉树的中序非递归遍历算法。4. 编写函数,求二叉树的叶子个数。5. 编写函数,交换二叉树每个结点的左子树和右子树。6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

五. 数据结构设计

1.二叉树结构

typedef struct node { char data; /*数据域*/

struct node *lchild; /*左孩子域*/

struct node *rchild; /*右孩子域*/} BTNode;

2.栈的结构

typedef BTNode *DataType; typedef struct {

DataType data[MAX]; int top;} SeqStack;

SeqStack *s;

六. 编码设计

#include "stdio.h" #define PR printf #define ERROR 0 #define MAX 100

/*============================建立各结构体===============================*/ typedef struct node {

char data; /*数据域*/ struct node *lchild;

struct node *rchild; /*结点的左右指针，分别指向结点的左右孩子*/ }BTNode;

typedef BTNode *DataType; typedef struct {

DataType data[MAX];

int top; }SeqStack;

SeqStack *s;

/*============================栈的操作===================================*/

1. 编写函数,输入字符序列,建立二叉树的二叉链表。2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法,输出各遍历序列;3. 编写函数,实现二叉树的中序非递归遍历算法。4. 编写函数,求二叉树的叶子个数。5. 编写函数,交换二叉树每个结点的左子树和右子树。6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

SeqStack *createemptystacks() /*创建一个空栈*/ { SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack)); {

s->top=0; return s; }

int stackemptys(SeqStack *s) /*判栈空*/

return s->top==0; }

int stackfulls(SeqStack *s) /*判栈满*/ {

return s->top==MAX; }

void pushs(SeqStack *s,DataType x) /*进栈*/ {

if(stackfulls(s)) PR("over flow\n"); else s->data[s->top++]=x; }

void pops(SeqStack *s) /*退栈*/ { if(stackemptys(s))

PR("underflow\n"); else }

s->top--;

DataType gettops(SeqStack *s) /*栈非空时取栈顶元素*/ {

return s->data[s->top-1]; }

/*============================建立二叉树==================================*/

BTNode *createbintree() /*输入扩充的先序序列，建立二叉树*/ {

1. 编写函数,输入字符序列,建立二叉树的二叉链表。2. 编写函数, 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法,输出各遍历序列;3. 编写函数,实现二叉树的中序非递归遍历算法。4. 编写函数,求二叉树的叶子个数。5. 编写函数,交换二叉树每个结点的左子树和右子树。6. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

BTNode *t;

char x;

scanf("%c",&x); if(x=='#')

t=NULL; /*读入#，返回空指针 */ else {

t=(BTNode *)malloc(sizeof(BTNode)); /*生成结点*/ t->data=x;

t->lchild=createbintree(); /*构造 …… 此处隐藏：6294字，全部文档内容请下载后查看。喜欢就下载吧 ……