数据结构之二叉树 （构造 拷贝构造 以及前序中序后续三种遍历方法）

首先二叉树的节点定义如下：
struct BinaryNode
{

                 BinaryNode *_left;
                 BinaryNode *_right;
                 T _data;
                BinaryNode( T data ) :_data(data), _left( NULL), _right(NULL )
                {};
};

二叉树的结构以及接口如下
template<class T>
class BinaryTree
{
                 typedef BinaryNode <T> Node;
public:
                BinaryTree() :_head( NULL)
                {};
                BinaryTree( const T * a, size_t size, const T & valiue)
                ~BinaryTree()
                BinaryTree( BinaryTree &b )
                void PrevOder()
                 void InOder()
                 void PostOder()
private:
public:
                 void LevalOder()
                 size_t depth()
                 size_t size()
                 size_t learsize()
                 void _LevalOder(BinaryNode <T> *root);
                 size_t _depth(BinaryNode <T> *root);
                 void _size(BinaryNode <T> *root, int *p);
                 void _leafsize(BinaryNode <T> *root, size_t *p);
                 int Leafsize(BinaryNode <T> *root);
                 void PrevOder_Nor();
                 void InOder_Nor();
                 void PostOder_Nor();
                 void Distory(Node *_root)
                 Node* _Copy(Node *cur);
private:
                 BinaryNode<T > *_root;
};


二叉树的建立（构造函数）
                BinaryTree( const T * a, size_t size, const T & valiue)
                {
                                 size_t index = 0;
                                _root = _CreatTree( a, size , index, valiue);
                }
                 BinaryNode<T >* _CreatTree(const T* a, size_t size, size_t &index, const T &valiue)
                {
                                 BinaryNode<T > *root = NULL;
                                 if (index < size&& a[index ] != valiue)
                                {
                                                root = new BinaryNode <T>(a[index]);
                                                root->_left = _CreatTree(a, size , ++index, valiue);
                                                root->_right = _CreatTree(a, size , ++index, valiue);
                                }
                                 return root;
                }
二叉树的销毁（析构函数）
                ~BinaryTree()
                {
                                Distory(_root);
                                cout << " ~BinaryTree()" << endl;
                }
                 void Distory(Node *_root)
                {
                                 if (_root == NULL)
                                                 return;
                                Distory( _root->_left);
                                Distory( _root->_right);
                                 if (_root )
                                                 delete _root ;
                                 _root == NULL ;

                }
二叉树的拷贝(拷贝构造)
                BinaryTree( BinaryTree &b )
                {
                                _root = _Copy( b._root);
                }
BinaryNode<T >* BinaryTree< T>::_Copy(Node *cur)
{
                 if (cur == NULL)
                                 return NULL ;
                 Node *tmp = new Node(cur->_data);
                tmp->_left=_Copy( cur->_left);
                tmp->_right=_Copy( cur->_right);
                 return tmp;

}
求叶子节点个数（两种方法）
一：
int BinaryTree <T>::Leafsize( BinaryNode<T > *root)
{
                 int count;
                 if (root == NULL)
                                count = 0;
                 else if (root->_left == NULL&&root ->_right == NULL)
                {
                                count = 1;
                }
                 else  count = Leafsize(root ->_left) + Leafsize(root->_right);
                 return count;
}
二：
void BinaryTree <T>::_leafsize( BinaryNode<T > *root, size_t * p)
{
                 if (root != NULL)
                {
                                _leafsize( root->_left,p );
                                _leafsize( root->_right,p );
                                 if (root ->_left == NULL&& root->_right == NULL )
                                {
                                                ++ *p;
                                }

                }
}

二叉树前序遍历递归
                 void _PrevOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                cout << root->_data << " " ;
                                _PrevOder( root->_left);
                                _PrevOder( root->_right);
                }
二叉树前序遍历非递归
void BinaryTree <T>::PrevOder_Nor()
{
                 BinaryNode<T > *cur = _root;
                 stack<BinaryNode <T>*> s;
                 if (cur == NULL )
                                 return;
                s.push(cur);
                 while (!s.empty())
                {
                                 BinaryNode<T > *tmp = s.top();
                                cout << tmp->_data << " ";
                                s.pop();
                                 if (tmp->_right)
                                {
                                                s.push(tmp->_right);
                                }
                                 if (tmp->_left)
                                {
                                                s.push(tmp->_left);
                                }
                }
                cout << endl;
                
}
二叉树层序遍历（队列实现）
void BinaryTree <T>::_LevalOder( BinaryNode<T > *root)
{
                 deque<BinaryNode <T>*> q;
                q.push_back( root);
                 while (q.size())
                {
                                 BinaryNode<T > *pNode = q.front();
                                q.pop_front();
                                cout << pNode->_data << " ";
                                 if (pNode->_left)
                                {
                                                q.push_back(pNode->_left);
                                }
                                 if (pNode->_right)
                                {
                                                q.push_back(pNode->_right);
                                }
                }
                

}
二叉树中序遍历递归
                 void _InOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                _InOder( root->_left);
                                cout << root->_data << " " ;
                                _InOder( root->_right);
                }
二叉树中序遍历非递归
void BinaryTree <T>::InOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack<Node *> s;
                 while (cur||!s.empty())
                {
                                 while (cur)
                                {
                                                s.push(cur);
                                                cur = cur->_left;
                                }
                                 Node *tmp = s.top();
                                cout << tmp->_data << " ";
                                s.pop();
                                cur = tmp->_right;
                }
                cout << endl;

}
二叉树后序遍历递归
                 void  _PostOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                _PostOder( root->_left);
                                _PostOder( root->_right);
                                cout << root->_data << " " ;
                }
二叉树后序遍历非递归
void BinaryTree <T>::PostOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack<Node *> s;
                 Node *prev = NULL ;
                 while (cur||!s.empty())
                {
                                 while (cur)
                                {
                                                s.push(cur);
                                                cur = cur->_left;
                                }
                                 Node *tmp = s.top();
                                 if (tmp->_right == NULL || tmp->_right == prev)
                                {
                                                cout << tmp->_data << " " ;
                                                s.pop();
                                                prev = tmp;
                                }
                                 else
                                {
                                                cur = tmp->_right;
                                }
                }
                cout << endl;
                
}
二叉树的深度
size_t BinaryTree <T>::_depth( BinaryNode<T > *root)
{
                 int hleft;
                 int hright;
                 int max;
                 if (root )
                {
                                hleft = _depth( root->_left);
                                hright = _depth( root->_right);
                                max = hleft > hright ? hleft : hright;
                                 return max + 1;

                }
                 else
                {
                                 return 0;
                }
}
二叉树的大小
                 size_t size()
                {
                                 int count = 0;
                                _size(_root,&count);
                                 return count;
                }
void BinaryTree <T>::_size( BinaryNode<T > *root,int *p)
{
                 if (root )
                {
                                ++(* p);
                                _size( root->_left, p );
                                _size( root->_right, p );
                }
                 return ;
}