二叉树的实现
#include<iostream>
using?namespace?std;
#include<queue>
#include<stack>
template<class?T>
struct?BinaryTreeNode//節點
{
????BinaryTreeNode(const?T&?x)//構造函數
????????:_data(x)
????????,_left(NULL)
????????,_right(NULL)
????{}
????T?_data;
????BinaryTreeNode<T>*?_left;
????BinaryTreeNode<T>*?_right;
};
template<class?T>
class?BinaryTree
{
public:
????BinaryTree()//構造函數
????????:_root(NULL)//根節點賦空值
????{}
?????
????BinaryTree(const?T*?a,size_t?size)//建立二叉樹
????{
????????size_t?index=0;
????????_root=_CreatTree(a,index,size);
????}
????~BinaryTree()//析構
????{
????????Destroy();
????}
????BinaryTreeNode<T>*?Copy()
????{
????????return?_Copy(_root);
????}
????BinaryTreeNode<T>*?Destroy()//刪除二叉樹
????{
???????return?_Deatroy(_root);
????}
????void?PrevOrder()//前序遍歷
????{
???????_PrevOrder(_root);
???????cout<<endl;
????}
????void?InOrder()//中序遍歷
????{
???????_InOrder(_root);
???????cout<<endl;
????}
????void?PostOrder()//后序遍歷
????{
???????_PostOrder(_root);
???????cout<<endl;
????}??
????void?LevelOrder()//層次遍歷
????{
????????_LevelOrder(_root);
????????cout<<endl;
????}
????int?Size()//計算大小
????{
?????????return?_Size(_root);
?????????cout<<endl;
????}
????int?LeafNum()//葉子節點個數
????{
?????????return?_LeafNum(_root);
?????????cout<<endl;
????}
????int?Hight()//計算二叉樹高度
????{
????????return?_Hight(_root);
????}
????void?PrevOrder_Non_R()//非遞歸前序遍歷
????{
?????????_PrevOrder_Non_R(_root);
?????????cout<<endl;
????}
????void?InOrder_Non_R()//非遞歸中序遍歷
????{
??????????_InOrder_Non_R(_root);
??????????cout<<endl;
????}
????void?PostOrder_Non_R()//非遞歸后序遍歷
????{
??????????_PostOrder_Non_R(_root);
??????????cout<<endl;
????}
protected:
????BinaryTreeNode<T>*?_CreatTree(const?T*?a,size_t&?index,size_t?size)//創建二叉樹
????{
?????????BinaryTreeNode<T>*?root=NULL;
?????????if(index<size&&a[index]!='#')
?????????{
?????????????root=new?BinaryTreeNode<T>(a[index]);//先序創建根節點
?????????????root->_left=_CreatTree(a,++index,size);//遞歸創建左節點
?????????????root->_right=_CreatTree(a,++index,size);//遞歸創建右節點
?????????}
?????????return?root;
????}
????void?_PrevOrder(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????{
????????????return;
????????}
????????else
????????{
????????????cout<<root->_data<<"?";
???????????_PrevOrder(root->_left?);
???????????_PrevOrder(root->_right?);
????????}
????}
????void?_InOrder(BinaryTreeNode<T>*?root)
????{
???????if(root==NULL)
???????{
??????????return;
???????}
??????else
???????{
??????????_InOrder(root->_left?);
??????????cout<<root->_data?<<"?";
??????????_InOrder(root->_right?);
???????}
????}
????void?_PostOrder(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????????return;
????????else
????????{
????????????_PostOrder(root->_left?);
????????????_PostOrder(root->_right?);
????????????cout<<root->_data?<<"?";
????????}
????}
????void?_LevelOrder(BinaryTreeNode<T>*?root)//隊列的使用
????{
???????queue<BinaryTreeNode<T>*>?q;
???????q.push(root);
???????while(root)
???????{
???????????cout<<root->_data?<<"?";
???????????if(!q.empty())
???????????{
??????????????BinaryTreeNode<T>*?front?=q.front();
??????????????q.pop();
??????????????q.push(front->_left?);
??????????????q.push(front->_right?);
???????????}
???????????root=q.front();
???????}
????}
????int?_Size(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????????return?0;
????????return??_Size(root->_left?)+_Size(root->_right?)+1;
????}
????int?_LeafNum(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????????return?0;
????????if((root->_left?==NULL)&&(root->_right?==NULL))
????????????return?1;
?????????
????????return?_LeafNum(root->_left?)+_LeafNum(root->_right?);
????}
????int?_Hight(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????????return?0;
????????if(_Hight(root->_left)?>_Hight(root->_right?))
????????{
????????????return??_Hight(root->_left?)+1;
????????}
????????else
????????{
?????????????return?_Hight(root->_right?)+1;
????????}
????}
????BinaryTreeNode<T>*?_Copy(BinaryTreeNode<T>*?root)
????{
????????if(root==NULL)
????????????return?NULL;
????????else
????????{
????????????BinaryTreeNode<T>*?r=new?BinaryTreeNode<T>(root->_data?);
????????????BinaryTreeNode<T>*?left=_Copy(root->_left?);
????????????BinaryTreeNode<T>*?right=_Copy(root->_right?);
????????????return?r;
????????}
????}
????BinaryTreeNode<T>*?_Deatroy(BinaryTreeNode<T>*&?root)
????{
???????if(root!=NULL)
???????{
???????????_Destroy(root->_left?);
???????????_Deatroy(root->_right?);
???????????delete?root;
???????????root=NULL;
???????}
???????return?root;
????}
????void??_PrevOrder_Non_R(BinaryTreeNode<T>*?root)
????{
????????BinaryTreeNode<T>*?cur=root;
????????stack<BinaryTreeNode<T>*>?s;
????????while(cur!=NULL||!s.empty?())
????????{
????????????while(cur!=NULL)
????????????{
?????????????????cout<<cur->_data?<<"?";
?????????????????s.push(cur);
?????????????????cur=cur->_left?;
????????????}
????????????if(!s.empty?())
????????????{
?????????????????cur=s.top();
?????????????????s.pop();
?????????????????cur=cur->_right?;
????????????}
????????}??????
????}
????void??_InOrder_Non_R(BinaryTreeNode<T>*?root)
????{
????????BinaryTreeNode<T>*?cur=root;
????????stack<BinaryTreeNode<T>*>?s;
????????while(cur!=NULL||!s.empty?())
????????{
????????????while(cur!=NULL)
????????????{
?????????????????s.push(cur);
?????????????????cur=cur->_left?;
????????????}
????????????if(!s.empty?())
????????????{
?????????????????cur=s.top();
?????????????????cout<<cur->_data?<<"?";
?????????????????s.pop();
?????????????????cur=cur->_right?;
????????????}
????????}??????
????}
????void?_PostOrder_Non_R(BinaryTreeNode<T>*?root)
????{
????????BinaryTreeNode<T>*?cur=NULL;
????????BinaryTreeNode<T>*?temp=NULL;
????????stack<BinaryTreeNode<T>*>?s;
????????s.push(root);
????????while(!s.empty?())
????????{
????????????cur=s.top();
????????????if((cur->_left?==NULL?&&?cur->_right?==NULL)||
????????????????(temp!=NULL?&&?(temp==cur->_left||temp==cur->_right)))
????????????{
???????????????cout<<cur->_data?<<"?";
???????????????s.pop();
???????????????temp=cur;
????????????}
????????????else
????????????{
????????????????if(cur->_right?!=NULL)
????????????????{
???????????????????s.push(cur->_right?);
????????????????}
????????????????if(cur->_left?!=NULL)
????????????????{
????????????????????s.push(cur->_left?);
????????????????}
????????????}
????????}??????
????}
protected:
????BinaryTreeNode<T>*?_root;
};
總結
