二叉树的基本操作

最近被数模搞疯了，没有什么事情是容易的。二叉树有很多性质，也包括一些递归算法，看起来很有意思，递归不要懂得太多。我还是想学习，做一个美男子，呵呵哒。各种不同的遍历，线索树我还没学太懂。 还有树的创建方法（前中序，中后序，输入法（#结束））

#include <iostream> #include<queue> #include<stack> using namespace std; template<class T> class BinaryTreeNode { public: T element; BinaryTreeNode<T> *leftchild; BinaryTreeNode<T> *rightchild; public: BinaryTreeNode(); BinaryTreeNode(const T& ele,BinaryTreeNode<T>*l=NULL,BinaryTreeNode<T>*r=NULL); BinaryTreeNode<T> *getLeftchild(); BinaryTreeNode<T> *getRightchild(); void setLeftchild(BinaryTreeNode<T>*l); void setRightchild(BinaryTreeNode<T>*r); T getValue(); void setValue(T& val); bool isLeaf(); }; template<class T> BinaryTreeNode<T>::BinaryTreeNode() { element=NULL; leftchild=NULL; rightchild=NULL; } template<class T> BinaryTreeNode<T>::BinaryTreeNode(const T& ele,BinaryTreeNode<T>*l,BinaryTreeNode<T>*r) { element=ele; leftchild=l; rightchild=r; } template<class T> BinaryTreeNode<T>* BinaryTreeNode<T>::getLeftchild() { return leftchild; } template<class T> BinaryTreeNode<T>* BinaryTreeNode<T>::getRightchild() { return rightchild; } template<class T> void BinaryTreeNode<T>::setLeftchild(BinaryTreeNode<T>*l) { leftchild=l; } template<class T> void BinaryTreeNode<T>::setRightchild(BinaryTreeNode<T>*r) { rightchild=r; } template<class T> T BinaryTreeNode<T>::getValue() { return element; } template<class T> void BinaryTreeNode<T>::setValue(T & ele) { element=ele; } template<class T> bool BinaryTreeNode<T>::isLeaf() { if(leftchild==NULL&&rightchild==NULL) { return true; } else { return false; } } template<class T> class BinaryTree{ public: BinaryTreeNode<T> *root; int count_0; int count_1; int count_2; int height; int width; T max; public: BinaryTree(){ count_0=0; count_1=0; count_2=0; height=0; width=0; max=NULL; }; //~BinaryTree(); bool isEmpty(); BinaryTreeNode<T> *getParent(BinaryTreeNode<T> *current); bool creat(BinaryTreeNode<T> *&root); bool Creat(); BinaryTreeNode<T> *getLeftSibling(BinaryTreeNode<T> *current); BinaryTreeNode<T> *getRightSibling(BinaryTreeNode<T> *current); void breathFistOrder(BinaryTreeNode<T> *root); void preOrder(BinaryTreeNode<T> *root); void inOrder(BinaryTreeNode<T> *root); void postOrder(BinaryTreeNode<T> *root); void preOrderWithoutRecusion(BinaryTreeNode<T> *root); void inOrderWithoutRecusion(BinaryTreeNode<T> *root); void postOrderWithoutRecusion(BinaryTreeNode<T> *root); void LevelOrder(BinaryTreeNode<T> *root); void deleteBinaryTree(BinaryTreeNode<T> *root); BinaryTreeNode<T>* createBianryTreeByinpost(T A[],int b1,int e1,T B[],int b2,int e2); BinaryTreeNode<T>* createBianryTreeByinpre(T A[],int b1,int e1,T B[],int b2,int e2); int mounted_Degree_1(BinaryTreeNode<T>* root); int mounted_Degree_2(BinaryTreeNode<T>* root); int mounted_Degree_0(BinaryTreeNode<T>* root); int mounted_TreeHeight(BinaryTreeNode<T>* root); int mounted_Width(BinaryTreeNode<T>* root,int level); T mounted_Max(BinaryTreeNode<T>* root); BinaryTreeNode<T>* swap_TreeNode(BinaryTreeNode<T>* root); int delete_LeafNode(BinaryTreeNode<T>* root); bool isComplete_Binarytree(BinaryTreeNode<T>* root); }; template<class T> bool BinaryTree<T>::isComplete_Binarytree(BinaryTreeNode<T>* root) { /* */ using std::queue; queue<BinaryTreeNode<T> *>nodeQueue; BinaryTreeNode<T>* ptr; nodeQueue.push(root); /* store the TreeNOde, NULL NOde included,using queque to memorize the order */ while((ptr=nodeQueue.front())!=NULL) { nodeQueue.pop(); nodeQueue.push(ptr->leftchild); nodeQueue.push(ptr->rightchild); } while(!nodeQueue.empty())/*finally the queue is filled with NULL NOde,if the tree is complete Tree*/ { ptr=nodeQueue.front(); nodeQueue.pop(); if(ptr!=NULL) { return false; } } return true; } template<class T> int BinaryTree<T>::delete_LeafNode(BinaryTreeNode<T>* rt) { if(rt==NULL) { return NULL; } if(rt->rightchild==NULL&&rt->leftchild==NULL) { rt->element=NULL;/*delete,if delete it,clear the tree?*/ } delete_LeafNode(rt->rightchild); delete_LeafNode(rt->leftchild); } template<class T> BinaryTreeNode<T>* BinaryTree<T>::swap_TreeNode(BinaryTreeNode<T>* rt) { if(rt==NULL||(rt->leftchild==NULL&rt->rightchild==NULL)) { return rt; } BinaryTreeNode<T>* temp; temp=rt->leftchild; rt->leftchild=rt->rightchild; rt->rightchild=temp; if(rt->leftchild) { rt->leftchild=swap_TreeNode(rt->leftchild); } if(rt->rightchild) { rt->rightchild=swap_TreeNode(rt->rightchild); } return rt; } template<class T> T BinaryTree<T>::mounted_Max(BinaryTreeNode<T>* rt) { if(rt!=NULL) { if(max<rt->element) { max=rt->element; } mounted_Max(rt->leftchild); mounted_Max(rt->rightchild); return max; } else { return NULL; } } int count[100]; template<class T> int BinaryTree<T>::mounted_Width(BinaryTreeNode<T>* rt,int level) { if(rt==NULL) { return NULL; } count[level]++; if(width<count[level]) { width=count[level]; } mounted_Width(rt->leftchild,level+1); mounted_Width(rt->rightchild,level+1);/*遍历的过程也是++的过程*/ return width; } template<class T> int BinaryTree<T>::mounted_TreeHeight(BinaryTreeNode<T>* rt) { if(rt!=NULL) { int u=mounted_TreeHeight(rt->leftchild); int v=mounted_TreeHeight(rt->rightchild); if(u>v) { height=u+1; return u+1; } height=v+1; return height; } else { return 0; } } template<class T> int BinaryTree<T>::mounted_Degree_1(BinaryTreeNode<T>* rt) { if(rt!=NULL) { if(rt->leftchild==NULL&&rt->rightchild!=NULL) { count_1+=1; mounted_Degree_1(rt->rightchild); } else if(rt->rightchild==NULL&&rt->leftchild!=NULL) { count_1+=1; mounted_Degree_1(rt->leftchild); } else { mounted_Degree_1(rt->leftchild); mounted_Degree_1(rt->rightchild); } } return count_1; } template<class T> int BinaryTree<T>::mounted_Degree_2(BinaryTreeNode<T>* rt) { if(rt!=NULL) { if(rt->leftchild!=NULL&&rt->rightchild!=NULL) { count_2+=1; } mounted_Degree_2(rt->leftchild); mounted_Degree_2(rt->rightchild); } return count_2; } template<class T> int BinaryTree<T>::mounted_Degree_0(BinaryTreeNode<T>* rt) { if(rt!=NULL) { if(!rt->leftchild&&!rt->rightchild) { count_0+=1; } mounted_Degree_0(rt->leftchild); mounted_Degree_0(rt->rightchild); } return count_0; } template<class T> bool createBinaryTree(BinaryTreeNode<T> *b) { cout<<"dd"<<endl; int a; cout<<"ÊäÈë½Ó¿Ú"<<endl; cin>>a; if(a==0) { return true; } else { b=new BinaryTreeNode<T>; b->element=a; createBinaryTree(b->leftchild); createBinaryTree(b->leftchild); } } template<class T> void visit(BinaryTreeNode<T> *root) { cout<<root->element<<endl; } template<class T> void BinaryTree<T>::LevelOrder(BinaryTreeNode<T> *root) { using std::queue; queue<BinaryTreeNode<T> *>nodeQueue; BinaryTreeNode<T> *pointer=root; if(pointer) { nodeQueue.push(pointer); } while(!nodeQueue.empty()) { pointer=nodeQueue.front(); visit(pointer); nodeQueue.pop(); if(pointer->leftchild) nodeQueue.push(pointer->leftchild); if(pointer->rightchild) nodeQueue.push(pointer->rightchild); } } template<class T> void BinaryTree<T>::preOrder(BinaryTreeNode<T> *root) { if(root!=NULL) { visit(root); preOrder(root->leftchild); preOrder(root->rightchild); } } template<class T> void BinaryTree<T>::inOrder(BinaryTreeNode<T> *root) { if(root!=NULL) { inOrder(root->leftchild); visit(root); inOrder(root->rightchild); } } template<class T> void BinaryTree<T>::postOrder(BinaryTreeNode<T> *root) { if(root!=NULL) { postOrder(root->leftchild); postOrder(root->rightchild); visit(root); } } template<class T> void BinaryTree<T>::preOrderWithoutRecusion(BinaryTreeNode<T> *root) { using std::stack; stack<BinaryTreeNode<T> *>nodestack; BinaryTreeNode<T>* pointer=root; while(!nodestack.empty()||pointer) { if(pointer) { nodestack.push(pointer); visit(pointer); pointer=pointer->leftchild; } else { pointer=nodestack.top(); pointer=pointer->rightchild; nodestack.pop(); } } } template<class T> void BinaryTree<T>::inOrderWithoutRecusion(BinaryTreeNode<T> *root) { using std::stack; stack<BinaryTreeNode<T> *>nodestack; BinaryTreeNode<T>* pointer=root; while(!nodestack.empty()||pointer) { if(pointer) { nodestack.push(pointer); pointer=pointer->leftchild; } else { pointer=nodestack.top(); visit(pointer); pointer=pointer->rightchild; nodestack.pop(); } } } template<class T> void BinaryTree<T>::postOrderWithoutRecusion(BinaryTreeNode<T> *root) { using std::stack; stack<BinaryTreeNode<T> *>nodestack; BinaryTreeNode<T>* pointer=root; BinaryTreeNode<T>* pre=root; while(pointer) { for(;pointer->leftchild!=NULL;pointer=pointer->leftchild) nodestack.push(pointer); while(pointer!=NULL&&(pointer->rightchild==NULL||pointer->rightchild==pre)) { visit(pointer); pre=pointer; if(nodestack.empty()) return; pointer =nodestack.top(); nodestack.pop(); } nodestack.push(pointer); pointer=pointer->rightchild; } } template<class T> bool BinaryTree<T>::Creat() { if(creat(root)); return true; return false; } template<class T> bool BinaryTree<T>::creat(BinaryTreeNode<T> *&root) { T tempaval; cin>>tempaval; if(tempaval!='#') { root=new BinaryTreeNode<T>; if(!root) { root=NULL; return false; } root->element=tempaval; if(!creat(root->leftchild)) root->leftchild=NULL; if(!creat(root->rightchild)) root->rightchild=NULL; } else return false; return true; } template <class T> BinaryTreeNode<T>* BinaryTree<T>::createBianryTreeByinpost(T A[],int b1,int e1,T B[],int b2,int e2)/*zhong-hou*/ { T rtdata=B[e2]; int k=0; for(k=b1;k<=e1;k++) { if(A[k]==rtdata) { break; } } if(k>e1) { return NULL; } BinaryTreeNode<T>* root_1=new BinaryTreeNode<T>(rtdata,NULL,NULL); int leftlen=k-b1; int rightlen=e1-k; if(leftlen>0) { root_1->leftchild=createBianryTreeByinpost(A,b1,b1+leftlen-1,B,b2,b2+leftlen-1); } if(rightlen>0) { root_1->rightchild=createBianryTreeByinpost(A,k+1,e1,B,b2+leftlen,e2-1); } return root_1; } template <class T> BinaryTreeNode<T>* BinaryTree<T>::createBianryTreeByinpre(T A[],int b1,int e1,T B[],int b2,int e2)/*zhong-qian*/ { T rtdata=B[b2]; int k=0; for(k=b1;k<=e1;k++) { if(A[k]==rtdata) { break; } } if(k>e1) { return NULL; } BinaryTreeNode<T>* root_1=new BinaryTreeNode<T>(rtdata,NULL,NULL); int leftlen=k-b1; int rightlen=e1-k; if(leftlen>0) { root_1->leftchild=createBianryTreeByinpre(A,b1,b1+leftlen-1,B,b2+1,b2+leftlen); } if(rightlen>0) { root_1->rightchild=createBianryTreeByinpre(A,k+1,e1,B,b2+leftlen+1,e2); } return root_1; } int main() { BinaryTree<char> s; char A[8]={'B','F','D','G','A','C','E','H'}; char B[8]={'F','G','D','B','H','E','C','A'}; char C[8]={'A','B','D','F','G','C','E','H'}; //s.root= s.createBianryTreeByinpost(A,0,7,B,0,7); s.root= s.createBianryTreeByinpre(A,0,7,C,0,7); cout<<"in oder:"<<endl; s.inOrder(s.root); cout<<"----------------"<<endl; s.inOrderWithoutRecusion(s.root); cout<<"post oder:"<<endl; s.postOrder(s.root); cout<<"----------------"<<endl; s.postOrderWithoutRecusion(s.root); cout<<"pre oder:"<<endl; s.preOrder(s.root); cout<<"----------------"<<endl; s.preOrderWithoutRecusion(s.root); cout<<"Level oder:"<<endl; s.LevelOrder(s.root); cout<<"Test width:"<<endl; cout<<s.mounted_Width(s.root,0)<<endl; cout<<"Test height:"<<endl; cout<<s.mounted_TreeHeight(s.root)<<endl; cout<<"Test Degree 0:"<<endl; cout<<s.mounted_Degree_0(s.root)<<endl; cout<<"Test Degree 1:"<<endl; cout<<s.mounted_Degree_1(s.root)<<endl; cout<<"Test Degree 2:"<<endl; cout<<s.mounted_Degree_2(s.root)<<endl; cout<<"Test MaxValue:"<<endl; cout<<s.mounted_Max(s.root)<<endl; cout<<"Test Swap:"<<endl; s.postOrder(s.root); cout<<"----------------"<<endl; s.root=s.swap_TreeNode(s.root); s.postOrder(s.root); cout<<"----------------"<<endl; cout<<"Test deleteLeaf"<<endl; s.delete_LeafNode(s.root); s.postOrder(s.root); cout<<"Test Is copmpleteTree"<<endl; cout<<s.isComplete_Binarytree(s.root); return 0; }