1、前言

在現實生活中，大部分事物之間的關系都是非常複雜的，單從事物聯系的數量來說，有的是一對一的關系，有的是一對多的關系，有的是多對多的關系。這就誕生了除了線性結構以外，還包含了樹結構和圖結構。樹結構通常來免回一對多的關系，圖結構則總是用在多對多的關系。前者比如族譜，後者比如交通圖。是以，對于它們的了解，可以加強我們對現實生活的事物之間的抽象了解，這樣才可以開發處符合現實生活的資料結構。本文主要講解樹結構。

2、樹結構的概念

接下來通過二叉樹來了解樹結構，因為二叉樹是一個典型的例子，通過它就可以推廣到整個樹結構。

二叉樹是有限個資料元素的集合，這個集合或者為空，或者隻有一個根節點，又或者含有左子樹和右子樹的二叉樹。當集合為空時，則稱為這個二叉樹為空二叉樹。二叉樹的每一個元素又稱為節點。

3、樹結構相關專業術語

節點的度：節點的分支數叫做這個節點的度。

葉節點：節點的分支數為0的節點稱為葉節點。既不含有子元素。

分支節點：節點的分支數不為0的節點稱為分支節點。即含有子元素。

左孩子，右孩子，雙親，兄弟：如果一個節點擁有子元素，那麼它的左邊的子元素稱為左孩子，右邊的子元素稱為右孩子。對于孩子節點來說，這個節點就是雙親節點。而左孩子與右孩子互相又稱為兄弟節點。

路徑，路徑長度：如果一棵樹中的含有一串節點，節點n 1,n2......nk，其中ni是ni-1的父元素，則稱這段節點為n1到nk的路徑。這段路徑的長度為k-1。

祖先，子孫：如果存在一條從ni到nk的路徑，則稱ni是nk的在子孫。

節點的層數：規定根節點的層數為1，其餘節點為其父節點的層數+1。

滿二叉樹：如果一棵樹的每一層的節點都達到了最大值（2的（n-1)次方)，則稱這棵樹為滿二叉樹。滿二叉樹的特點除了葉子結點外，所有的分支節點都含有左子樹和右子樹。

完全二叉樹：假設根節點的标号是1，其餘節點均按次序從上到下，從左到右編号，每個編号均和滿二叉樹相同，則稱這棵二叉樹為完全二叉樹。完全二叉樹不一定是滿二叉樹，滿二叉樹一定是完全二叉樹。因為完全二叉樹的最後一層的節點可以不達到該層的最大節點數。

4、二叉樹的主要性質以及證明

性質1 一棵非空二叉樹第i層上最多有2的（i-1)次方個節點（i>=1）

思路：這種證明題，通常都是使用數學歸納法證明的。

證明：

二叉樹的基本性質及使用實作1、前言 2、樹結構的概念3、樹結構相關專業術語4、二叉樹的主要性質以及證明5、二叉樹的基本運算6、二叉樹的存儲方式7、二叉連結清單的基本實作

性質2：一棵深度額為k的二叉樹，最多具有2的k次方-1個節點。

證明思路：證明每一層的節點數相加不超過2的k次方-1即可。

證明：

性質3：對于一顆非空的二叉樹，若葉子結點數為n0,度數為2的節點數為n2，則有n0=n2+1

證明思路：要證明度數為0的節點和度數為2的節點的關系，我們需要為他們之間建立關系式。首先可以從節點總數出發，即n=n0+n1+n2，接着我們需要借助其他證明把n1和n0以及n2的關系求出來，既可以得到n0和n2的關系。

證明：

性質4：由于涉及到對數，不好寫直接上圖。

5、二叉樹的基本運算

1、initial，建立一棵空的二叉樹。建議的做法是用一個頭節點指向根節點。

2、create，建立二叉樹的根節點。

3、insertL，給根節點插入左孩子節點，如果根節點本身含有左孩子節點，則将原來的左孩子節點作為目前結點的左孩子節點，目前結點則作為根節點的左孩子節點。

4、insertR，給根結點插入右孩子節點，如果根節點本身含有右孩子節點，則将原來的右孩子節點作為目前結點的右孩子節點，目前結點則作為根節點的右孩子節點。

5、deleteL，在二叉樹中删除某個節點的左子樹。

6、deleteR，在二叉樹中删除某個節點的右子樹。

7、search，在二叉樹中查找某個值得節點元素。

8、traverse，周遊二叉樹的所有節點。常用的周遊方式有三種，前序周遊，中序周遊，後序周遊。後面會展開講解。

6、二叉樹的存儲方式

基本運算是資料結構的邏輯實作，具體的實作必須确認了存儲方式才能實作，是以現在必須先了解二叉樹可用的存儲方式。

6.1、順序存儲結構

