《数据结构》实验报告（四）——二叉树的遍历及相关应用

野性酷女 2022-12-24 12:57 88阅读 0赞

*注：代码直接从实验报告上复制的，可能格式啥的有错误。*  
**一、实验目的**  
(1) 掌握用 C 语言调试程序的基本方法。  
(2) 掌握二叉树的基本定义及其存储实现。  
(3) 掌握二叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。  
**二、实验环境**  
Windows 10，Microsoft Visual C++ 2010 Express  
**三、实验内容**  
1、内容描述  
用递归的方法实现以下二叉树算法：  
(1) 以二叉链表表示二叉树，建立一棵二叉树（先序）；  
(2) 输出二叉树的中序遍历结果；  
(3) 输出二叉树的前序遍历结果；  
(4) 输出二叉树的后序遍历结果；  
(5) 计算二叉树的深度；  
(6) 统计二叉树的叶子结点个数。  
2、实现代码

#include<stdio.h>
    typedef struct BiTNode{
        
    	char data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //先序建立一棵二叉树
    void createBiTree(BiTree &T){
        
    	char str;
    	scanf("%c",&str);
    	if(str=='#')
    		T=NULL;
    	else{
        
    		T=new BiTNode;
    		T->data=str;
    		createBiTree(T->lchild);
    		createBiTree(T->rchild);
    	}
    }
    
    //中序遍历
    void inorder(BiTree T){
         
    	if(T!=NULL){
         
    		inorder(T->lchild);  //递归遍历左子树
    		printf("%c",T->data);//访问根结点
    		inorder(T->rchild);  //递归遍历右子树
    	}
    }
    
    //前序遍历
    void preorder(BiTree T){
         
    	if(T!=NULL){
         
    		printf("%c",T->data);//访问根结点
    		preorder(T->lchild); //递归遍历左子树
    		preorder(T->rchild); //递归遍历右子树
    	}
    }
    
    //后序遍历
    void postorder(BiTree T){
         
    	if(T!=NULL){
         
    		postorder(T->lchild); //递归遍历左子树
    		postorder(T->rchild); //递归遍历右子树
    		printf("%c",T->data); //访问根结点
    	}
    }
    
    //二叉树深度
    int height(BiTree T){
        
    	int m,n;
    	if(T==NULL)
    		return 0;
    	else{
        
    		m=height(T->lchild);
    		n=height(T->rchild);
    		return m>n?m+1:n+1;
    	}
    }
    
    //叶子结点的个数
    int leafnode(BiTree T){
        
    	if(T==NULL)
    		return 0;
    	else if(T->lchild==NULL&&T->rchild==NULL)
    		return 1;
    	else
    		return leafnode(T->lchild)+leafnode(T->rchild);
    }
    
    void main(){
        
    	BiTree T;
    	printf("输入字符顺序：");
    	createBiTree(T);
    	printf("(1)中序遍历的结果为：");
    	inorder(T);
    	printf("\n");
    	printf("(2)前序遍历的结果为：");
    	preorder(T);
    	printf("\n");
    	printf("(3)后序遍历的结果为：");
    	postorder(T);
    	printf("\n");
    	printf("(4)二叉树深度为：%d\n",height(T));
    	printf("(5)叶子结点个数为：%d\n",leafnode(T));
    }

**三、运行结果**  
![运行结果][20201128140942593.png]

[20201128140942593.png]: /images/20221120/6885a2df89c64507941e104e36f0529d.png