数据结构实验报告，二叉树的基本操作（C语言）

- 日理万妓 2023-09-25 20:54 59阅读 0赞

## 数据结构实验报告，二叉树的基本操作（C语言） ##

--------------------

> 作者：命运之光  
> 专栏：数据结构

--------------------

#### 目录 ####

*  数据结构实验报告，二叉树的基本操作（C语言）
 *   *  实验六 二叉树的基本操作
     *   *  一、需求分析
         *  二、概要设计
         *  三、详细设计
         *  四、调试分析
         *  五、测试结果
         *  附录：源程序代码（带注释）

![在这里插入图片描述][b4f03cfe205346daa3d2aed80b6295cc.jpeg_pic_center]

--------------------

> 实验六 二叉树的基本操作  
> 实验环境：Visual C++或Dev C++  
> 实验目的：  
> 1、掌握二叉树创建；  
> 2、掌握二叉树的遍历及常用算法。  
> 实验内容：  
> 通过完全前序序列创建一棵二叉树，完成如下功能：  
> 1)输出二叉树的前序遍历序列；  
> 2)输出二叉树的中序遍历序列；  
> 3)输出二叉树的后序遍历序列；  
> 4)统计二叉树的结点总数；  
> 5)统计二叉树中叶子结点的个数；

--------------------

### 实验六 二叉树的基本操作 ###

--------------------

#### 一、需求分析 ####

通过完全前序序列创建一棵二叉树，完成如下功能：  
1)创建二叉树；  
2)输出二叉树的前序遍历序列；  
3)输出二叉树的中序遍历序列；  
4)输出二叉树的后序遍历序列；  
5)统计二叉树的结点总数；  
6)统计二叉树中叶子结点的个数；

--------------------

#### 二、概要设计 ####

1.用结构体定义一个二叉树

//定义二叉树（二叉链式）
    typedef struct BTnode {
        
    	char data;
    	struct BTnode* lchild;
    	struct BTnode* rchild;
    }BTnode, * BiTree;

> 其中用字符型来定义数据data  
> 用lchild来定义左子树  
> 用rchild来定义右子树

2.主程序

switch (x) {
        
    		case 1:
    			printf("输入二叉树结点的值:\n");
    			T = creatT();
    			break;
    		case 2:
    			//先序遍历
    			printf("先序遍历二叉树:n");
    			TraverseBiTree(T);
    			break;
    		case 3:
    			//中序遍历
    			printf("中序遍历二叉树:n");
    			InOrderBiTree(T);
    			break;
    		case 4:
    			//后序遍历
    			printf("后序遍历二叉树:n");
    			PostOrderBiTree(T);
    			break;
    		case 5:
    			printf("二叉树的结点总数为:%d\n", count(T));
    			break;
    		case 6:
    			//叶子结点数
    			Leafcount(T, &num);
    			printf("n树的叶子结点个数为:%d", num);
    			break;
    		default:exit(0);
    		}

> 用switch函数来调用自定义中的所有函数来实现函数的调用。

--------------------

#### 三、详细设计 ####

1）定义二叉树

//定义二叉树（二叉链式）
    typedef struct BTnode{
        
       char data;
       struct BTnode *lchild;
       struct BTnode *rchild;
    }BTnode,*BiTree;
    BiTree T;

2）创建二叉树

//创建二叉树
    BiTree creatT(){
        
     BTnode *T; 
     char ch;
     scanf("%c",&ch);
     if(ch=='#')  T=NULL;
     else{
        
    	 T=(BTnode*)malloc(sizeof(BTnode));
         T->data=ch;
         T->lchild=creatT();
         T->rchild=creatT(); 
     }
     return T;
    }

3）先序遍历

void TraverseBiTree(BiTree T) {
        //先序遍历
    //	BTnode *T; 
    	if (T == NULL)
    		return;
    	else {
        
    		printf("%c", T->data);
    		TraverseBiTree(T->lchild);
    		TraverseBiTree(T->rchild);
    	}
    }

4）中序遍历

//中序遍历 
    void InOrderBiTree(BiTree T) {
        
    	if (NULL == T)
    		return;
    	else {
        
    		InOrderBiTree(T->lchild);
    		printf("%c", T->data);
    		InOrderBiTree(T->rchild);
    	}
    }

5）后续遍历

//后序遍历 
    void PostOrderBiTree(BiTree T) {
        
    	if (NULL == T)
    		return;
    	else {
        
    		//中序遍历
    		InOrderBiTree(T->lchild);
    		InOrderBiTree(T->rchild);
    		printf("%c", T->data);
    	}
    }

6）统计二叉树结点的个数