順序存儲結構在實作上就是利用數組來存儲一組相鄰的元素。在二叉樹中，分為滿二叉樹，完全二叉樹以及一般的二叉樹。事實上，如果用數組來存儲二叉樹的元素，這裡按照從上到下，從左到右的次序存儲二叉樹中的元素。考慮到相鄰元素之間必須在二叉樹裡面也是相鄰的，也隻有滿二叉樹，完全二叉樹可以毫無縫隙的對接樹的相鄰元素和數組的相鄰元素恰好是相鄰關系。而一般的二叉樹，如果也希望用數組存儲，并且數組的相鄰元素在二叉樹上也是相鄰元素，隻能對樹結構進行完全化後再進行存儲。

完全化：即對于樹中的元素，按照從上到下，從左到右的次序存儲，一旦遇到空的元素，就用NULL補齊，直到最後一個元素被存儲。這樣，如果相鄰的元素是NULL，說明該元素并沒有在樹結構上相鄰的元素。因為看上去用NULL補齊的樹，就像一棵完全二叉樹，是以稱為完全化。

綜上所述，如果二叉樹的結構是滿二叉樹或者完全二叉樹，那麼可以考慮使用數組存儲。但如果是一般的二叉樹則不建議，因為完全化後的二叉樹，空元素也需要占據空間，但實際上，這些元素并沒有實際含義，是以會導緻大量的空間浪費。

無論什麼結構的二叉樹，都建議使用鍊式存儲結構。

6.2、鍊式存儲結構

鍊式存儲結構，即用連結清單的方式存儲二叉樹的結構，在此又分為二叉連結清單存儲和三叉連結清單存儲，它們的結構如下：

二叉連結清單：

三叉連結清單：

二叉樹的基本性質及使用實作1、前言 2、樹結構的概念3、樹結構相關專業術語4、二叉樹的主要性質以及證明5、二叉樹的基本運算6、二叉樹的存儲方式7、二叉連結清單的基本實作

二叉連結清單存儲，包含三個資訊，左孩子節點指針，右孩子節點指針，以及資料域。如果沒有孩子節點，則将指針域置為NULL。使用二叉連結清單結構，一般會建立一個頭節點，并将其中的左子樹指向根節點，右子樹為NULL，這樣友善了後續的操作。

三叉連結清單存儲，除了含有二叉連結清單的結構外，還含有一個雙親節點指針域，指向它的雙親節點。這是典型的空間換時間的方法，如果涉及的操作需要頻繁通路雙親節點，就建議使用三叉連結清單的存儲結構。

對于一般的二叉樹而言，二叉連結清單存儲是最簡單有效的方式，也是推薦使用的。

7、二叉連結清單的基本實作

在給出代碼之前，先講述二叉樹的周遊方法。

先序周遊是先通路父元素在通路左孩子最後是右孩子。

中序周遊是先通路左孩子再通路父節點最後是右孩子。

後序周遊是先通路左孩子在通路右孩子最後通路父節點。

看了很多解釋周遊的解說，都是特别抽象難懂的，筆者的建議是，結合代碼以及提到的周遊的方法，一步一步調試，才會比較容易的去了解。

代碼如下：

Node.h

#include<string>


class Node
{
public:
	Node();
	~Node();
	std::string data;
	Node *lChild;
	Node *rChild;

private:

};

Node::Node()
{
}

Node::~Node()
{
}

BinaryTree.h

#include "Node.h"
#include <iostream>
#include<stack>

/*
初始化二叉樹的表頭
*/
Node *initial()
{
	Node *header = new Node;
	header->lChild = nullptr;
	header->rChild = nullptr;
	header->data = " ";
	return header;
}

/*
建立根節點
*/
void createRoot(std::string data, Node *header)
{
	Node *root = new Node();
	root->data = data;
	root->lChild = nullptr;
	root->rChild = nullptr;
	header->lChild = root;//将樹的根節點儲存在頭節點的左節點。以後的操作隻要正對根節點就行了
}

/*
給根結點添加左孩子節點，如果根節點本身就存在左孩子節點就将目前結點作為根節點的左孩子，之前的左孩子節點作為新的節點的左孩子節點
*/


void insertL(std::string data, Node *header)
{
	Node *root = header->lChild;
	Node *lChild = new Node();
	lChild->data = data;
	lChild->rChild = nullptr;//新添加的節點應該是不含孩子節點的，但如果根節點本身就有左孩子節點，則此節點有左孩子節點
	if (root->lChild != nullptr)
		lChild->lChild = root->lChild;
	else
		lChild->lChild = nullptr;
	root->lChild = lChild;
}


/*
給根結點添加右孩子節點，如果根節點本身就存在右孩子節點就将目前結點作為根節點的右孩子，之前的右孩子節點作為新的節點的右孩子節點
*/


void insertR(std::string data, Node *header)
{
	Node *root = header->lChild;
	Node *rChild = new Node();
	rChild->data = data;
	rChild->lChild = nullptr;//新添加的節點應該是不含孩子節點的，但如果根節點本身就有右孩子節點，則此節點有右孩子節點
	if (root->rChild != nullptr)
		rChild->rChild = root->rChild;
	else
		rChild->rChild = nullptr;
	root->rChild = rChild;
}


