数据结构二叉树/二叉链表实验

古城微笑少年丶 2023-03-13 05:58 26阅读 0赞

实验五 树及二叉树  
1.实验目的

1.  掌握二叉树的建立与存储；  
    2）掌握二叉树的遍历方法；  
    2.实验要求  
    要求能够熟练运用 DEV C++ 6.0软件所提供的菜单、工具、模型等编写二叉树的相关应用。  
    3.实验内容  
    使用 DEV C++ 6.0 来编写二叉树的中序遍历递归算法。  
    4.实验步骤
2.  先序遍历的顺序建立二叉链表；
3.  中序遍历二叉树的递归算法；  
    5.实验学时：2 学时。  
    6.实验结果：上交所制作的文件和实验报告。  
    实验代码：

#include<iostream>
    using namespace std;
    #define OK 0
    #define Error -1
    static int i = 0;
    static char ch;
    
    typedef struct BiNode{
        
    	char data;
    	struct BiNode *Lchild,*Rchild;
    }BiTNode,*BiTree;
    
    int createBiTree(BiTree &T){
        
    	if(ch=='#')  {
        
    	T=NULL;return OK;
    	}
    	cin>>ch;
    	if(ch=='#')  {
        
    	T=NULL;	cout<<"建造完成，叶子结点共有"<<i<<"个"<<endl;return OK;
    	}
    	else{
        
    		cout<<"建造中...叶子结点现有"<<++i<<"个"<<endl;
    		
    		T=new BiTNode;
    		T->data=ch;
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild); 
    		//Sleep(10);
    	}
    } 
    
    void seeTree(BiTree T){
        
    	if(T)
    	{
        
    		seeTree(T->Lchild);
    		cout << T->data << " ";
    		seeTree(T->Rchild); 
    	}
    
    }
    
    int main()
    {
        
    	BiTree T;
    	cout<<"输入建立二叉列表序列,以#结尾:"<<endl;
    	createBiTree(T);
    	//cout<<T->Rchild->data; 
    	cout<<"中序遍历结果:"<<endl;
    	seeTree(T);
    	cout<<endl; 
    	return 0;
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY0MzkwMA_size_16_color_FFFFFF_t_70]

7.实验小结。  
通过本次实验，我对二叉树和二叉链表的了解更加深入，掌握了对二叉树的先序、中序和后序的遍历。在程序编写过程中，我遇到了一些困难，如：DEV编译器不允许main函数为空；先序建立二叉树时，由于cin>>ch在if语句之前，所以每次递归都要先执行cin>>ch ，影响了函数正常结束，我将ch设为全局变量，并且在输入语句前也加入一个if语句来判断ch的值，使函数功能正常运行。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY0MzkwMA_size_16_color_FFFFFF_t_70]: /images/20230312/6e2ff59878d3437daab89a6dfb4f886b.png