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

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

二叉树的结构以及接口如下
template
class BinaryTree
{
                 typedef BinaryNode  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  *root);
                 size_t _depth(BinaryNode  *root);
                 void _size(BinaryNode  *root, int *p);
                 void _leafsize(BinaryNode  *root, size_t *p);
                 int Leafsize(BinaryNode  *root);
                 void PrevOder_Nor();
                 void InOder_Nor();
                 void PostOder_Nor();
                 void Distory(Node *_root)
                 Node* _Copy(Node *cur);
private:
                 BinaryNode *_root;
};


二叉树的建立（构造函数）
                BinaryTree( const T * a, size_t size, const T & valiue)
                {
                                 size_t index = 0;
                                _root = _CreatTree( a, size , index, valiue);
                }
                 BinaryNode* _CreatTree(const T* a, size_t size, size_t &index, const T &valiue)
                {
                                 BinaryNode *root = NULL;
                                 if (index < size&& a[index ] != valiue)
                                {
                                                root = new BinaryNode (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* 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 ::Leafsize( BinaryNode *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 ::_leafsize( BinaryNode *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  * root)
                {
                                 if (root == NULL)
                                                 return;
                                cout << root->_data << " " ;
                                _PrevOder( root->_left);
                                _PrevOder( root->_right);
                }
二叉树前序遍历非递归
void BinaryTree ::PrevOder_Nor()
{
                 BinaryNode *cur = _root;
                 stack*> s;
                 if (cur == NULL )
                                 return;
                s.push(cur);
                 while (!s.empty())
                {
                                 BinaryNode *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 ::_LevalOder( BinaryNode *root)
{
                 deque*> q;
                q.push_back( root);
                 while (q.size())
                {
                                 BinaryNode *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  * root)
                {
                                 if (root == NULL)
                                                 return;
                                _InOder( root->_left);
                                cout << root->_data << " " ;
                                _InOder( root->_right);
                }
二叉树中序遍历非递归
void BinaryTree ::InOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack 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  * root)
                {
                                 if (root == NULL)
                                                 return;
                                _PostOder( root->_left);
                                _PostOder( root->_right);
                                cout << root->_data << " " ;
                }
二叉树后序遍历非递归
void BinaryTree ::PostOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack 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 ::_depth( BinaryNode *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 ::_size( BinaryNode *root,int *p)
{
                 if (root )
                {
                                ++(* p);
                                _size( root->_left, p );
                                _size( root->_right, p );
                }
                 return ;
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

创新互联建站成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟，建立了一套“以技术为基点，以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目，如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、成都App定制开发、成都做手机网站、微信网站制作、软件开发、BGP机房服务器托管等实行标准化操作，让客户可以直观的预知到从创新互联建站可以获得的服务效果。
文章题目：数据结构之二叉树（构造拷贝构造以及前序中序后续三种遍历方法）-创新互联
网站URL：http://kswjz.com/article/dpgsse.html