/*
删除某個節點的左子樹
*/
void deleteL(Node *parent, Node *header)
{
	if (parent == nullptr || parent->lChild == nullptr)
		return;
	else
	{
		Node *lChild = parent->lChild;
		parent->lChild = nullptr;
		lChild = nullptr;
		free(lChild);
	}
}

/*
删除某個節點的右孩子樹
*/
void deleteR(Node *parent, Node *header)
{
	if (parent == nullptr || parent->rChild == nullptr)
		return;
	else
	{
		Node *rChild = parent->rChild;
		parent->rChild = nullptr;
		rChild = nullptr;
		free(rChild);
	}
}

/*
查找某個資料的節點元素
*/

Node *search(std::string data, Node *header)
{
	Node *root = header->lChild;
	Node *item = header->lChild;
	std::stack<Node *> nodeStack;
	nodeStack.push(item);
	//先序周遊查找節點	
	while (item != nullptr || nodeStack.size() != 0)
	{

		while (item != nullptr)
		{
			if (item->data == data)
				return item;
			if (item != header->lChild)
				nodeStack.push(item);
			item = item->lChild;

		}
		if (nodeStack.size() == 0)
			return nullptr;
		item = nodeStack.top();
		nodeStack.pop();
		item = item->rChild;
	}
	return nullptr;

}

/*
先序周遊二叉樹
*/
void preTraveler(Node *header)
{
	Node *item = header->lChild;
	//需要用一個棧來儲存所有通路過的元素，這樣才能通路目前元素的父元素
	std::stack<Node *> nodeStack;
	nodeStack.push(item);
	//隻有當棧沒有元素了，item也是null的時候，才說明二叉樹通路完畢
	while (item != nullptr || nodeStack.size() != 0)
	{

		while (item != nullptr)
		{
			//将左子樹入棧
			std::cout << item->data << " ";
			if (item != header->lChild)
				nodeStack.push(item);
			item = item->lChild;
			

		}
		//如果棧中沒有元素，說明所有的元素都通路過了。
		if (nodeStack.size() == 0)
			return;
		//彈出棧頂元素
		item = nodeStack.top();
		nodeStack.pop();
		item = item->rChild;
	}

}


/*
中序周遊二叉樹
和先序周遊不同的地方在于，通路節點資料的位置不同。
先序周遊是先通路節點在入棧，中序周遊則是先入棧在通路節點
*/
void midTraveler(Node *header)
{
	Node *item = header->lChild;
	std::stack<Node *> nodeStack;
	nodeStack.push(item);
	while (item != nullptr || nodeStack.size() != 0)
	{

		while (item != nullptr)
		{
			
			if (item != header->lChild)
				nodeStack.push(item);
			item = item->lChild;


		}
		if (nodeStack.size() == 0)
			return;
		item = nodeStack.top();
		std::cout << item->data << " ";
		nodeStack.pop();
		item = item->rChild;
	}

}

Main.cpp

#include"BinaryTree.h"
#include<sstream>//fstream


int main()
{
	Node *header = initial();
	createRoot("root", header);//建立根節點
	//将偶數插入左子樹，奇數插入右子樹。
	//由于每次都插入到根節點的字數，導緻數的結構是左子樹隻有左孩子，右子樹隻有右孩子。
	//其實insertL可以傳遞的header可以改成需要作為父元素的節點，這樣就可避免除出現簽名的情況
	std::stringstream inS;
	for (int i = 1; i <= 100; i++)
	{
		inS <<std::unitbuf<< i<<std::nounitbuf;
		if (i % 2 == 0)
			insertL(inS.str(), header);
		else
			insertR(inS.str(), header);
		inS.str("");//必須情況内容，否則的話，會把前面的内容拼合起來
	}
	//先序周遊
	preTraveler(header);
	std::cout << std::endl;
	//中序周遊
	midTraveler(header);

	return 0;
}

筆者隻是實作了先序周遊和中序周遊，後續周遊的流程比較複雜一點，目前暫時沒有思路。有興趣的讀者可以自己去研究。

---------文章寫自：HyHarden---------

--------部落格位址：http://blog.csdn.net/qq_25722767-----------

二叉樹的基本性質及使用實作1、前言 2、樹結構的概念3、樹結構相關專業術語4、二叉樹的主要性質以及證明5、二叉樹的基本運算6、二叉樹的存儲方式7、二叉連結清單的基本實作

1、前言

2、樹結構的概念

3、樹結構相關專業術語

4、二叉樹的主要性質以及證明

5、二叉樹的基本運算

6、二叉樹的存儲方式

6.1、順序存儲結構

6.2、鍊式存儲結構

二叉樹的基本性質及使用實作1、前言 2、樹結構的概念3、樹結構相關專業術語4、二叉樹的主要性質以及證明5、二叉樹的基本運算6、二叉樹的存儲方式7、二叉連結清單的基本實作

7、二叉連結清單的基本實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器