实验三 二叉树的遍历
一、 实验目的
1． 进一步掌握指针变量的含义。
2． 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。
3． 掌握用指针类型描述、访问和处理二叉树的运算。
二、 实验要求
1． 认真阅读和掌握本实验的参考程序。
2． 按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。
3． 保存程序的运行结果，并结合程序进行分析。
三、 实验内容
以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建正确与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿
教材
民兵爆破地雷教材pdf初中剪纸校本课程教材衍纸校本课程教材排球校本教材中国舞蹈家协会第四版四级教材
例6.4初始化方式创建二叉树:所有的空指针均用#表示，如教材图6-13对应的二叉树，建立时的初始序列为：AB#D##CE##F##。
参考程序:
#define max 30
#define NULL 0
#include
#include
typedef struct BNode
{
char data; /*数据域 */
struct BNode *lchild,*rchild;; //指向左右子女
}BinTree;
void preorder(BinTree *t); //声明先根遍历函数
void inorder(BinTree *t); //声明中根遍历函数
void postorder(BinTree *t);//声明后根遍历函数
int leafs(BinTree *b); //声明求叶子数函数
int treedeep(BinTree *p); //声明求树的深度函数
BinTree *swap(BinTree *p); //声明交换二叉树的所有结点的左右子树的函数
//将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树
BinTree *cre_tree(char *str,int i,int m)
{
BinTree *p;
if(i>=m) //无效结点
return NULL;
p=(BinTree *)malloc(sizeof(BinTree));//生成新结点
p->data=str[i];
p->lchild=cre_tree(str,2*i+1,m);//创建新结点的左子树
p->rchild=cre_tree(str,2*i+2,m);//创建新结点的右子树
return p;
}
void main()
{
int i,n;
char str[max];
BinTree *root;//根结点
printf("请输入二叉树的结点数:");
scanf("%d",&n);
getchar();//输入数字
printf("请输入长度为 %d 的字符串 :",n);
for(i=0;idata);
if(t->lchild)
{
printf("->");
preorder(t->lchild);
}
if(t->rchild)
{
printf("->");
preorder(t->rchild);
}
}
}
void inorder(BinTree *t)
{
if(t!=NULL)
{
inorder(t->lchild);
printf(" %c ",t->data);
inorder(t->rchild);
}
}
void postorder(BinTree *t)
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf(" %c ",t->data);
}
}
int leafs(BinTree *b)//求叶子数
{
int num1,num2;
if(b==NULL) return (0);
else if(b->lchild==NULL && b->rchild==NULL) return (1);
else
{
num1=leafs(b->lchild);
num2=leafs(b->rchild);
return(num1+num2);
}
}
int treedeep(BinTree *p)//求树的深度
{
int ldeep,rdeep,deep;
if(p==NULL) deep=0;
else
{
ldeep=treedeep(p->lchild);
rdeep=treedeep(p->rchild);
deep=(ldeep>rdeep?ldeep:rdeep)+1;
}
return deep;
}
BinTree *swap(BinTree *p)//交换二叉树的所有结点的左右子树
{
BinTree *stack[max];
int k=0;
stack[k]=NULL;
if(p!=NULL)
{
stack[++k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=swap(p->lchild);
p->rchild=swap(p->rchild);
}
return p;
}
//按完全二叉树思想将输入的字符串生成二叉树
#define max 30
#define NULL 0
#include
#include
typedef struct Bnode
{ char data;
struct Bnode *lchild,*rchild;
}Btree;
void preorder(Btree *t)
{ if(t)
{ printf("%c",t->data);
if(t->lchild)
{ printf("->");
preorder(t->rchild);
}
if(t->rchild)
{ printf("->");
preorder(t->rchild);
}
}
}
void inorder(Btree *t)
{ if(t)
{ inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
void postorder(Btree *t)
{ if(t)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
int leafs(Btree *b)
{ int num1,num2;
if(b==NULL) return(0);
else if(b->lchild==NULL&&b->rchild==NULL) return(1);
else
{
num1=leafs(b->lchild);
num2=leafs(b->rchild);
return(num1+num2);
}
}
int treedeep(Btree *p)
{ int ldeep,rdeep,deep;
if(p==NULL) deep=0;
else
{ ldeep=treedeep(p->lchild);
rdeep=treedeep(p->rchild);
deep=(ldeep>rdeep?ldeep:rdeep)+1;
}
return deep;
}
Btree *swap(Btree *p)
{ Btree *stack[max];
int k=0;
stack[k]=NULL;
if(p!=NULL)
{ stack[++k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=swap(p->lchild);
p->rchild=swap(p->rchild);
}
return p;
}
Btree *cretree(char *str,int i,int m)
{ Btree p;
if(i>=m)
return NULL;
p=(Btree *)malloc(sizeof(Btree));
p->data=str[i];
p->lchild=cretree(str,2*i+1,m);
p->rchild=cretree(str,2*i+2,m);
return p;
}
void main()
{ int i,n;
char str[max];
Btree *root;
printf("请输入二叉树的结点数:");
scanf("%d",&n);
getchar();//输入数字
printf("请输入长度为 %d 的字符串 :",n);
for(i=0;i
#include
typedef struct Bnode
{ char data;
struct Bnode *lchild,*rchild;
}Btree;
void preorder(Btree *t)
{ if(t)
{ printf("%c",t->data);
if(t->lchild)
{ printf("->");
preorder(t->lchild);
}
if(t->rchild)
{ printf("->");
preorder(t->rchild);
}
}
}
void inorder(Btree *t)
{ if(t)
{ inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
void postorder(Btree *t)
{ if(t)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
int leafs(Btree *b)
{ int num1,num2;
if(b==NULL) return(0);
else if(b->lchild==NULL&&b->rchild==NULL) return(1);
else
{
num1=leafs(b->lchild);
num2=leafs(b->rchild);
return(num1+num2);
}
}
int treedeep(Btree *p)
{ int ldeep,rdeep,deep;
if(p==NULL) deep=0;
else
{ ldeep=treedeep(p->lchild);
rdeep=treedeep(p->rchild);
deep=(ldeep>rdeep?ldeep:rdeep)+1;
}
return deep;
}
Btree *swap(Btree *p)
{ Btree *stack[max];
int k=0;
stack[k]=NULL;
if(p!=NULL)
{ stack[++k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=swap(p->lchild);
p->rchild=swap(p->rchild);
}
return p;
}
Btree *cretree()
{ Btree *p;
char ch;
ch=getchar();
if(ch=='#') return NULL;
else
{
p=(Btree *)malloc(sizeof(Btree));
p->data=ch;
p->lchild=cretree();
p->rchild=cretree();
}
return p;
}
void main()
{
Btree *root;
;
root=cretree();
printf("\n");
//先根遍历
printf("\n先根遍历结果:");
preorder(root);
printf("\n");
//中根遍历
printf("\n中根遍历结果:");
inorder(root);
printf("\n");
//后根遍历
printf("\n后根遍历结果:");
postorder(root);
printf("\n");
printf("\n叶子数为：%d\n",leafs(root));
printf("\n树的深度为：%d\n",treedeep(root));
printf("\n交换左右子树后先序遍历序列为：");
preorder(swap(root));
printf("\n\n");
}改过 #define max 30
#include
#include
typedef struct Bnode
{ char data;
struct Bnode *lchild,*rchild;
}Btree;
void preorder(Btree *t)
{ if(t)
{ printf("%c",t->data);
if(t->lchild)
{ printf("->");
preorder(t->lchild);
}
if(t->rchild)
{ printf("->");
preorder(t->rchild);
}
}
}
void inorder(Btree *t)
{ if(t)
{ inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
void postorder(Btree *t)
{ if(t)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
int leafs(Btree *b)
{ int num1,num2;
if(b==NULL) return(0);
else if(b->lchild==NULL&&b->rchild==NULL) return(1);
else
{
num1=leafs(b->lchild);
num2=leafs(b->rchild);
return(num1+num2);
}
}
int treedeep(Btree *p)
{ int ldeep,rdeep,deep;
if(p==NULL) deep=0;
else
{ ldeep=treedeep(p->lchild);
rdeep=treedeep(p->rchild);
deep=(ldeep>rdeep?ldeep:rdeep)+1;
}
return deep;
}
Btree *swap(Btree *p)
{ Btree *stack[max];
int k=0;
stack[k]=NULL;
if(p!=NULL)
{ stack[++k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=swap(p->lchild);
p->rchild=swap(p->rchild);
}
return p;
}
Btree *cretree()
{ Btree *p;
char ch;
if((ch=getchar())=='#') return NULL;
else
{
p=(Btree *)malloc(sizeof(Btree));
p->data=ch;
p->lchild=cretree();
p->rchild=cretree();
}
return p;
}
void main()
{
Btree *root;
root=cretree();
printf("\n");
//先根遍历
printf("\n先根遍历结果:");
preorder(root);
printf("\n");
//中根遍历
printf("\n中根遍历结果:");
inorder(root);
printf("\n");
//后根遍历
printf("\n后根遍历结果:");
postorder(root);
printf("\n");
printf("\n叶子数为：%d\n",leafs(root));
printf("\n树的深度为：%d\n",treedeep(root));
printf("\n交换左右子树后先序遍历序列为：");
preorder(swap(root));
printf("\n\n");
}
#include"stdio.h"
#include"string.h"
#include
#include
#define max 20 //结点的最大个数
using namespace std;
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
BinTree CreatBinTree(void)
{//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
void Preorder(BinTree bt)
{//========NLR 先序遍历=============
if(bt!=NULL) {
printf("%c",bt->data); //访问结点
Preorder(bt->lchild); //先序遍历左子树
Preorder(bt->rchild); //先序遍历右子树
}
}
void Inorder(BinTree bt)
{//========LNR 中序遍历===============
if(bt!=NULL) {
Inorder(bt->lchild);
printf("%c",bt->data);
Inorder(bt->rchild);
}
}
void Postorder(BinTree bt)
{
if(bt!=NULL)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->data);
}
}
int TreeDepth(BinTree bt)
{
int hl,hr,max;
if(bt)
{
hl=TreeDepth(bt->lchild); //求左深度
hr=TreeDepth(bt->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
void Levelorder(BinTree T)
{//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
void main()
{ BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //输入二叉树的先序序列，用#代表虚结点
root=CreatBinTree(); //创建二叉树，返回根结点
do
{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Inorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i)
{
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); break;
default: exit(1);
}
printf("\n");
}
while(i!=0);
}
浙公网安备 33021202002483