树和二叉树实验报告.pdf

树 和 二 叉 树

一、实验目的

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

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

二、实验要求

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

2. 上机运行本程序。

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

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

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

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

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

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

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立

二叉树有各种不同的方法。一种方法是利用二叉树的性质 5 来建立二叉树，

输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，

数据元素 0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与

先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的

某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申

1

后序遍历左子树，○

4、层次遍历算法：采用一个队列 q，先将二叉树根结点入队列，然后退队列，

输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右

子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达

到按层次遍历二叉树的目的。

五、程序清单

#include<stdio.h>

#include<stdlib.h>

#define M 100

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( );

BiTNode *t;

int count=0;

//主函数

void main()

{

printf("\n\n\n");

printf("\n===================主菜单===================");

printf("\n\n 7.计算二叉树的高度");

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

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

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

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

printf("\n============================================");

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

case 3:if(t)

{printf("先序遍历二叉树:");

preorder(t);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case 4:if(t)

{printf("中序遍历二叉树:");

{printf("后序遍历二叉树:");

postorder(t);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case 6:if(t)

{printf("层次遍历二叉树：");

levorder(t);

printf("\n");

}

else printf("二叉树为空！\n");

break;

case 8:if(t)

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

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