int count(BiTree T){
        
     int num,left,right;
     if(T==NULL) num=0;
     else{
        
       left=count(T->lchild);
       right=count(T->rchild);
       num=left+right+1;
     }
     return num; 
    }

7）统计二叉树叶子结点个数

Leafcount(BiTree T, int num) {
        
    	if (T)
    	{
        
    		if (T->lchild == NULL && T->rchild == NULL)
    		{
        
    			num++;
    			printf("%c", T->data);
    		}
    		Leafcount(T->lchild, num);
    		Leafcount(T->rchild, num);
    	}
    	//return num;
    }

8）菜单

void menu(){
        
    	BiTree T; 
     printf("*****************************************\n");
     printf("1:创建二叉树；\n");
     printf("2:先序遍历二叉树；\n");
     printf("3:中序遍历二叉树；\n");
     printf("4:后序遍历二叉树；\n");
     printf("5:统计二叉树结点个数；\n");
     printf("6:统计二叉树叶子结点个数；\n");
     printf("0:退出！\n");
     printf("*****************************************\n");
    }

9）主函数

int main(){
        
     int x;
     BiTree T; 
     menu();
     scanf("%d",&x);
     getchar();
     while(x){
           
       switch(x){
        
       case 1:
    	   printf("输入二叉树结点的值:\n");
    	   T=creatT();
    	   break;
       case 2:
    	   //先序遍历
    	   	printf("先序遍历二叉树:n");
    		TraverseBiTree(T);
    		break;
       case 3:
    	    //中序遍历
    		printf("中序遍历二叉树:n");
    		InOrderBiTree(T);
    		break;
       case 4:
    	    //后序遍历
    	   	printf("后序遍历二叉树:n");
    		PostOrderBiTree(T);
    		break;
       case 5:
    	    printf("二叉树的结点总数为:%d\n",count(T));
    	    break;
       case 6:
    	    //叶子结点数
    	    count(T);
    		Leafcount(T,num);
    		printf("n树的叶子结点个数为:%d", num);
    		break;
       default:exit(0);
       }
     getchar();
     printf("\n请选择要进行的操作:\n");
     menu();
     scanf("%d",&x);
     }
       printf("________________________________________");
       printf("\n\n");
    }

--------------------

#### 四、调试分析 ####

简单分析：  
相比起之前的实验，要实现二叉树先需要定义出一个结构体，通过对左右子树的查找来实现先序中序以及后续遍历的结果，经行了简单的函数封装调用以及传参，通过switch来实现按钮操作，中途注意逻辑合理不要产生逻辑错误否则可能会导致输出结果的错误。  
经验和体会：  
通过对二叉树的建立我更加的理解了二叉树再程序中的一个执行步骤，先序中序后序遍历之间的不同，对与函数的调用以及传参的运用有了更加深刻的理解。体会到二叉树算法在实际的查找中的便利。

--------------------

#### 五、测试结果 ####

调试测试数据：1、输入二叉树的结点建立二叉树；2、先序便利二叉树；3、中序遍历二叉树；4、后序遍历二叉树；5、统计二叉树结点个数；6、统计二叉树叶子结点个数；  
数据测试如下截图：  
输入：ab\#\#c\#\#  
（1）输入二叉树的结点建立二叉树；  
![在这里插入图片描述][3ae0987cc51546f6998da17acd0f57ea.png]  
（2）先序便利二叉树；  
![在这里插入图片描述][4bd4afabe3484f4fa7b37f0439afdbe8.png]  
（3）中序遍历二叉树；  
![在这里插入图片描述][8b505571a8754ddab3ca09e9ea242420.png]  
（4）后序遍历二叉树；  
![在这里插入图片描述][aeb4ac560e534db983994e484dbd6c94.png]  
（5）统计二叉树结点个数；  
![在这里插入图片描述][2b5639947de34d3ea57e536147fecc45.png]  
（6）统计二叉树叶子结点个数；  
![在这里插入图片描述][bacf135832fb48bfb6ed5dfaf4e9e920.png]

--------------------

#### 附录：源程序代码（带注释） ####

