首先先來看一下樹的結(jié)構(gòu)：

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、成都網(wǎng)站建設(shè)、平泉網(wǎng)絡(luò)推廣、小程序定制開發(fā)、平泉網(wǎng)絡(luò)營(yíng)銷、平泉企業(yè)策劃、平泉品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供平泉建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18980820575，官方網(wǎng)址：www.cdcxhl.com

樹是n（n>=0）個(gè)有限個(gè)數(shù)據(jù)的元素集合，形狀像一顆倒過來的樹。

而二叉樹就是樹的一種特殊結(jié)構(gòu)：

1. 完全二叉樹的數(shù)組表示

   

2. 鏈表存儲(chǔ)表示

下面我就實(shí)現(xiàn)一下二叉鏈的這種結(jié)構(gòu)：

首先是它的節(jié)點(diǎn)的結(jié)構(gòu)：

template 
struct BinaryTreeNode
{
public:
	BinaryTreeNode(const T &data)//構(gòu)造函數(shù)
		:_left(NULL)
		,_right(NULL)
		,_data(data)
	{}
public:
	BinaryTreeNode * _left;//左子樹
	BinaryTreeNode * _right;//右子樹
	T _data;//數(shù)據(jù)項(xiàng)
};

然后是它的基本成員函數(shù)：

template 
class BinaryTree
{
	typedef BinaryTreeNode Node;//重命名struct結(jié)構(gòu)
public:
	BinaryTree()//無參的構(gòu)造函數(shù)
		:_root(NULL)
	{}

	BinaryTree(const T* a, size_t size, const T& invalid)//有參構(gòu)造函數(shù)
		:_root(NULL)
	{
		size_t index = 0;
		_root = _CreatBinaryTree(a, size, invalid, index);
	}

	BinaryTree(const BinaryTree & t)//拷貝構(gòu)造
		:_root(NULL)
	{
		_root = _Copy(t._root);
	}

	BinaryTree& operator=(BinaryTree t)//賦值運(yùn)算符的重載
	{
		if (this != &t)//防止自賦值
		{
			swap(_root, t._root);
		}
		return *this;
	}

	~BinaryTree()//析構(gòu)函數(shù)
	{
		if (_root)
		{
			_Delete(_root);
		}
	}

	void PrevOrder()//前序遍歷
	{
		_PrevOrder(_root);
		cout << "over"<_left = _CreatBinaryTree(a, size, invalid, ++index);//遞歸創(chuàng)建左子樹
			cur->_right = _CreatBinaryTree(a, size, invalid, ++index);//遞歸創(chuàng)建右子樹
		}
		return cur;
	}
	//復(fù)制二叉樹
	Node* _Copy(Node * root)
	{
		Node * cur = NULL;
		if (root == NULL)
		{
			return NULL;
		}

		cur = new Node(root->_data);//創(chuàng)建該節(jié)點(diǎn)

		cur->_left = _Copy(root->_left);
		cur->_right = _Copy(root->_right);
		return cur;
	}
	//刪除
	void _Delete(Node * &root)
	{
		if (root == NULL)
		{
			return;
		}
		if (root->_left == NULL && root->_right == NULL)//該節(jié)點(diǎn)沒有左右孩子
		{
			delete root;//釋放該節(jié)點(diǎn)
			root = NULL;
			return;
		}
		_Delete(root->_left);
		_Delete(root->_right);
	}
	//前序遍歷：根節(jié)點(diǎn)--左子樹--右子樹
	void _PrevOrder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}

		cout << root->_data << "->";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}
	//中序遍歷：左子樹--根節(jié)點(diǎn)--右子樹
	void _InOrder(Node * root)
	{
		
		if (root == NULL)
		{
			return;
		}
		
		_PrevOrder(root->_left);
		cout << root->_data << "->";
		_PrevOrder(root->_right);
	}
	//后序遍歷：左子樹--右子樹--根節(jié)點(diǎn)
	void _PostOrder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}

		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
		cout << root->_data << "->";
	}
	//層次遍歷
	void _LevelOrder(Node* root)
	{
		queue q;
		if (root == NULL)
		{
			return;
		}
		q.push(root);
		while (!q.empty())
		{
			if (q.front()->_left != NULL)
			{
				q.push(q.front()->_left);
			}
			if (q.front()->_right != NULL)
			{
				q.push(q.front()->_right);
			}
			cout << q.front()->_data << "->";
			q.pop();
		}
	}
	//節(jié)點(diǎn)個(gè)數(shù)
	size_t _Size(Node * root)
	{
		if (root == NULL)
		{
			return 0;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;//當(dāng)左子樹或者右子樹不為空時(shí)，該節(jié)點(diǎn)有數(shù)據(jù)
	}
	//二叉樹的深度
	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;*/
		return leftDepth > rightDepth?leftDepth + 1 : rightDepth+1;
	}
	//葉子節(jié)點(diǎn)個(gè)數(shù)
	size_t _LeafSize(Node * root)
	{
		size_t size = 0;
		if (root == NULL)
		{
			return size;
		}
		if (root->_left == NULL&&root->_right == NULL)
		{
			size++;
			return size;
		}
		
		return _LeafSize(root->_left)+_LeafSize(root->_right);
	}



private:
	Node * _root;//根節(jié)點(diǎn)
};

測(cè)試用例以及結(jié)果如下：

void Test()
{
	int array1[10] = { 1, 2, 3, '#', '#', 4, '#' , '#', 5, 6 };
	BinaryTree b1(array1, 10, '#');
	cout << "前序遍歷：";
	b1.PrevOrder();
	cout << "中序遍歷：";
	b1.InOrder();
	cout << "后序遍歷：";
	b1.PostOrder();
	cout << "層次遍歷：";
	b1.LevelOredr();
	cout << endl;
	cout << "節(jié)點(diǎn)數(shù)：" << b1.Size() << endl;
	cout << "深度：" << b1.Depth() << endl;
	cout << "葉子節(jié)點(diǎn)數(shù)：" << b1.LeafSize() << endl;
	cout << endl;

	BinaryTree b2(b1);
	cout << "前序遍歷：";
	b2.PrevOrder();
	cout << "中序遍歷：";
	b2.InOrder();
	cout << "后序遍歷：";
	b2.PostOrder();
	cout << "層次遍歷：";
	b2.LevelOredr();
	cout << endl;
	cout << "節(jié)點(diǎn)數(shù)：" << b2.Size() << endl;
	cout << "深度：" << b2.Depth() << endl;
	cout << "葉子節(jié)點(diǎn)數(shù)：" << b2.LeafSize() << endl;
	cout << endl;

	BinaryTree b3;
	b3 = b1;
	cout << "前序遍歷：";
	b3.PrevOrder();
	cout << "中序遍歷：";
	b3.InOrder();
	cout << "后序遍歷：";
	b3.PostOrder();
	cout << "層次遍歷：";
	b3.LevelOredr();
	cout << endl;
	cout << "節(jié)點(diǎn)數(shù)：" << b3.Size() << endl;
	cout << "深度：" << b3.Depth() << endl;
	cout << "葉子節(jié)點(diǎn)數(shù)：" << b3.LeafSize() << endl;

}