树和二叉树实验报告

一、实验目的

1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。

2.掌握用指针类型描述、访问和处理二叉树的运算。

二、实验要求

1.认真阅读和掌握本实验的程序。

2.上机运行本程序。

3.保存和打印出程序的运行结果，并结合程序进行分析。

4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

三、实验内容

1.输入字符序列，建立二叉链表。

2.按先序、中序和后序遍历二叉树（递归算法）。

3.按某种形式输出整棵二叉树。

4.求二叉树的高度。

5.求二叉树的叶节点个数。

6.交换二叉树的左右子树。

7.借助队列实现二叉树的层次遍历。

8.在主函数中设计一个简单的菜单，分别调试上述算法。

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。

四、解题思路

1、先序遍历：访问根结点，先序遍历左子树，先序遍历右子树

2、中序遍历：中序遍历左子树，访问根结点，中序遍历右子树

3、后序遍历：后序遍历左子树，后序遍历右子树，访问根结点

4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。

五、程序清单

#include

#include

#define M 100

t定义二叉树结点值的类型为字符型

t树结点结构

{  

}BiTNode,*BiTree;

BiTree que[M];

int front=0,rear=0;

//函数原型声明

BiTNode *creat_bt1();

BiTNode *creat_bt2();

void preorder(BiTNode *p);

void inorder(BiTNode *p);

void postorder(BiTNode *p);

void enqueue(BiTree);

BiTree delqueue( );

void levorder(BiTree);

int treedepth(BiTree);

void prtbtree(BiTree,int);

void exchange(BiTree);

int leafcount(BiTree);

void paintleaf(BiTree);

BiTNode *t;

int count=0;

//主函数

void main()

{

 主菜单===================");

        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.计算二叉树的高度");

        printf("\\n\\n   8.计算二叉树中叶结点个数");

        printf("\\n\\n   9.交换二叉树的左右子树");

        printf("\\n\\n   10.打印二叉树");

        printf("\\n\\n   0.结束程序运行");

        printf("\\n   请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");

            case 1:t=creat_bt1( );break;                  //调用性质5建立二叉树算法

 请输入二叉树各结点值:");fflush(stdin);

            t=creat_bt2();break;                        //调用递归建立二叉树算法

 先序遍历二叉树:");

 二叉树为空!\\n");

 中序遍历二叉树:");

 二叉树为空!\\n");

 后序遍历二叉树:");

 二叉树为空!\\n");

 层次遍历二叉树：");

 二叉树为空！\\n");

 二叉树的高度为：%d",treedepth(t));

 二叉树为空！\\n");

 二叉树的叶子结点数为：%d\\n",leafcount(t));

 二叉树的叶结点为：");paintleaf(t);

 二叉树为空！\\n");

 交换二叉树的左右子树：\\n");

 二叉树为空！\\n");

 逆时针旋转90度输出的二叉树：\\n");

 二叉树为空！\\n");

            }   //switch

 再见！按回车键，返回…\\n");

//利用二叉树性质5，借助一维数组V建立二叉树

BiTNode *creat_bt1()

{ BiTNode *t,*p,*v[20];int i,j;Etype e;

/*输入结点的序号i、结点的数据e*/

printf("\\n请输入二叉树各结点的编号和对应的值（如1，a）：");

scanf("%d,%c",&i,&e);

w当i为0，e为'#'时，结束循环

{

    t=p;   //序号为1的结点是根 

 序号为偶数，作为左孩子 

 序号为奇数，作为右孩子 

 请继续输入二叉树各结点的编号和对应的值：");

}

return(t);

}//creat_bt1;

//模仿先序递归遍历方法，建立二叉树

BiTNode *creat_bt2()

{

    if(e=='#')t=NULL;   //对于'#'值，不分配新结点 

 左孩子获得新指针值 

 右孩子获得新指针值

return(t);

//先序递归遍历二叉树

void preorder(BiTNode *p)

{if(p){

//中序递归遍历二叉树

void inorder(BiTNode *p)

{if(p){

} //inorder

//后序递归遍历二叉树

void postorder(BiTNode *p)

{ if(p){ postorder(p->lch);

} //postorder

void enqueue(BiTree T)

{

}

BiTree delqueue( )

{

}

v层次遍历二叉树

{

}

i计算二叉树的高度

{

}

v逆时针旋转90度输出二叉树树形

{int j;

if(bt)

{prtbtree(bt->rch,level+1);

for(j=0;j<=6*level;j++)printf(" ");

printf("%c\\n",bt->data);

prtbtree(bt->lch,level+1);

}

}

void exchange(BiTree bt)  //交换二叉树左右子树

{BiTree p;

if(bt)

{p=bt->lch;bt->lch=bt->rch;bt->rch=p;

exchange(bt->lch);exchange(bt->rch);

}

}

int leafcount(BiTree bt)  //计算叶结点数

{

if(bt!=NULL)

{leafcount(bt->lch);

leafcount(bt->rch);

if((bt->lch==NULL)&&(bt->rch==NULL))

}

return(count);

}

v输出叶结点 

{if(bt!=NULL)

paintleaf(bt->rch);

}

图11.2所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。

图11.2  二叉树示意图

运行结果：

===================主菜单===================

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 1

请输入二叉树各结点的编号和对应的值（如1，a）：1，a

请继续输入二叉树各结点的编号和对应的值：2，b

请继续输入二叉树各结点的编号和对应的值：3，c

请继续输入二叉树各结点的编号和对应的值：4，d

请继续输入二叉树各结点的编号和对应的值：6，e

请继续输入二叉树各结点的编号和对应的值：7，f

请继续输入二叉树各结点的编号和对应的值：9，g

请继续输入二叉树各结点的编号和对应的值：13，h

请继续输入二叉树各结点的编号和对应的值：0，#

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 3

先序遍历二叉树：a  b  d  g  c  e  h  f

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 4

中序遍历二叉树：d  g  b  a  e  h  c  f 

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 5

后序遍历二叉树：g  d  b  h  e  f  c  a  

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 6

层次遍历二叉树： 97 98 99100101102103104

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 7

二叉树的高度为：4

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 8

二叉树的叶子结点数为：3

二叉树的叶结点为： g  h  f

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 9

交换二叉树的左右子树：

 a

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 10

逆时针旋转90度输出的二叉树：

 a

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 2

请输入二叉树各结点值：abd#g###ce#h##f##

===================主菜单===================");

 建立二叉树方法1

 建立二叉树方法2

 先序递归遍历二叉树

 中序递归遍历二叉树

 后序递归遍历二叉树

 层次遍历二叉树

 计算二叉树的高度

 计算二叉树中叶结点个数

 交换二叉树的左右子树

 打印二叉树

 结束程序运行

============================================

 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 0

请按任意键继续. . .

六、调试心得及收获

建立二叉树有两种方法：一种方法是利用二叉树的性质5来建立二叉树；另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。建立后，通过先序、中序、后序遍历，对二叉树有了进一步的理解与掌握。对二叉树中各种计算也更了解了！

七、其他所想到的

一个二叉树，有许多部分构成，每一个部分都需要精心编写，才能对其进行操作，不至于出错。