#include "stdio.h"
    #include "string.h"
    #include "stdlib.h"
    int num=0;
    //定义二叉树（二叉链式）
    typedef struct BTnode{
        
       char data;
       struct BTnode *lchild;
       struct BTnode *rchild;
    }BTnode,*BiTree;
    BiTree T;
    //创建二叉树
    BiTree creatT(){
        
     BTnode *T; 
     char ch;
     scanf("%c",&ch);
     if(ch=='#')  T=NULL;
     else{
        
    	 T=(BTnode*)malloc(sizeof(BTnode));
         T->data=ch;
         T->lchild=creatT();
         T->rchild=creatT(); 
     }
     return T;
    }
    void TraverseBiTree(BiTree T) {
        //先序遍历
    //	BTnode *T; 
    	if (T == NULL)
    		return;
    	else {
        
    		printf("%c", T->data);
    		TraverseBiTree(T->lchild);
    		TraverseBiTree(T->rchild);
    	}
    }
    //中序遍历 
    void InOrderBiTree(BiTree T) {
        
    	if (NULL == T)
    		return;
    	else {
        
    		InOrderBiTree(T->lchild);
    		printf("%c", T->data);
    		InOrderBiTree(T->rchild);
    	}
    }
    //后序遍历 
    void PostOrderBiTree(BiTree T) {
        
    	if (NULL == T)
    		return;
    	else {
        
    		//中序遍历
    		InOrderBiTree(T->lchild);
    		InOrderBiTree(T->rchild);
    		printf("%c", T->data);
    	}
    }
    //统计二叉树结点的个数
    int count(BiTree T){
        
     int num,left,right;
     if(T==NULL) num=0;
     else{
        
       left=count(T->lchild);
       right=count(T->rchild);
       num=left+right+1;
     }
     return num; 
    }
    //结点数 
    Leafcount(BiTree T, int num) {
        
    	if (T)
    	{
        
    		if (T->lchild == NULL && T->rchild == NULL)
    		{
        
    			num++;
    			printf("%c", T->data);
    		}
    		Leafcount(T->lchild, num);
    		Leafcount(T->rchild, num);
    	}
    	//return num;
    }
    //菜单
    void menu(){
        
    	BiTree T; 
     printf("*****************************************\n");
     printf("1:创建二叉树；\n");
     printf("2:先序遍历二叉树；\n");
     printf("3:中序遍历二叉树；\n");
     printf("4:后序遍历二叉树；\n");
     printf("5:统计二叉树结点个数；\n");
     printf("6:统计二叉树叶子结点个数；\n");
     printf("0:退出！\n");
     printf("*****************************************\n");
    }
    //主函数
    int main(){
        
     int x;
     BiTree T; 
     menu();
     scanf("%d",&x);
     getchar();
     while(x){
           
       switch(x){
        
       case 1:
    	   printf("输入二叉树结点的值:\n");
    	   T=creatT();
    	   break;
       case 2:
    	   //先序遍历
    	   	printf("先序遍历二叉树:n");
    		TraverseBiTree(T);
    		break;
       case 3:
    	    //中序遍历
    		printf("中序遍历二叉树:n");
    		InOrderBiTree(T);
    		break;
       case 4:
    	    //后序遍历
    	   	printf("后序遍历二叉树:n");
    		PostOrderBiTree(T);
    		break;
       case 5:
    	    printf("二叉树的结点总数为:%d\n",count(T));
    	    break;
       case 6:
    	    //叶子结点数
    	    count(T);
    		Leafcount(T,num);
    		printf("n树的叶子结点个数为:%d", num);
    		break;
       default:exit(0);
       }
     getchar();
     printf("\n请选择要进行的操作:\n");
     menu();
     scanf("%d",&x);
     }
       printf("________________________________________");
       printf("\n\n");
    }

> 适用于：  
> 大一数据结构实验课实验报告——二叉树的练习（C语言版）

![在这里插入图片描述][4beebf5572c744898000a2f087ac9d52.jpeg_pic_center]

[b4f03cfe205346daa3d2aed80b6295cc.jpeg_pic_center]: https://img-blog.csdnimg.cn/b4f03cfe205346daa3d2aed80b6295cc.jpeg#pic_center
[3ae0987cc51546f6998da17acd0f57ea.png]: https://img-blog.csdnimg.cn/3ae0987cc51546f6998da17acd0f57ea.png
[4bd4afabe3484f4fa7b37f0439afdbe8.png]: https://img-blog.csdnimg.cn/4bd4afabe3484f4fa7b37f0439afdbe8.png
[8b505571a8754ddab3ca09e9ea242420.png]: https://img-blog.csdnimg.cn/8b505571a8754ddab3ca09e9ea242420.png
[aeb4ac560e534db983994e484dbd6c94.png]: https://img-blog.csdnimg.cn/aeb4ac560e534db983994e484dbd6c94.png
[2b5639947de34d3ea57e536147fecc45.png]: https://img-blog.csdnimg.cn/2b5639947de34d3ea57e536147fecc45.png
[bacf135832fb48bfb6ed5dfaf4e9e920.png]: https://img-blog.csdnimg.cn/bacf135832fb48bfb6ed5dfaf4e9e920.png
[4beebf5572c744898000a2f087ac9d52.jpeg_pic_center]: https://img-blog.csdnimg.cn/4beebf5572c744898000a2f087ac9d52.jpeg#pic_center