實驗五 樹和二叉樹實驗2

一、實驗目的

1、   熟練了解樹和二叉樹的相關概念，掌握的存儲結構和相關操作實作；

2、   掌握樹的順序結構的實作；

3、   學會運用樹的知識解決實際問題

二、 實驗内容

1、自己确定一個二叉樹（樹結點類型、數目和結構自定）利用鍊式存儲結構方法存儲。實作樹的構造，并完成：

1）用前序周遊、中序周遊、後序周遊輸出結點資料；

2）以合理的格式，輸出各個結點和雙親、孩子結點資訊；

3）輸出所有的葉子結點資訊；

三、代碼

#include<iostream>
using namespace std;
template <class Datatype>  //二叉連結清單
struct BiNode{
Datatype data;
BiNode<Datatype >*lchild,*rchild;
} ;
int count=0;
template<class Datatype>
class BiTree{
public:
	BiTree(){root=Creat(root);}
	~BiTree(){Release(root);}
	void PreOeder(){PreOrder(root);}
	void InOrder(){InOrder(root);}
	void PostOrder(){PostOrder(root);}
	void LeverOrder();
	int Count(){ return Count(root);}
private:
	BiNode <Datatype> *root;
	BiNode <Datatype >*Creat(BiNode<Datatype>* bt);
	void Release(BiNode <Datatype> *bt);
	void PreOrder(BiNode<Datatype> *bt);
	void InOrder(BiNode<Datatype> *bt);
	void PostOrder(BiNode<Datatype> *bt);
	int Count(BiNode<Datatype> *bt);
}; 
template<class Datatype>
void BiTree<Datatype>::PreOrder(BiNode<Datatype>*bt){
if(bt==NULL) return;
else{
cout<<bt->data<<" ";
PreOrder(bt->lchild );
PreOrder(bt->rchild );
}
}
template<class Datatype>
void BiTree<Datatype>::InOrder(BiNode<Datatype> *bt)
{
if(bt==NULL)return;
else
{
InOrder (bt->lchild );
cout<<bt->data<<" ";
InOrder(bt->rchild);
}
}
template<class Datatype>
void BiTree<Datatype>::PostOrder(BiNode<Datatype>*bt){
if(bt==NULL) return;
else{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout<<bt->data<<" ";
}
}template<class Datatype>
void BiTree<Datatype>::LeverOrder()
{
	BiNode<Datatype>*Q[20],*q;
	int rear,front; 
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<class Datatype>
BiNode <Datatype>*BiTree<Datatype>::Creat(BiNode<Datatype>*bt){
	char ch;
cin>>ch;
if(ch=='#') bt=NULL;
else{
bt=new BiNode<Datatype>;
bt->data=ch;
bt->lchild=Creat(bt->lchild);
bt->rchild=Creat(bt->rchild);
}
return bt;
}
template<class Datatype>
void BiTree<Datatype>::Release(BiNode<Datatype>*bt)
{
	if(bt!=NULL)
	{
	Release(bt->lchild);
	Release(bt->rchild);
	delete bt;
	}
}
template<class Datatype>
int BiTree<Datatype>::Count(BiNode<Datatype> *bt)
{
    if(bt == NULL)
        return 0;
    BiNode<Datatype> *p = bt;
    if(p->lchild == NULL && p->rchild == NULL)
        return 1;
    return (Count(p->lchild) + Count(p->rchild));
	return bt->data;
}

int main(){
	cout<<"輸入樣式："<<endl;
	BiTree<char> b;
	cout<<"前序周遊";
	b.PreOeder();
	cout<<endl;
	cout<<"中序周遊";
	b.InOrder();
	cout<<endl;
	cout<<"後序周遊";
	b.PostOrder ();
	cout<<endl;
	cout<<"層序周遊";
	b.LeverOrder();
	cout<<endl;
	cout<<"此二叉樹葉子的結點個數為："<<b.Count();
	cout<<endl;
	return 0;
}
           

四、樹的形狀

五、運作結果