二叉樹的簡單遞歸實現（創建，遍歷，高度，大小）

二叉樹

二叉樹:二叉樹是一棵特殊的樹，二叉樹每個節點最多有兩個孩子結點，分別稱為左孩子和右孩子

滿二叉樹:高度為N的滿二叉樹有2^N - 1個節點的二叉樹。

完全二叉樹: 若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹

二叉樹的存儲結構

數組表示存儲

鏈表存儲表示：

    數組表示法用于完全二叉樹的存儲非常有效，但表示一般的二叉樹則不是很理想。此外，在一棵樹中進行插入和刪除時，為了反映節點的層次變化，可能需要移動許多節點，降低了算法效率，二使用連接表示，可以克服這些缺點。

    根據二叉樹的定義，可以設計出二叉樹的節點結構。二叉樹的每一個節點有三個域：數據域_data，左子女節點指針_leftChild，右子女節點指針_rightChild。這中鏈表稱為二叉鏈表。使用這種結構，可以很方便的根據左右孩子指針找到他的左右孩子。但要找到他的雙親很難。為了找到雙親節點，可以在節點中在增加一個雙親指針域_parent，他被稱為三叉鏈表結構。

樓主主要實現的是二叉鏈表結構

節點的定義

//節點結構
template<class T>
struct BinaryTreeNode
{
	//構造函數 
	BinaryTreeNode(const T& data)
		:_data(data)
		,_leftChild(NULL)
		,_rightChild(NULL)
	{}
public:
	T _data;//數據域
	BinaryTreeNode* _leftChild;//左孩子指針
	BinaryTreeNode* _rightChild;//右孩子指針
};

二叉樹的實現

//二叉樹類
template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;
public:
	BinaryTree()
		:_root(NULL)
	{}
	//構造函數
	BinaryTree(const T* a, size_t size, const T& invalid)
	{
		assert(a);
		size_t index = 0;
		_root = _CreateTree(a, size, invalid,index);
	}
	//拷貝構造
	BinaryTree(const BinaryTree<T>& t)
	{
		_root = _Copy(t._root);
	}
	//賦值運算符的重載
	BinaryTree<T>& operator=(BinaryTree<T> t)
	{
		swap(_root, t._root);
		return *this;
	}
	//析構函數
	~BinaryTree()
	{
		_Destory(_root);
	}

public:
	//前序遍歷
	void PrevOrder()
	{
		_PrevOrder(_root);
		cout << endl;
	}
	//中序遍歷
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	//后序遍歷
	void PostOrder()
	{
		_PostOrder(_root);
		cout << endl;
	}
	//層次遍歷
	void LevelOrder()
	{
		_LevelOrder(_root);
		cout << endl;
	}
	//求二叉樹的節點個數
	size_t Size()
	{
		return _Size(_root);
	}
	//求二叉樹的深度
	size_t Depth()
	{
		return _Depth(_root);
	}
	//求二叉樹的葉子節點的個數
	size_t LeafSize()
	{
		return _LeafSize(_root);
	}
