数据结构|二叉树的链式存储（实验6.2）

雨点打透心脏的1/2处 2022-06-06 12:45 175阅读 0赞

# 一、实验目的 #

1、   熟练理解树和二叉树的相关概念，掌握的存储结构和相关操作实现；

2、   掌握树的顺序结构的实现；

3、   学会运用树的知识解决实际问题

# 二、 实验内容 #

1、自己确定一个二叉树（树结点类型、数目和结构自定）利用链式存储结构方法存储。实现树的构造，并完成：

1）用前序遍历、中序遍历、后序遍历输出结点数据；

2）以合理的格式，输出各个结点和双亲、孩子结点信息；

3）输出所有的叶子结点信息；

三、实验步骤

1、依据实验内容，先确定具体的二叉树，并说明结点的数据类型；

template <typename T>
    class Bitree
    {
    	public:
    		Bitree() { root=Creat(root); }  //构造函数
    		~Bitree() { Release(root); }  //析构函数
    		void Preorder() { Preorder(root); }  //前序遍历
    		void Inorder() { Inorder(root); }   //中序遍历
    		void Postorder() { Postorder(root); }   //后序遍历
    		void Leverorder();    //层序遍历
    		void findmessage(T x){ findmessage(root,x); }  //查找各结点的信息
    	private:
    		BiNode<T> *root;  //指向根结点的头指针
    		BiNode<T> *Creat(BiNode<T> *bt);   //构造函数调用
    		void Release (BiNode<T> *bt);
    		void Preorder (BiNode<T> *bt);
    		void Inorder (BiNode<T> *bt);
    		void Postorder (BiNode<T> *bt);
    		void findmessage(BiNode<T> *bt,T x);
    		void Parent(BiNode<T> *bt,T x);
    };

2、设计具体的算法；

2.1构造函数：建立一个二叉树；

2.2建立二叉链表算法：

①输入数据信息，空树的符号为“\#”

②生成结点，分别递归建立左子树和右子树。

2.3析构函数：采用后序遍历，先后释放左子树、右子树、根结点。

2.4前序遍历函数：递归调用，先后遍历根结点的数据域、左子树、右子树。

2.5中序遍历函数：递归调用，先后遍历根结点的左子树、数据域、右子树。

2.6后序遍历函数：递归调用，先后遍历根结点的左子树、右子树、数据域。

3、写出完整程序；

由于结点元素类型不确定，因此采用C++模板机制。

源代码如下：

