二叉树的各种遍历，二叉搜索树的建立，前中序构建二叉树

#include<iostream> #include<stack> #include<queue> using namespace std; //****************** The BinaryTreeNode ***************** template<class T> class BinaryTreeNode { public: T info; BinaryTreeNode<T>* LeftChild; //Left Child BinaryTreeNode<T>* RightChild; //Right Child public: BinaryTreeNode(T ele,BinaryTreeNode<T>*L=0,BinaryTreeNode<T>*R=0); T value()const; //Get the value of the node BinaryTreeNode<T> * leftchild()const;//Get the left child BinaryTreeNode<T> * rightchild()const;//Get the right child void setLeftChild(BinaryTreeNode<T>*p=0);//Set the left child void setRightChild(BinaryTreeNode<T>*p=0);//Set the right child void setValue(const T & date);//Set the value bool isLeaf();//Make sure if it is the leaf //BinaryTreeNode<T> &operator=(const BinaryTreeNode<T>& Node); }; template<class T> BinaryTreeNode<T>::BinaryTreeNode(T ele,BinaryTreeNode<T> *L,BinaryTreeNode<T> *R) { info=ele; LeftChild=L; RightChild=R; } template<class T> T BinaryTreeNode<T>::value()const { return info; } template<class T> BinaryTreeNode<T>* BinaryTreeNode<T>::leftchild()const { return LeftChild; } template<class T> BinaryTreeNode<T>* BinaryTreeNode<T>::rightchild()const { return RightChild; } template<class T> void BinaryTreeNode<T>::setLeftChild(BinaryTreeNode<T>*p) { LeftChild=p; } template<class T> void BinaryTreeNode<T>::setRightChild(BinaryTreeNode<T>*p) { RightChild=p; } template<class T> void BinaryTreeNode<T>::setValue(const T &date) { info=date; } template<class T> bool BinaryTreeNode<T>::isLeaf() { if(LeftChild==0&&RightChild==0) return true; return false; } //*************** The BinaryTree ***************** template<class T> class BinaryTree { private: BinaryTreeNode<T> *root; public: BinaryTree(){root=0;} ~BinaryTree(){DeleteBinaryTree(root);} bool isEmpty(); BinaryTreeNode<T> *Root(){return root;} BinaryTreeNode<T> *Parent(BinaryTreeNode<T> *current);//get their parent node BinaryTreeNode<T> *LeftSibling(BinaryTreeNode<T> *current);//get their left tree BinaryTreeNode<T> *RightSibling(BinaryTreeNode<T> *current);//get their right tree void visit(T Date); void CreatTree(const T info,BinaryTree<T> &Left,BinaryTree<T> &Right);//creat a new tree with trees void CreatTree(const T info,BinaryTreeNode<T> *Left,BinaryTreeNode<T> *Right);// creat a new tree with nodes void LevelOrder(BinaryTreeNode<T> *Root); //the LeveOrder void PreOrderRe(BinaryTreeNode<T>*Root);//the preorder with recursion void PreOrderNoRe(BinaryTreeNode<T>*Root);//the preorder with no recursion void InOrderRe(BinaryTreeNode<T>*Root);//the iborder with no recursion void InOrderNoRe(BinaryTreeNode<T>*Root);//the inorder with no recursion void PostOrderRe(BinaryTreeNode<T>*Root);//the postorder with no recursion void PostOrderNoRe(BinaryTreeNode<T>*Root);//the postorder with no recursion void DeleteBinaryTree(BinaryTreeNode<T>*Root);//delete the binarytree }; template<class T> bool BinaryTree<T>::isEmpty() { if(root==0) return true; return false; } template<class T> BinaryTreeNode<T> *BinaryTree<T>::Parent(BinaryTreeNode<T>*current) { using std::stack; stack<BinaryTreeNode<T>*> Sta; BinaryTreeNode<T>* p=root; if(p!=0 && current!=0) { while(!Sta.empty()||p!=0) { if(p!=0) { if(current==p->leftchild()||current==p->rightchild()) return p; Sta.push(p); p=p->leftchild(); } else { p=Sta.top(); Sta.pop(); p=p->rightchild(); } } } else { cout<<"the point is null\n"; return NULL; } } template<class T> BinaryTreeNode<T> * BinaryTree<T>::LeftSibling(BinaryTreeNode<T>*current) { return current->leftchild(); } template<class T> BinaryTreeNode<T> * BinaryTree<T>::RightSibling(BinaryTreeNode<T>*current) { return current->rightchild(); } template<class T> void BinaryTree<T>::visit(T date) { cout<<date<<" "; } template<class T> void BinaryTree<T>::CreatTree(const T info,BinaryTree<T> &Left,BinaryTree<T> &Right) { root=new BinaryTreeNode<T>(info,Left.root,Right.root); Left.root=Right.root=0; } template<class T> void BinaryTree<T>::CreatTree(const T info,BinaryTreeNode<T> *Left,BinaryTreeNode<T> *Right) { root=new BinaryTreeNode<T>(info,Left,Right); } template<class T> void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>*Root) { using std::queue; queue<BinaryTreeNode<T>*> Qu; BinaryTreeNode<T> *p=Root; if(p) Qu.push(p); else { cout<<"the root is null"; return ; } while(!Qu.empty()) { p=Qu.front(); visit(p->value()); Qu.pop(); if(p->leftchild()!=0) { Qu.push(p->leftchild()); } if(p->rightchild()!=0) { Qu.push(p->rightchild()); } } } template<class T> void BinaryTree<T>::PreOrderRe(BinaryTreeNode<T>*Root) { if(Root!=0) { visit(Root->value()); PreOrderRe(Root->leftchild()); PreOrderRe(Root->rightchild()); } } template<class T> void BinaryTree<T>::PreOrderNoRe(BinaryTreeNode<T>*Root) { using std::stack; stack<BinaryTreeNode<T>*> St; BinaryTreeNode<T>*p=Root; St.push(0); while(p) { visit(p->value()); if(p->rightchild()!=0) { St.push(p->rightchild()); } if(p->leftchild()!=0) { p=p->leftchild(); } else { p=St.top(); St.pop(); } } } template<class T> void BinaryTree<T>::InOrderRe(BinaryTreeNode<T>*Root) { if(Root) { InOrderRe(Root->leftchild()); visit(Root->value()); InOrderRe(Root->rightchild()); } } template<class T> void BinaryTree<T>::InOrderNoRe(BinaryTreeNode<T>*Root) { using std::stack; stack<BinaryTreeNode<T>*> St; BinaryTreeNode<T>*p=Root; while(!St.empty()||p!=0) { if(p!=0) { St.push(p); p=p->leftchild(); } else { p=St.top(); St.pop(); visit(p->value()); p=p->rightchild(); } } } template<class T> void BinaryTree<T>::PostOrderRe(BinaryTreeNode<T>*Root) { if(Root!=0) { PostOrderRe(Root->leftchild()); PostOrderRe(Root->rightchild()); visit(Root->value()); } } template<class T>//maybe have some problems void BinaryTree<T>::PostOrderNoRe(BinaryTreeNode<T>*Root) { BinaryTreeNode<T>*p=Root; BinaryTreeNode<T>*pre=0; using std::stack; stack<BinaryTreeNode<T>*> St; if(Root==0) return; while(!St.empty()||p!=0) { while(p!=0) { St.push(p); p=p->leftchild() ; } p=St.top(); St.pop(); if(p->rightchild()!=0 && p->rightchild()!=pre) { St.push(p); p=p->rightchild(); } else { visit(p->value()); pre=p; p=p->rightchild(); p=0; } } } template<class T> void BinaryTree<T>::DeleteBinaryTree(BinaryTreeNode<T>*Root) { if(Root) { DeleteBinaryTree(Root->leftchild()); DeleteBinaryTree(Root->rightchild()); delete Root; } } void main() { //两种方式建立二叉树 /* BinaryTree<int> tree0; BinaryTree<int> tree7; BinaryTree<int> tree6; BinaryTree<int> tree5; BinaryTree<int> tree4; BinaryTree<int> tree3; BinaryTree<int> tree2; BinaryTree<int> tree1; tree4.CreatTree(4,tree0,tree0); tree5.CreatTree(5,tree0,tree0); tree6.CreatTree(6,tree0,tree0); tree7.CreatTree(7,tree0,tree0); tree3.CreatTree(3,tree6,tree7); tree2.CreatTree(2,tree4,tree5); tree1.CreatTree(1,tree2,tree3); */ BinaryTreeNode<int> *Node7=new BinaryTreeNode<int>(7); BinaryTreeNode<int> *Node6=new BinaryTreeNode<int>(6); BinaryTreeNode<int> *Node5=new BinaryTreeNode<int>(5); BinaryTreeNode<int> *Node4=new BinaryTreeNode<int>(4); BinaryTreeNode<int> *Node3=new BinaryTreeNode<int>(3,Node6,Node7); BinaryTreeNode<int> *Node2=new BinaryTreeNode<int>(2,Node4,Node5); BinaryTree<int> tree1; tree1.CreatTree(1,Node2,Node3); cout<<"广度优先：\n"; tree1.LevelOrder(tree1.Root()); cout<<endl; cout<<"前序递归优先：\n"; tree1.PreOrderRe(tree1.Root()); cout<<endl; cout<<"前序非递归优先：\n"; tree1.PreOrde