二叉樹的實作及其操作

一些常用的資料結構必須了解：比如基本的三種資料結構：連結清單，棧，隊列，其中連結清單是最基礎，實作了連結清單就可以利用繼承或者合成的關系實作棧或者隊列，他們簡單在于都是線性結構；進階一點的就是二叉樹，堆和優先隊列，而二叉樹是關鍵！

1、建立：

類似于連結清單的的建立，如建立：   root ---->   60

                                                     left:55                           right:100

這樣簡單二叉樹：有結構體建立節點法和類構造法：

template<typename T>
struct treenode{
T ele;
treenode<T>*left;
treenode<T>*right;};
int main(){
	treenode<int> left={55,NULL,NULL};
	treenode<int> right={100,NULL,NULL};
	treenode<int> root={60,&left,&right};
	treenode<int>*p=&root;
	cout<<"the inf:"<<endl;
	cout<<"   "<<p->ele<<endl;
	cout<<left.ele<<"   "<<right.ele<<endl;
system("pause");
return 0;}//結構體建立
           

template<typename T>
class treenode{
public:
T ele;
treenode<T>*left;
treenode<T>*right;
treenode(){left=NULL;
right=NULL;}
treenode(T ele){
	this->ele=ele;
left=NULL;
right=NULL;}
};
           

int main(){
treenode<int> *root=new treenode<int>(60);
root->left=new treenode<int>(55);
root->right=new treenode<int>(100);
cout<<"the inf of tree:"<<endl;
cout<<"   "<<root->ele<<endl;
cout<<root->left->ele<<"   "<<root->right->ele<<endl;
system("pause");
return 0;}//類構造
           

2、插入資料元素

template<typename T>
bool bitree<T>::insert(T ele){
if(root==NULL) root=new treenode<T>(ele);
else{
treenode<T>*parent=NULL;
treenode<T>*p=root;
while(p!=NULL){
	if(ele<p->ele){parent=p;
	p=p->left;}//新元素小于父節點，則做父節點左孩紙
	else if(ele>p->ele){parent=p;p=p->right;}//新元素大于父節點，則做父節點右邊孩紙
	else return false;
	if(ele<parent->ele)parent->left=new treenode<T>(ele);
	else parent->right=new treenode<T>(ele);}
}
           

3、周遊元素

元素的周遊一般常見的有先序(中-左-右)、中序(左-中-右)以及後序(左-右-中)周遊。其實作的思想都是一樣：都是利用遞歸思想：例如先序周遊：先輸出中間目前元素，然後以此元素為父節點繼續先序周遊此節點的左子樹和此節點的右子樹。。。以此周遊下去：

template<typename T>
void bitree<T>::preorder(){
preorder(root);}
template<typename T>
void bitree<T>::preorder(treenode<T>*root){
	if(root==NULL)return ;
	else{
	cout<<root->ele<<" ";
	preorder(root->left);
	preorder(root->right;);}//前序周遊
           

整體定義二叉樹類如下：

template<typename T>
class treenode{
public:
T ele;
treenode<T>*left;
treenode<T>*right;
treenode(){left=NULL;
right=NULL;}
treenode(T ele){
	this->ele=ele;
left=NULL;
right=NULL;}
};

template<typename T>
class bitree{
private:treenode<T>*root;
		int size;
         void inorder(treenode<T>*root);
		 void preorder(treenode<T>*root);
		 void postorder(treenode<T>*root);
public:
	bitree(){root=NULL;size=0;}
	bitree(T ele[],int size);
	bool insert(T ele);
    void inorder();
void preorder();
void postorder();
};
template<typename T>
bitree<T>::bitree(T ele[],int size){
root=new treenode<T>(ele[0]);
this->size=size;;
for(int i=0;i<size;i++)
  insert(ele[i]);}
template<typename T>
bool bitree<T>::insert(T ele){
if(root==NULL) root=new treenode<T>(ele);
else{
treenode<T>*parent=NULL;
treenode<T>*p=root;
while(p!=NULL){
	if(ele<p->ele){parent=p;
	p=p->left;}//新元素小于父節點，則做父節點左孩紙
	else if(ele>p->ele){parent=p;p=p->right;}//新元素大于父節點，則做父節點右邊孩紙
	else return false;}
	if(ele<parent->ele)parent->left=new treenode<T>(ele);
	else parent->right=new treenode<T>(ele);
}
size++;
return true;}
template<typename T>
void bitree<T>::inorder(){
inorder(root);}
template<typename T>
void bitree<T>::inorder(treenode<T>*root){
if(root==NULL) return;
else{
	inorder(root->left);
	cout<<root->ele<<" ";
	inorder(root->right);
	}
}//中序周遊，遞歸
template<typename T>
void bitree<T>::preorder(){
preorder(root);}
template<typename T>
void bitree<T>::preorder(treenode<T>*root){
	if(root==NULL)return;
	else{
	cout<<root->ele<<" ";
	preorder(root->left);
	preorder(root->right);}}//前序周遊
template<typename T>
void bitree<T>::postorder(){
postorder(root);}
template<typename T>
void bitree<T>::postorder(treenode<T>*root){
if(root==NULL) return;
else{postorder(root->left);
postorder(root->right);
cout<<root->ele<<" ";
}}//後序
           

調用結果：