#include<iostream>
    using namespace std;
    
    template <typename T>
    struct BiNode
    {
    	T data;
    	BiNode<T> *lchild,*rchild;
    };
    
    template <typename T>
    class Bitree
    {
    	public:
    		Bitree() { root=Creat(root); }  //构造函数
    		~Bitree() { Release(root); }  //析构函数
    		void Preorder() { Preorder(root); }  //前序遍历
    		void Inorder() { Inorder(root); }   //中序遍历
    		void Postorder() { Postorder(root); }   //后序遍历
    		void Leverorder();    //层序遍历
    		void findmessage(T x){ findmessage(root,x); }  //查找各结点的信息
    	private:
    		BiNode<T> *root;  //指向根结点的头指针
    		BiNode<T> *Creat(BiNode<T> *bt);   //构造函数调用
    		void Release (BiNode<T> *bt);
    		void Preorder (BiNode<T> *bt);
    		void Inorder (BiNode<T> *bt);
    		void Postorder (BiNode<T> *bt);
    		void findmessage(BiNode<T> *bt,T x);
    		void Parent(BiNode<T> *bt,T x);
    };
    
    template <typename T>
    void Bitree<T>::Preorder(BiNode<T> *bt)
    {
    	if(bt==NULL) return;    //递归调用的结束条件
    	else {
    		cout<<bt->data<<" ";    //访问根结点的数据域
    		Preorder(bt->lchild);  //前序递归遍历左子树
    		Preorder(bt->rchild);  //前序递归遍历右子树
    	}
    }
    
    template <typename T>
    void Bitree<T>::Inorder(BiNode<T> *bt)
    {
    	if(bt==NULL) return;    //递归调用的结束条件
    	else {
    		Inorder(bt->lchild);  //中序递归遍历左子树
    		cout<<bt->data<<" ";    //访问根结点的数据域
    		Inorder(bt->rchild);  //中序递归遍历右子树
    	}
    }
    
    template <typename T>
    void Bitree<T>::Postorder(BiNode<T> *bt)
    {
    	if(bt==NULL) return;    //递归调用的结束条件
    	else {
    		Postorder(bt->lchild);  //后序递归遍历左子树
    		Postorder(bt->rchild);  //后序递归遍历右子树
    		cout<<bt->data<<" ";    //访问根结点的数据域
    	}
    }
    
    template <typename T>
    void Bitree<T>::Leverorder()
    {
    	front = rear =-1;  //
    	if(root == NULL) return;  //
    	Q[++rear] = root;
    	while(front!=rear)
    	{
    		q=Q[++front];   //
    		cout<<q->data;
    		if(q->lchild !=NULL) Q[++rear]=q->lchild;
    		if(q->rchild !=NULL) Q[++rear]=q->rchild;
    	}
    }
    
    template <typename T>
    BiNode<T> *Bitree<T>::Creat(BiNode<T> *bt)
    {
    	char ch;
    	cout<<"输入二叉树的各个结点数据，空树为# ："<<endl;
    	cin>>ch;
    	if(ch == '#') bt=NULL;
    	else {
    		bt= new BiNode<T>; bt->data = ch;
    		bt->lchild=Creat(bt->lchild);
    		bt->rchild=Creat(bt->rchild);
    		
    	}
    	return bt;
    }
    
    template <typename T>
    void Bitree<T>::Release(BiNode<T> *bt)
    {
    	if(bt!=NULL) {
    		Release(bt->lchild);
    		Release(bt->rchild);
    		delete bt;
    	}
    }
    
    template <typename T>
    void Bitree<T>::findmessage(BiNode<T> *bt,T x)
    {
    	int data;
    	if(bt==NULL) return;
    	else{
    		if(bt->data == x){
    			cout<<"结点"<<bt->data<<endl;
                if(bt->lchild!=NULL) cout<<"左孩子为:"<<bt->lchild->data<<endl;  
    			else cout<<"无左孩子"<<endl;  
                if(bt->rchild!=NULL) cout<<"右孩子为:"<<bt->rchild->data<<endl;
    			else cout<<"无右孩子。"<<endl;  
                if(bt==root)  cout<<"该结点为根，无双亲"<<endl;  
                else   Parent(root,x);
    		}
            else{  
                findmessage(bt->lchild,x);  
                findmessage(bt->rchild,x);  
            }
        }
    }
    
    template<typename T>  
    void Bitree<T>::Parent(BiNode<T> *bt,T x)  
    {  
        if(bt==NULL) return;  
        else  
        {  
            if(bt->lchild->data==x||bt->rchild->data==x)    cout<<"双亲为:"<<bt->data<<endl;  
            else{  
                Parent(bt->lchild,x);  
                Parent(bt->rchild,x);  
            }  
        }  
    }
    
    void main()
    {
    	char x; int select;
    	cout<<"创建对象"<<endl;
    	Bitree<char>a;
    	cout<<"【现以各种便利方式输出结点数据】"<<endl;
    	cout<<"前序遍历："<<endl;
    	a.Preorder();
    	cout<<endl;
    	cout<<"中序遍历："<<endl;
    	a.Inorder();
    	cout<<endl;
    	cout<<"后序遍历："<<endl;
    	a.Postorder();
    	cout<<endl;
    	cout<<"【输出结点信息】"<<endl;
    	for(int i=0;i=1;i=select){
    		cout<<"请输入需要查询信息的结点元素"<<endl;
    	    cin>>x;
            a.findmessage(x);
         	cout<<"是否需要继续查询？"<<endl<<"是：1      否：0"<<endl;
    	    cin>>select;
    		if (select==0) break;
    	}
    }

4、总结、运行结果和分析算法效率。

①总结

在程序内创建对象，并通过调用成员函数实现各种功能，如前序遍历、中序遍历、后序遍历，输出结点信息等。

②运行结果如下：

![20171109111836560][]![20171109111850070][]

5、总体收获和不足，疑问等。

整体的实验过程中，我一度因为实验过程困难而选择放弃继续实验。经过冷静地思考以及向同学询问、上网查找解决方法、查找课本等方式，最终还是完成了实验。虽然相关代码仍存有瑕疵，但我会继续努力，继续更改。

这次实验，我发现了自己对于理论学习还是存有不足之处，但总得来说，我对理论知识有了更充分的理解，也能较大程度明白运行原理。

[20171109111836560]: https://img-blog.csdn.net/20171109111836560
[20171109111850070]: /images/20220606/a0319cf7ebbd4005bb393eb37a1456f8.png