实验三 树
1.实验目的
通过本实验，使学生加深对二叉树的基本概念的理解；掌握掌握二叉排序树的插入和生成；掌握二叉树遍历操作及应用。
2.实验内容
创建一个二叉树，并进行先序遍历、中序遍历、后序遍历、层次遍历，打印二叉树的叶子结构，并统计叶子结点个数和总结点个数。
3.实验要求
（1）设计一个程序实现上述过程。
（2）采用二叉链表存储结构。
4、实验步骤
#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode { ELEMTYPE data;
struct BiTNode
*lchild,*rchild; } BiTNode;
BiTNode *bulid() /*建树*/
{ BiTNode *q;
BiTNode *s[20];
int i,j; char x;
printf("请按顺序输入二叉树的结点以输入0和*号结束\n");
printf("请输入你要输入的为第几个结点i=\n");
scanf("%d",&i); printf("请输入你要输入该结点的数为x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{
q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x; q->rchild=NULL;
q->lchild=NULL; s[i]=q; if(i!=1)
{ j=i/2; if(i%2==0) s[j]->lchild=q; else s[j]->rchild=q; }
printf("请输入你要输入的为第几个结点x=\n");
scanf("%d",&i); printf("请输入你要输入该结点的数x=");
getchar(); scanf("%c",&x);}
return s[1]; }
void preoder(BiTNode *bt) /*先序遍历*/
{ if(bt!=NULL)
{ printf("%c\n",(bt->data)); preoder(bt->lchild); preoder(bt->rchild); }
}
void InOrder(BiTNode *bt) /*中序遍历*/
{ if(bt!=NULL) { InOrder(bt->lchild); printf("%c\n",bt->data); InOrder(bt->rchild); }
}
void postOrder(BiTNode *bt) /*后序遍历*/
{ if(bt!=NULL) { postOrder(bt->lchild); postOrder(bt->rchild); printf("%c\n",bt->data); }
}
Int main()
{
int a;
BiTNode *bt; bt=bulid();
k1:
printf("需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:"); scanf("%d",&a);
switch(a)
{ case(1): preoder(bt); goto k1; case(2): InOrder(bt); goto k1; case(3): postOrder(bt); goto k1; case(0): break; }
5、实验结果
第二篇：数据结构之二叉树编程实验报告
实验报告：
二叉树
题目：
建立一棵二叉树，数据以字符串形式从键盘输入，在此二叉树上完成：
（1） 前序、中序、后序遍历
（2） 求出叶子数
（3） 求树高
（4） 左右子树交换，输出交换后的前序、中序遍历序列
分析：
建树：
输入的字符串序列为带有空节点的前序遍历序列（空节点用*表示）。
①：前序，中序，后序遍历：递归遍历
②：求叶子数：
当一个节点的左右孩子都是NULL时，此节点即为叶子节点。
③：求树高
当前节点的树高等于其左右孩子树高大的加1。
④：左右子树交换：
对于每个节点，将其左右孩子交换，再递归对其左右子树交换。
测试结果：
附：源码
#include <iostream>
#include <stdlib.h>
using namespace std;
struct Bintree
{
char data;
Bintree* lchild;
Bintree* rchild;
};
Bintree *head;
int sp;
/* 已知一棵二叉树的前序序列，建立这棵树 */
void CreateTree(Bintree *&p,char a[])
{
Bintree *temp;
if(a[sp]!=0)
{
if(a[sp]=='*')
{
p=NULL;
sp++;
return ;
}
p=new Bintree;
p->data=a[sp++];
CreateTree(p->lchild,a);
CreateTree(p->rchild,a);
}
else p=NULL;
}
/* 求一棵树的高度 */
int Depth(Bintree *&t)
{
int lh , rh ;
if( t == NULL )
{
return 0 ;
}
else
{
lh = Depth( t->lchild ) ;
rh = Depth( t->rchild ) ;
return ( lh > rh ? lh : rh ) + 1 ;
}
}
/* 将二叉树的左右子树互换 */
void Exchange1(Bintree *&t)
{
Bintree *temp;
if(t)
{
Exchange1(t->lchild);
Exchange1(t->rchild);
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
}
}
/* 按照前序递归遍历二叉树 */
void Preorder1(Bintree *&t)
{
if(t!=NULL)
{
printf("%c",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}
/* 按照中序递归遍历二叉树 */
void Inorder1(Bintree *&t)
{
if(t!=NULL)
{
Inorder1(t->lchild);
printf("%c",t->data);
Inorder1(t->rchild);
}
}
/* 按照后序递归遍历二叉树 */
void Posorder1(Bintree *&t)
{
if(t!=NULL)
{
Posorder1(t->lchild);
Posorder1(t->rchild);
printf("%c",t->data);
}
}
/* 递归法求叶子结点个数 */
int Leaves_Num1(Bintree *&t)
{
if(t)
{
if(t->lchild==NULL&&t->rchild==NULL)
{
return 1;
}
return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild);
}
return 0;
}
/*******************************************/
int main ()
{
char a[100];
memset(a,0,sizeof(a));
cout<<"输入带有空节点的前序遍历序列（空节点用*表示）"<<endl;
cin>>a;
sp=0;
CreateTree(head,a);
cout<<"前序遍历："<<endl;
Preorder1(head);
cout<<endl;
cout<<"中序遍历："<<endl;
Inorder1(head);
cout<<endl;
cout<<"后序遍历："<<endl;
Posorder1(head);
cout<<endl;
cout<<"叶子数："<<Leaves_Num1(head)<<endl;
cout<<"树高："<<Depth(head)<<endl;
cout<<"左右子树交换后"<<endl;
Exchange1(head);
cout<<"前序遍历："<<endl;
Preorder1(head);
cout<<endl;
cout<<"中序遍历："<<endl;
Inorder1(head);
cout<<endl;
cout<<"后序遍历："<<endl;
Posorder1(head);
cout<<endl;
return 0;
}