实验4 二叉树操作
一、实验目的
1.熟悉树的存储结构;
2.熟悉二叉链表的创建;
3.熟悉二叉树的遍历操作和其他操作。
二、实验内容
1、针对如图所示的二叉树,用先序遍历方法创建该二叉树的二叉链表存储;
2、 在第1步基础上,用非递归中序遍历方法和后序递归遍历方法,分别输出遍历结果;
3、用非递归方法找出该二叉树的所有叶子结点并输出。
三、实验要求
1.每个同学必须独立完成;
2.程序中的开头部分必须对本程序的总体功能进行注释;程序中每个函数段必须要有注释说明该函数的功能或作用;
3.上机进行调试和修改并填写实验报告;
4.实验报告中的源程序必须调试通过。
5.在体会中描述如下内容:
(1)对算法与程序的区别上的体会。
(2)本次实验过程的体会,是否自己独立完成?最大的困难是什么?自己准备如何解决这个困难?
6.提交实验报告(报告中包含关键源代码)。
参考实验代码:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
typedef struct Binnode{
char data;
struct Binnode *lchild;
struct Binnode *rchild;
}Binnode;
/*按照前序遍历建立二叉树*/
void Creat_Bintree(Binnode **t)
{
char ch;
scanf("\n%c",&ch);
if(ch=='0') *t=NULL;
else
{
*t=(Binnode*)malloc(sizeof(Binnode));
if(!*t)exit(OVERFLOW);
(*t)->data=ch;
printf("%c: left",ch); Creat_Bintree(&(*t)->lchild);
printf("%c: right",ch);Creat_Bintree(&(*t)->rchild);
}
}
/* 按照后序递归遍历二叉树*/
void Posorder1(Binnode *t)
{ /* printf("\n输出后序递归遍历序列:");*/
if(t!=NULL)
{
Posorder1(t->lchild);
Posorder1(t->rchild);
printf("%c",t->data);
}
}
/*按照中序非递归遍历二叉树*/
void Inorder2(Binnode *root)/*中序非递归遍历二叉树*/
{ Binnode *p,*stack[100];
int top=0;
p=root;
do{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[top];/*p所指的节点为无左子树或其左子树已经遍历过*/
top--;
printf("%c",p->data);
p=p->rchild;
}
}while(p!=NULL||top!=0);
}
/*非递归法求叶子结点个数*/
int Leaves_Num2(Binnode *t)
{
Binnode *s[100];
int count=0,top=0;
while(t||top>0)
{
if(t)
{
s[top++]=t;
if(t->lchild==NULL&&t->rchild==NULL)
{
count++;
printf("%c",t->data);/*输出叶子结点*/
}
t=t->lchild;
}
else
{
t=s[--top]->rchild;
}
}
return count;
}
int main()
{
Binnode *proot=NULL;
int p,q;
printf("1.CreateBitree:\n");
Creat_Bintree(&proot); /*建立二叉树时,无左右孩子的结点输入’0’值*/
printf("\n5.Output Not Digui InOrder:\n");
Inorder2(proot);
printf("\n6.Output Digui PostOrder:\n");
Posorder1(proot);
printf("\n11.Leaves_Node:\n");
q=Leaves_Num2(proot);
printf("\n12.Output Not Digui Leaves_Num:%d\n",q);
return 0;
}
分享到:
相关推荐
南邮数据结构实验使用C++描述,二叉树的基本操作
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
【实验课程名称】算法与数据结构 【实验项目名称】二叉树基本操作的实现
实验七 二叉树操作验证 1. 实验目的 ⑴ 掌握二叉树的逻辑结构; ⑵ 掌握二叉树的二叉链表存储结构; ⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。 2. 实验内容 ⑴ 建立一棵含有n个结点的二叉树,采用二叉链表...
一、实验目的 1.掌握二叉树的二叉表存储结构。 2.掌握利用二叉树创建方法。 3.掌握二叉树的先序,中序,后序的递归实现方法。 二、实验环境( 硬件/软件要求 ) Windows XP/Windows 7,Visual C++ 6.0 三、实验内容 在...
//按照先序非递归遍历二叉树 void preorder(BiTree T) { BiTree*stack[100];//定义栈 int top ; if(T!=NULL) {top=1; stack[top]=T;//进栈 while(top>0) { T=stack[top] ; top--; printf("%c",T->data);//...
广州大学 数据结构实验报告 实验二 二叉树的操作与实现 1、二叉树的基本操作算法实现 2、二叉树的各种遍历算法实现 3、线索二叉树的遍历 4、构造哈夫曼树和哈夫曼编码的算法实现
实验四 二叉树操作实现.pdf实验四 二叉树操作实现.pdf
实验四 二叉树操作实现.docx实验四 二叉树操作实现.docx
熟悉二叉树结点的结构和对二叉树的基本操作。掌握对二叉树每一种操作的具体实现。学会利用递归方法和非递归方法编写对二叉树这种递归数据结构进行处理的算法。
实验六 二叉树操作.cpp
1、 创建二叉树类。二叉树的存储结构使用链表。 2、 提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目...4、 接收键盘录入的二叉树前序序列和中序序列(各元素各不相同),输出该二叉树的后序序列。
问题描述:采用二叉链表作为存储结构,完成图1的二叉树的建立和遍历操作。 基本要求: (1)基于先序遍历的构造算法。输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符...
程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法,同时也给出了查询“E”是否在二叉树里的...资源含有实验报告的编写,及选做题(编写二叉树的前序(或中序)的非递归遍历算法并进行测试)
本人本科期间数据结构二叉树的实验 1、建立二叉树的存储结构 2、先序、中序、后序遍历二叉树(要求任选某一种用非递归算法完成) 3、查询二叉树中某个结点 4、统计二叉树中叶子结点的个数 5、求二叉树的深度 6、要求...
附程序代码和实验报告 1 输入形式和输入值的范围:定义二叉树的结点类型为字符型。在生成二叉树和查找结点时按要求输入字符。 2 输出形式和输出值的范围:在所有功能中,二叉树的遍历和查找,输出的是字符型数据,在...
二叉树基本操作 数据结构 实验报告
201900302030_邵嘉明_实验五 二叉树操作1
1.输入字符序列,建立二叉链表。 2.中序遍历二叉树:递归算法。 3.中序遍历二叉树:非递归算法。(最好也能实现先序,后序非递归算法) 4.求二叉树的高度 。 5.求二叉树的叶子个数。