二叉樹的遞歸實(shí)現(xiàn)

  二叉樹是一種非常有用的結(jié)構(gòu)，二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

  二叉樹的每個結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。

  一棵深度為k，且有2^k-1個節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號為1至n的節(jié)點(diǎn)對應(yīng)時，稱之為完全二叉樹。詳細(xì)定義見百度百科

 二叉樹的結(jié)構(gòu)使其在排序算法中非常有用，最有用的當(dāng)屬平衡二叉樹，平衡二叉樹將會在本人的博客中討論。

 說起二叉樹，就不得不討論一下二叉樹的遍歷，一般來說，二叉樹的遍歷方式有4種：

 假設(shè)我們的樹是這樣的：

（一）前序遍歷

    首先我們得分析先序遍歷的順序：A,B,D,E,C,F,G。

    樹的遍歷利用遞歸來實(shí)現(xiàn)會簡單一點(diǎn)，我們將遍歷一整棵樹分解成遍歷左子樹和右子樹的子問題。

	void PrevOrder()//前序遍歷
	{
		_PrevOrder(_root);
	}
	void _PrevOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return;
		}
		cout << root->_data <<" ";//先輸出根節(jié)點(diǎn)
		_PrevOrder(root->_left);//在輸出左子樹
		_PrevOrder(root->_right);//最后右子樹
	}

（二）中序遍歷

   遍歷的順序：D,B,E,A,F,C,G

	void MidOrder()//中序遍歷
	{
		_MidOrder(_root);
	}
	void _MidOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return;
		}
		_MidOrder(root->_left);
		cout << root->_data << " ";
		_MidOrder(root->_right);
	}

（三）后序遍歷

   遍歷順序：D,E,B,F,G,C,A

	void RearOrder()//后序遍歷
	{
		_RearOrder(_root);
	}
	void _RearOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return;
		}
		_RearOrder(root->_left);
		_RearOrder(root->_right);
		cout << root->_data << " ";
	}

（四）層序遍歷

   遍歷順序：A,B,C,D,E,F,G

   層序遍歷的話可以利用隊(duì)列先進(jìn)先出的特點(diǎn)，將每一層的節(jié)點(diǎn)入隊(duì)列，只要隊(duì)列不為空，就出一次隊(duì)列。

void SequenceOrder()//層序遍歷
	{
		queue<BinaryTreeNode<T>*> q;
		if (_root)
			q.push(_root);
		while (!q.empty())
		{
			if (q.front()->_left)
			{
				q.push(q.front()->_left);
			}
			if (q.front()->_right)
			{
				q.push(q.front()->_right);
			}
			cout << q.front()->_data<< " ";
			q.pop();
		}
	}

樹的遍歷是比較簡單的，下面我們看一下有點(diǎn)難度的：

（一）求樹的葉子節(jié)點(diǎn)的個數(shù)：

  數(shù)的葉子節(jié)點(diǎn)總是在最深的一層。，每次當(dāng)一個子問題的根節(jié)點(diǎn)的左右子樹都為NULL時，我們就將戒子節(jié)點(diǎn)的個數(shù)加一，當(dāng)然，可以把葉子節(jié)點(diǎn)定義為一個靜態(tài)變量，這樣，每次加的都是同一個變量上。

也可以不用定義靜態(tài)的變量，因?yàn)殪o態(tài)變量會有線程的安全問題。

        size_t LeafCount()
	{
		return _LeafCount(_root);
	}
	size_t _LeafCount(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		if (root->_left==NULL && root->_right ==NULL)
		{
			return 1;
		}

		return (_LeafCount(root->_left)+_LeafCount(root->_right));
	}
	

（二）求樹的深度

  求樹的深度是一個比較有難度的問題，因?yàn)槲覀円容^不同子樹的深度的大小，然后取最大的哪一個，但是在一個遞歸程序中很難保證一個變量不會改變。在這里我們只要比較每個子問題中的左右字?jǐn)?shù)的深度，每次返回使深度最大值加一，最后的值就是樹的深度。

	size_t Deepth()
	{
		return _Deepth(_root);
	}
	size_t _Deepth(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		size_t leftDeep = _Deepth(root->_left)+1;
		size_t rightDeep = _Deepth(root->_right)+1;
		return leftDeep > rightDeep ? leftDeep: rightDeep;
	}

（三）求樹的節(jié)點(diǎn)的個數(shù)

   這個問題是比較容易的，我們可以用任意一種遍歷方式遍歷這棵樹，每遍歷到一個節(jié)點(diǎn)，個數(shù)就加以。

	size_t Size()
	{
		return _Size(_root);
	}
	size_t _Size(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;
	}