protected:
	Node* _CreateTree(const T* a, size_t size, const T& invalid,  size_t&  index)
		//index要傳引用，需要更改index的值
	{
		Node* root = NULL;
		//判斷數組是否越界和輸入的值是否合法
		if (index < size&&a[index] != invalid)
		{
			root = new Node(a[index]);//創建根節點
			root->_leftChild = _CreateTree(a, size, invalid, ++index);//遞歸創建左子樹
			root->_rightChild = _CreateTree(a, size, invalid, ++index);//遞歸創建右子樹
		}
		return root;//返回根節點
	}

	void _PrevOrder(Node* root)
	{
		//如果節點為空則直接返回
		if (root == NULL)
		{
			return;
		}

		cout << root->_data << " ";//訪問根節點
		_PrevOrder(root->_leftChild);//遞歸訪問左子樹
		_PrevOrder(root->_rightChild);//遞歸訪問右子樹
	}

	void _InOrder(Node* root)
	{
		//如果節點為空則直接返回
		if (root == NULL)
		{
			return;
		}

		_InOrder(root->_leftChild);//訪問左子樹
		cout << root->_data << " ";//遞歸訪問根節點
		_InOrder(root->_rightChild);//遞歸訪問右子樹
	}

	void _PostOrder(Node* root)
	{
		//如果節點為空則直接返回
		if (root == NULL)
		{
			return;
		}

		_PostOrder(root->_leftChild);//訪問左子樹
		_PostOrder(root->_rightChild);//遞歸訪問右子樹
		cout << root->_data << " ";//遞歸訪問根節點
	}

	//層次遍歷
	void _LevelOrder(Node* root)
	{
		if (root == NULL)
		{

			return;
		}
		queue<Node*> q;
		q.push(root);//根節點入隊
		while (!q.empty())//當隊列不為空
		{
			if (q.front()->_leftChild)
			{
				q.push(q.front()->_leftChild);
			}
			if (q.front()->_rightChild)
			{
				q.push(q.front()->_rightChild);
			}
			cout << q.front()->_data << " ";
			q.pop();
		}
	}

	size_t _Size(Node* root)
	{
		size_t count = 0;
		if (root == NULL)
		{
			return count;//樹為空
		}

		count++;//根節點
		count += _Size(root->_leftChild);//計算左子樹大小
		count+= _Size(root->_rightChild);//計算右子樹大小
		return count;
	}


	//返回左右子樹深度較大的
	size_t _Depth(Node* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		size_t LeftDepth = _Depth(root->_leftChild);
		size_t RightDepth= _Depth(root->_rightChild);
		if (LeftDepth > RightDepth)
		{
			return ++LeftDepth;
		}
		else
		{
			return ++RightDepth;
		}
	}

	size_t _LeafSize(Node*root)
	{
		if (root == NULL)
		{
			return 0;
		}
		if (root->_leftChild == NULL && root->_rightChild == NULL)
		{
			return 1;
		}

		return _LeafSize(root->_leftChild)+ _LeafSize(root->_rightChild);
	}

	Node* _Copy(Node* root)
	{
		
		if (root == NULL)
		{

			return NULL;
		}

		Node* newRoot = new Node(root->_data);
		newRoot->_leftChild = _Copy(root->_leftChild);
		newRoot->_rightChild = _Copy(root->_rightChild);
		return newRoot;
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		//刪除葉結點
		if (root->_leftChild == NULL&&root->_rightChild == NULL)
		{
			delete root;
			root = NULL;
			return;
		}

		_Destory(root->_leftChild);//遞歸刪除左子樹
		_Destory(root->_rightChild);//遞歸刪除右子樹
		delete root;
	}
private:
	BinaryTreeNode<T>* _root;//根節點
};

測試代碼

#include"BinaryTree.h"

void TestBinary()
{
	/*int a1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };
	BinaryTree<int> t1(a1, 10, '#');
	cout << "先序遍歷：";
	t1.PrevOrder();
	cout << "中序遍歷：";
	t1.InOrder();
	cout << "后序遍歷：";
	t1.PostOrder();
	cout << "層次遍歷：";
	t1.LevelOrder();
	cout << "size:" << t1.Size() << endl;
	cout << "depth:" << t1.Depth() << endl;
	cout << "leafSize:" << t1.LeafSize() << endl;*/

	int a2[15] = { 1,2,'#',3,'#','#',4,5,'#',6 ,'#' ,7,'#' ,'#' ,8 };
	int a[] = { 1,2,'#','#',3 };
	BinaryTree<int> t1(a, 5, '#');
	BinaryTree<int> t2;
	t2 = t1;
	cout << "先序遍歷："; 
	t2.PrevOrder();
	cout << "中序遍歷：";
	t2.InOrder();
	cout << "后序遍歷：";
	t2.PostOrder();
	cout << "層次遍歷：";
	t2.LevelOrder();
	cout << "size:" << t2.Size() << endl;
	cout << "depth:" << t2.Depth() << endl;
	cout << "leafSize:" << t2.LeafSize() << endl;
}
int main()
{
	TestBinary();
	getchar();
	return 0;
}

測試結果