二叉树：二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

二叉树节点结构：

struct BinaryTreeNode{	T _data;			//数据	BinaryTreeNode
     
      * _left;	//指向左子树	BinaryTreeNode
      
       * _right;	//指向右子树		BinaryTreeNode(const T& d)		:_data(d)		,_left(NULL)		,_right(NULL)	{}};
      
     

二叉树的创建：

Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid){	Node* root = NULL;	if(index
     
      _left = _CreateTree(a, size, ++index, invilid);	//递归实现左子树		root->_right = _CreateTree(a, size, ++index, invilid);	//递归实现右子树	}	return root;	//返回根节点}
     

前序遍历：

/* 前序遍历：根->左子树->右子树 */void _PrevOrder(Node* root){	if(root == NULL)	{		return;	}	cout<
     
      _data<<" ";		//打印根节点数据	_PrevOrder(root->_left);	//递归遍历左子树	_PrevOrder(root->_right);	//递归遍历右子树}
     

中序遍历：

/* 中序遍历：左子树->根->右子树 */void _InOrder(Node* root){	if(root == NULL)	{		return;	}	_InOrder(root->_left);		//递归遍历左子树	cout<
     
      _data<<" ";		//打印根节点数据	_InOrder(root->_right);		//递归遍历右子树}
     

后序遍历：

/* 后序遍历：左子树->右子树->根 */void _PostOrder(Node* root){	if(root == NULL)	{		return;	}	_PostOrder(root->_left);	//递归遍历左子树	_PostOrder(root->_right);	//递归遍历右子树	cout<
     
      _data<<" ";		//打印根节点数据}
     

层次遍历：

/* 层次遍历：第一层->最后一层 */void _LevelOrder(Node* root){	queue
     
       qt;		if(root == NULL)	{	        return;	}		qt.push(root);        //将根节点压到队列中		while(!qt.empty())	{	        /* 当根节点的左孩子不为空，就说明这一层还没有完全压入队列中 */	        if(qt.front()->_left != NULL)		{			qt.push(qt.front()->_left);    //将根节点左子树压到队列中		}		/* 当根节点的右孩子不为空，就说明这一层还没有完全压入队列中 */		if(qt.front()->_right != NULL)		{			qt.push(qt.front()->_right);   //将根节点右子树压到队列中		}				cout<
      
       _data<<" ";    //依次打印节点				qt.pop();       //将打印的节点出队列	}}
      
     

二叉树节点的个数 = 就是左子树节点个数加上右子树节点的个数再加上根节点

size_t _Size(Node* root){	if(root == NULL)	{		return 0;	}	return _Size(root->_left)+_Size(root->_right)+1;//左子树节点+右子树节点+根节点}

二叉树的深度 = 左子树 >= 右子树 ? 左子树+1， 右子树+1；

size_t _Depth(Node* root){	if(root == NULL)	{		return 0;	}	size_t LeftDepth = _Depth(root->_left);	size_t RightDepth = _Depth(root->_right);	if(LeftDepth >= RightDepth)	{		return LeftDepth+1;	}	else	{		return RightDepth+1;	}}

二叉树叶子节点的个数 = 左子树的叶子节点 个数+ 右子树的叶子节点个数

size_t _LeafSize(Node* root){	if(root == NULL)	{		return 0;	}	if(root->_left == NULL && root->_right == NULL)    //只有根节点	{		return 1;	}	return _LeafSize(root->_left)+_LeafSize(root->_right);}

整体代码：

#include 
     
      #include 
      
       using namespace std;template 
       
        struct BinaryTreeNode{	T _data;			//数据域	BinaryTreeNode
        
         * _left;	//指向左子树	BinaryTreeNode
         
          * _right;	//指向右子树		BinaryTreeNode(const T& d)		:_data(d)		,_left(NULL)		,_right(NULL)	{}};template
          
           class BinaryTree{ typedef BinaryTreeNode
           
             Node; //类型重命名，方便后面使用public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a, size_t size, const T& invilid) :_root(NULL) { size_t index = 0; _root = _CreateTree(a, size, index, invilid); } BinaryTree
            
             (const BinaryTree& tree) { _root = _Copy(tree._root); } BinaryTree& operator= (BinaryTree tree)    //现代式写法 { swap(_root, tree._root); return *this; } ~BinaryTree() { if(_root != NULL) { _Destroy(_root); } }public: void PrevOrder() { _PrevOrder(_root); cout<
             
              _left)+_Size(root->_right)+1; } size_t _Depth(Node* root) { if(root == NULL) { return 0; } size_t LeftDepth = _Depth(root->_left); size_t RightDepth = _Depth(root->_right); if(LeftDepth >= RightDepth) { return LeftDepth+1; } else { return RightDepth+1; } } size_t _LeafSize(Node* root) { if(root == NULL) { return 0; } if(root->_left == NULL && root->_right == NULL) { return 1; } return _LeafSize(root->_left)+_LeafSize(root->_right); }protected: /* 前序遍历：根->左子树->右子树 */ void _PrevOrder(Node* root) { if(root == NULL) { return; } cout<
              
               _data<<" "; //打印根节点数据 _PrevOrder(root->_left); //递归遍历左子树 _PrevOrder(root->_right); //递归遍历右子树 } /* 中序遍历：左子树->根->右子树 */ void _InOrder(Node* root) { if(root == NULL) { return; } _InOrder(root->_left); //递归遍历左子树 cout<
               
                _data<<" "; //打印根节点数据 _InOrder(root->_right); //递归遍历右子树 } /* 后序遍历：左子树->右子树->根 */ void _PostOrder(Node* root) { if(root == NULL) { return; } _PostOrder(root->_left); //递归遍历左子树 _PostOrder(root->_right); //递归遍历右子树 cout<
                
                 _data<<" "; //打印根节点数据 } /* 层次遍历：第一层->最后一层 */ void _LevelOrder(Node* root) { queue
                 
                   qt; if(root == NULL) { return; } qt.push(root); while(!qt.empty()) { if(qt.front()->_left != NULL) { qt.push(qt.front()->_left); } if(qt.front()->_right != NULL) { qt.push(qt.front()->_right); } cout<
                  
                   _data<<" "; qt.pop(); } }protected: Node* _Copy(Node* root) { if(root == NULL) { return NULL; } Node* NewRoot = new Node(root->_data); //创建新的根节点 Node* NewCur = NewRoot; NewCur->_left = _Copy(root->_left); NewCur->_right = _Copy(root->_right); return NewRoot; } void _Destroy(Node* root) { if(root == NULL) { return; } if(root->_left == NULL && root->_right == NULL) { delete root; root = NULL; return; } _Destroy(root->_left); _Destroy(root->_right); } Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid) { Node* root = NULL; if(index
                   
                    _left = _CreateTree(a, size, ++index, invilid);//递归实现左子树     root->_right = _CreateTree(a, size, ++index, invilid);//递归实现右子树 } return root; //返回根节点 }protected: Node* _root;    //根节点};int main(){ Test(); system("pause"); return 0;}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

测试结构：

测试代码：

void Test(){	int array[10] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};	BinaryTree
     
       tree(array, 10, '#');	tree.PrevOrder();	tree.InOrder();	tree.PostOrder();	tree.LevelOrder();		BinaryTree
      
        tree2(tree);	tree2.PrevOrder();	BinaryTree
       
         tree3 = tree2;	tree3.PrevOrder();}
       
      
     

测试结果：