二叉树

构建：二叉树的构建采用的是先序遍历，->先储存根节点然后左右节点，用递归的思想将所有数据放在树中。

代码实现：实现了4种访问方法，先序，中序，后序，和层序的访问方法都采用递归的方式。

#include<iostream>#include<queue>#include<stack>usingnamespacestd;template<classT>structrootnode{T_value;rootnode<T>*_leftnode;rootnode<T>*_rightnode;rootnode<T>(Tvalue):_value(value),_leftnode(NULL),_rightnode(NULL){}};template<classT>classBinaryTree{public:BinaryTree<T>(T*str){T*tmp=str;_root=_BinaryTree(tmp);}~BinaryTree(){_Clear(_root);}BinaryTree<T>(BinaryTree&t){_root=_Copy(t._root);}BinaryTree<T>&operator=(BinaryTreet){if(*this!=t){swap(_root,t._root);}}voidFastorder(){_Fastorder(_root);}voidInorder(){_Inorder(_root);}voidPostorder(){_Postorder(_root);}voidLevelorder(){queue<rootnode<T>*>q;if(_root==NULL){return;}q.push(_root);while(!q.empty()){rootnode<T>*root=q.front();cout<<root->_value;q.pop();if(root->_leftnode!=NULL){q.push(root->_leftnode);}if(root->_rightnode!=NULL){q.push(root->_rightnode);}}}intleafnum(){intnum=0;num=_Leafnum(_root,num);returnnum;}intSize(){intsize=0;_Size(_root,size);returnsize;}intDepth(){intDepth=_Depth(_root);returnDepth;}voidNRfastorder(){stack<rootnode<T>*>s;if(_root!=NULL){s.push(_root);}while(!s.empty()){rootnode<T>*front=s.top();cout<<front->_value;s.pop();if(front->_rightnode!=NULL){s.push(front->_rightnode);}if(front->_leftnode!=NULL){s.push(front->_leftnode);}}}voidNRinorder(){stack<rootnode<T>*>s;rootnode<T>*cur=_root;rootnode<T>*top=NULL;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_leftnode;}if(top!=s.top()->_rightnode){top=s.top();cout<<top->_value;s.pop();cur=top->_rightnode;}else{top=s.top();cout<<top->_value;s.pop();}}}voidNRpostorder(){rootnode<T>*cur=_root;stack<rootnode<T>*>s;rootnode<T>*top=NULL;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_leftnode;}if(s.top()->_rightnode!=NULL&&top!=s.top()->_rightnode){top=s.top();cur=top->_rightnode;}else{top=s.top();s.pop();cout<<top->_value;}}}protected:rootnode<T>*_BinaryTree(T*&str){rootnode<T>*root=NULL;if(*str!='#'&&*str!='\0'){root=newrootnode<T>(*str);str++;root->_leftnode=_BinaryTree(str);str++;root->_rightnode=_BinaryTree(str);}returnroot;}void_Fastorder(rootnode<T>*&root){if(root==NULL){return;}else{cout<<root->_value;_Fastorder(root->_leftnode);_Fastorder(root->_rightnode);}}void_Inorder(rootnode<T>*root){if(root==NULL){return;}_Inorder(root->_leftnode);cout<<root->_value;_Inorder(root->_rightnode);}void_Postorder(rootnode<T>*root){if(root==NULL){return;}_Postorder(root->_leftnode);_Postorder(root->_rightnode);cout<<root->_value;}void_Clear(rootnode<T>*root){if(root==NULL){return;}rootnode<T>*tmp=root->_leftnode;rootnode<T>*tmp2=root->_rightnode;deleteroot;_Clear(tmp);_Clear(tmp2);}rootnode<T>*_Copy(rootnode<T>*root){rootnode<T>*newroot=NULL;if(root==NULL){returnnewroot;}newroot=newrootnode<T>(root->_value);newroot->_leftnode=_Copy(root->_leftnode);newroot->_rightnode=_Copy(root->_rightnode);returnnewroot;}int_Size(rootnode<T>*root,int&size){if(root==NULL){return0;}size++;_Size(root->_leftnode,size);_Size(root->_rightnode,size);returnsize;}int_Depth(rootnode<T>*root){if(root==NULL){return0;}inthight=1;intleft=0;intright=0;left+=_Depth(root->_leftnode)+hight;right+=_Depth(root->_rightnode)+hight;if(left>right){returnleft;}else{returnright;}}int_Leafnum(rootnode<T>*root,int&num){if(root==NULL){return0;}if(root->_leftnode==NULL&&root->_rightnode==NULL){num++;}_Leafnum(root->_leftnode,num);_Leafnum(root->_rightnode,num);returnnum;}private:rootnode<T>*_root;};voidTest1(){char*str="123##45##6##78###";BinaryTree<char>b1(str);BinaryTree<char>b2(b1);BinaryTree<char>b3=b2;b1.Fastorder();cout<<endl;b1.Inorder();cout<<endl;b1.Postorder();cout<<endl;b2.Fastorder();cout<<endl;b3.Fastorder();cout<<endl;cout<<b3.Size()<<endl;cout<<b3.Depth()<<endl;b3.Levelorder();cout<<endl;cout<<b3.leafnum()<<endl;}intmain(){Test1();}