#pragma once #include
     
      #include
      
       #include
       
        using namespace std;template 
        
           //树的结构体struct BinaryTreeNode{public:	T _data;	BinaryTreeNode
         
          * _leftChild;	BinaryTreeNode
          
           * _rightChild;public: BinaryTreeNode(const T& data) :_data(data) , _leftChild(NULL) , _rightChild(NULL) {} ~BinaryTreeNode() {}};template 
           
            class BinaryTree //树的封装{public: BinaryTreeNode
            
             * _root;public: BinaryTree() :_root(NULL) {} BinaryTree( T*a, size_t size) { size_t index = 0; _root = _CreateBiTree(a, index, size); } BinaryTree(const BinaryTree& tmp) :_root(NULL) { _root=_Copy(tmp._root); } ~BinaryTree() { Destory(); } BinaryTree
             
              & operator=( BinaryTree
              
                tmp) { swap(_root, tmp._root); return *this; } void InOrder()//中序遍历递归方法 { _InOrder(_root); cout << endl; } void PreOrder()//前序遍历递归方法 { _PreOrder(_root); cout << endl; } void PosOrder()//后序遍历递归方法 { _PosOrder(_root); cout << endl; } void LevelOrder()//层序遍历 { queue
               
                
                 *> s ; s.push(_root); while (!s.empty()) { BinaryTreeNode
                 
                  * cur = s.front(); cout<
                  
                   _data<<' '; if (cur->_leftChild) s.push(cur->_leftChild); if (cur->_rightChild) s.push(cur->_rightChild); s.pop(); } cout << endl; } void Size()//节点数 { int size = 0; cout<<_Size(_root,size)<
                   
                    *> s ;  s.push(_root); while (!s.empty()) { BinaryTreeNode
                    
                     * cur; cur=s.top(); s.pop(); cout << cur->_data << ' '; if (cur->_rightChild) s.push(cur->_rightChild); if (cur->_leftChild) s.push(cur->_leftChild); } cout << endl; } void InOrderNonR() //中序 非递归 { if (_root == NULL) return; stack
                     
                      
                       *> s; s.push(_root); BinaryTreeNode
                       
                        * prev=NULL; BinaryTreeNode
                        
                         * cur=NULL; while (!s.empty()) { cur = s.top(); if(prev != cur&&cur->_leftChild) //左不空 压左 { s.push(cur->_leftChild); } else //左空   出栈 输出 { cout << cur->_data << ' '; s.pop(); if (!s.empty())     prev = s.top();//prev始终为出栈后的栈顶 if (cur->_rightChild)//  cur右不空  压右 { s.push(cur->_rightChild); } } } cout << endl; } void PosOrderNonR()  //后续  非递归 { if (_root == NULL) return; stack
                         
                          
                           *> s; BinaryTreeNode
                           
                            * cur = NULL; BinaryTreeNode
                            
                             * prev = NULL; BinaryTreeNode
                             
                              * tmp = NULL; s.push(_root);                  while (!s.empty()) { cur = s.top(); if (prev != cur&&cur->_leftChild != NULL)//1.左不空且prev！=cur 压左  s.push(cur->_leftChild); else//左空 { if (cur->_rightChild!=tmp  &&cur->_rightChild)//右不空 且 cur->right！=tmp 压右 { s.push(cur->_rightChild); } else             //右空  输出 cur { cout << cur->_data << ' '; tmp = s.top();    //tmp(判断是否压右)始终为出栈前的栈顶 s.pop(); if (!s.empty()) { prev = s.top();//prev（判断是否压右）始终为出栈后栈顶 } } } } cout << endl; }protected://以下为递归的调用函数 BinaryTreeNode
                              
                               * _CreateBiTree(const T* tmp, size_t& index, size_t size) { BinaryTreeNode
                               
                                * root = NULL; if (index < size&&tmp[index]!='#') { root = new BinaryTreeNode
                                
                                 (tmp[index]); root->_leftChild = _CreateBiTree(tmp, ++index, size); root->_rightChild = _CreateBiTree(tmp, ++index, size); }     return root; } void _InOrder(BinaryTreeNode
                                 
                                  * &T) { if (T == NULL) return; _InOrder(T->_leftChild); cout << T->_data << ' '; _InOrder(T->_rightChild); } void _PreOrder(BinaryTreeNode
                                  
                                   * &T) { if (T == NULL) return; cout << T->_data<<' '; _PreOrder(T->_leftChild); _PreOrder(T->_rightChild); } void _PosOrder(BinaryTreeNode
                                   
                                    * &T) { if (T == NULL) return; _PosOrder(T->_leftChild); _PosOrder(T->_rightChild); cout << T->_data << ' '; } int _Size(BinaryTreeNode
                                    
                                     * root,int & size) { if (root == NULL) return 0; size++; _Size(root->_leftChild, size); _Size(root->_rightChild, size); return size; } int _Hight(BinaryTreeNode
                                     
                                      * root) { int hight = 1; if (root == NULL) return 0; hight += _Hight(root->_leftChild); int ritHight = 0; ritHight+= _Hight(root->_rightChild); if (hight < ritHight) hight = ritHight; return hight; } void _Destory(BinaryTreeNode
                                      
                                       * root) { if (root == NULL) return; BinaryTreeNode
                                       
                                        * del = root; _Destory(del->_leftChild); _Destory(del->_rightChild); delete root; return; } void _LeafNum(BinaryTreeNode
                                        
                                         * root,int& num) { if (root == NULL) return ; if (root->_leftChild == NULL&&root->_rightChild == NULL) ++num; _LeafNum(root->_leftChild,num); _LeafNum(root->_rightChild,num); return ; } BinaryTreeNode
                                         
                                          * _Copy(BinaryTreeNode
                                          
                                           * root) { if (root == NULL) return NULL; BinaryTreeNode
                                           
                                            * newRoot = NULL; newRoot = new BinaryTreeNode
                                            
                                             (root->_data); newRoot->_leftChild = _Copy(root->_leftChild); newRoot->_rightChild = _Copy(root->_rightChild); return newRoot; }};//测试用例#include"binarytree.hpp"using namespace std;void test(){ int l[10] = { 1, 2, 3,'#', '#', 4, '#', '#', 5, 6 }; int s[18] = { 1, 2, 3, 4, '#', '#', 5, '#', '#', 6,'#','#' ,7, 8, '#', '#', 9, 10 }; BinaryTree
                                             
                                               t1; BinaryTree
                                              
                                                t2(s, 18); BinaryTree
                                               
                                                 t3(t2); t1 = t2; t2.PreOrder(); t2.InOrder(); t2.PosOrder(); t2.LevelOrder(); t2.Size(); t2.Hight(); t2.Destory(); t3.InOrder(); t1.InOrder(); t3.LeafNum(); t3.PreOrderNonR(); t3.InOrderNonR(); t3.PosOrderNonR();}int main(){ test(); return 0;}