※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

======================================================================================================

二叉樹

在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結點至多隻有二棵子樹(不存在出度大于2的結點)，二叉樹的子樹有左右之分，次序不能颠倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為，出度為2的結點數為，則=+ 1。

基本形态

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形态：

(1)空二叉樹——(a)；

(2)隻有一個根結點的二叉樹——(b)；

(3)隻有左子樹——(c)；

(4)隻有右子樹——(d)；

(5)完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

重要概念

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)深度——二叉樹的層數，就是高度。

性質

(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；

(2) 深度為h的二叉樹最多有2^h-1個結點(h>=1)，最少有h個結點；

(3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；

(4) 具有n個結點的完全二叉樹的深度為int（log2n）+1

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編号則如果I>1，則其父結點的編号為I/2；

如果2*I<=N，則其左兒子（即左子樹的根結點）的編号為2*I；若2*I>N，則無左兒子；

如果2*I+1<=N，則其右兒子的結點編号為2*I+1；若2*I+1>N，則無右兒子。

(6)給定N個節點，能構成h(N)種不同的二叉樹。

h(N)為卡特蘭數的第N項。h(n)=C(n,2*n)/(n+1)。

(7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i

1.完全二叉樹（Complete Binary Tree）

若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若幹結點，這就是完全二叉樹。

2.滿二叉樹（Full Binary Tree）

一個高度為h的二叉樹包含正是2^h-1元素稱為滿二叉樹。

二叉樹四種周遊

1.先序周遊（僅二叉樹）

指先通路根，然後通路孩子的周遊方式

非遞歸實作

利用棧實作，先取根節點，處理節點，然後依次周遊左節點，遇到有右節點壓入棧，向左走到盡頭。然後從棧中取出右節點，處理右子樹。

/*** PreOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	BOOL
* @note Pre-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeBinSeq<T>::PreOrderTraversal(AL_ListSeq<T>& listOrder) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	PreOrderTraversal(m_pRootNode, listOrder);
	return TRUE;
	
	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSeq<T>*> cStack;
	AL_TreeNodeBinSeq<T>* pTreeNode = m_pRootNode;

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			listOrder.InsertEnd(pTreeNode->GetData());
			if (NULL != pTreeNode->GetChildRight()) {
				//push the child right to stack
				cStack.Push(pTreeNode->GetChildRight());
			}
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL == pTreeNode) {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
		
	}
	return TRUE;
}

遞歸實作

/**
* PreOrderTraversal
*
* @param	const AL_TreeNodeBinSeq<T>* pCurTreeNode <IN>	
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	VOID
* @note Pre-order traversal
* @attention Recursion Traversal
*/
template<typename T> VOID 
AL_TreeBinSeq<T>::PreOrderTraversal(const AL_TreeNodeBinSeq<T>* pCurTreeNode, AL_ListSeq<T>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return;
	}
	//Do Something with root
	listOrder.InsertEnd(pCurTreeNode->GetData());

	if(NULL != pCurTreeNode->GetChildLeft()) {
		PreOrderTraversal(pCurTreeNode->GetChildLeft(), listOrder);
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		PreOrderTraversal(pCurTreeNode->GetChildRight(), listOrder);
	}
}

2.中序周遊（僅二叉樹）

指先通路左（右）孩子，然後通路根，最後通路右（左）孩子的周遊方式

非遞歸實作

利用棧實作，先取根節點，然後依次周遊左節點，将左節點壓入棧，向左走到盡頭。然後從棧中取出左節點，處理節點。然後處理其右子樹。

/**
* InOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	BOOL
* @note In-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeBinSeq<T>::InOrderTraversal(AL_ListSeq<T>& listOrder) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	listOrder.Clear();
	
	//Recursion Traversal
	InOrderTraversal(m_pRootNode, listOrder);
	return TRUE;

	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSeq<T>*> cStack;
	AL_TreeNodeBinSeq<T>* pTreeNode = m_pRootNode;

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			pTreeNode = pTreeNode->GetChildLeft();
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode->GetData());
				if (NULL != pTreeNode->GetChildRight()){
					//child right exist, push the node, and loop it's left child to push
					pTreeNode = pTreeNode->GetChildRight();
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

遞歸實作

/**
* InOrderTraversal
*
* @param	const AL_TreeNodeBinSeq<T>* pCurTreeNode <IN>	
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	VOID
* @note In-order traversal
* @attention Recursion Traversal
*/
template<typename T> VOID 
AL_TreeBinSeq<T>::InOrderTraversal(const AL_TreeNodeBinSeq<T>* pCurTreeNode, AL_ListSeq<T>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return;
	}
	
	if(NULL != pCurTreeNode->GetChildLeft()) {
		InOrderTraversal(pCurTreeNode->GetChildLeft(), listOrder);
	}

	//Do Something with root
	listOrder.InsertEnd(pCurTreeNode->GetData());

	if(NULL != pCurTreeNode->GetChildRight()) {
		InOrderTraversal(pCurTreeNode->GetChildRight(), listOrder);
	}
}

3.後序周遊（僅二叉樹）

指先通路孩子，然後通路根的周遊方式

非遞歸實作

利用棧實作，先取根節點，然後依次周遊左節點，将左節點壓入棧，向左走到盡頭。然後從棧中取出左節點，處理節點。處理其右節點，還需要記錄已經使用過的節點，比較麻煩和複雜。大緻思路如下：

1.找到最左邊的子節點
2.如果最左邊的子節點有右節點，處理右節點（類似1）
3.從棧裡彈出節點處理
3.當碰到左右節點都存在的節點時，需要進行記錄了回歸節點了。然後以目前節點的右子樹進行處理
4.碰到回歸節點時，把目前的最後一個元素消除（因為後面還會回歸到這個點的）。

/**
* PostOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	BOOL
* @note Post-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeBinSeq<T>::PostOrderTraversal(AL_ListSeq<T>& listOrder) const
{
	if (NULL == m_pRootNode) {
		return FALSE;
	}

	listOrder.Clear();

	//Recursion Traversal
	PostOrderTraversal(m_pRootNode, listOrder);
	return TRUE;

	//Not Recursion Traversal
	AL_StackSeq<AL_TreeNodeBinSeq<T>*> cStack;
	AL_TreeNodeBinSeq<T>* pTreeNode = m_pRootNode;
	AL_StackSeq<AL_TreeNodeBinSeq<T>*> cStackReturn;
	AL_TreeNodeBinSeq<T>* pTreeNodeReturn = NULL;

	while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
		while (NULL != pTreeNode) {
			cStack.Push(pTreeNode);
			if (NULL != pTreeNode->GetChildLeft()) {
				pTreeNode = pTreeNode->GetChildLeft();
			}
			else {
				//has not left child, get the right child
				pTreeNode = pTreeNode->GetChildRight();
			}
		}

		if (TRUE == cStack.Pop(pTreeNode)) {
			if (NULL !=  pTreeNode) {
				listOrder.InsertEnd(pTreeNode->GetData());
				if (NULL != pTreeNode->GetChildLeft() && NULL != pTreeNode->GetChildRight()){
					//child right exist
					cStackReturn.Top(pTreeNodeReturn);
					if (pTreeNodeReturn != pTreeNode) {
						listOrder.RemoveAt(listOrder.Length()-1);
						cStack.Push(pTreeNode);
						cStackReturn.Push(pTreeNode);
						pTreeNode = pTreeNode->GetChildRight();
					}
					else {
						//to pop the node in the stack
						cStackReturn.Pop(pTreeNodeReturn);
						pTreeNode = NULL;
					}
				}
				else {
					//to pop the node in the stack
					pTreeNode = NULL;
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}

	return TRUE;
}

遞歸實作

/**
* PostOrderTraversal
*
* @param	const AL_TreeNodeBinSeq<T>* pCurTreeNode <IN>	
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	VOID
* @note Post-order traversal
* @attention Recursion Traversal
*/
template<typename T> VOID 
AL_TreeBinSeq<T>::PostOrderTraversal(const AL_TreeNodeBinSeq<T>* pCurTreeNode, AL_ListSeq<T>& listOrder) const
{
	if (NULL == pCurTreeNode) {
		return;
	}

	if(NULL != pCurTreeNode->GetChildLeft()) {
		PostOrderTraversal(pCurTreeNode->GetChildLeft(), listOrder);
	}

	if(NULL != pCurTreeNode->GetChildRight()) {
		PostOrderTraversal(pCurTreeNode->GetChildRight(), listOrder);
	}

	//Do Something with root
	listOrder.InsertEnd(pCurTreeNode->GetData());
}

4.層次周遊

一層一層的通路，是以一般用廣度優先周遊。

非遞歸實作

利用連結清單或者隊列均可實作，先取根節點壓傳入連結表或者隊列，依次從左往右體通路子節點，壓傳入連結表或者隊列。直至處理完所有節點。

/**
* LevelOrderTraversal
*
* @param	AL_ListSeq<T>& listOrder <OUT>
* @return	BOOL
* @note Level-order traversal
* @attention 
*/
template<typename T> BOOL 
AL_TreeBinSeq<T>::LevelOrderTraversal(AL_ListSeq<T>& listOrder) const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	if (NULL == m_pRootNode) {
		return FALSE;
	}
	listOrder.Clear();
	/*
	AL_ListSeq<AL_TreeNodeBinSeq<T>*> listNodeOrder;
	listNodeOrder.InsertEnd(m_pRootNode);
	//loop the all node
	DWORD dwNodeOrderLoop = 0x00;
	AL_TreeNodeBinSeq<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinSeq<T>* pNodeOrderChild = NULL;
	while (TRUE == listNodeOrder.Get(pNodeOrderLoop, dwNodeOrderLoop)) {
		dwNodeOrderLoop++;
		if (NULL != pNodeOrderLoop) {
			listOrder.InsertEnd(pNodeOrderLoop->GetData());
			pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
			pNodeOrderChild = pNodeOrderLoop->GetChildRight();
			if (NULL != pNodeOrderChild) {
				queueOrder.Push(pNodeOrderChild);
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
	*/
	
	AL_QueueSeq<AL_TreeNodeBinSeq<T>*> queueOrder;
	queueOrder.Push(m_pRootNode);
	
	AL_TreeNodeBinSeq<T>* pNodeOrderLoop = NULL;
	AL_TreeNodeBinSeq<T>* pNodeOrderChild = NULL;
	while (FALSE == queueOrder.IsEmpty()) {
		if (TRUE == queueOrder.Pop(pNodeOrderLoop)) {
			if (NULL != pNodeOrderLoop) {
				listOrder.InsertEnd(pNodeOrderLoop->GetData()); 
				pNodeOrderChild = pNodeOrderLoop->GetChildLeft();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
				pNodeOrderChild = pNodeOrderLoop->GetChildRight();
				if (NULL != pNodeOrderChild) {
					queueOrder.Push(pNodeOrderChild);
				}
			}
			else {
				return FALSE;
			}
		}
		else {
			return FALSE;
		}
	}
	return TRUE;
}

遞歸實作（無）

======================================================================================================

樹（tree）

樹（tree）是包含n（n>0）個結點的有窮集合，其中：

每個元素稱為結點（node）；
有一個特定的結點被稱為根結點或樹根（root）。
除根結點之外的其餘資料元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹也可以這樣定義：樹是由根結點和若幹顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。

我們可以形式地給出樹的遞歸定義如下:

單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分别為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱n1,n2,..,nk為結點n的子樹。
空集合也是樹，稱為空樹。空樹中沒有結點。

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

樹的四種周遊

1.先序周遊（僅二叉樹）

指先通路根，然後通路孩子的周遊方式

2.中序周遊（僅二叉樹）

指先通路左（右）孩子，然後通路根，最後通路右（左）孩子的周遊方式

3.後序周遊（僅二叉樹）

指先通路孩子，然後通路根的周遊方式

4.層次周遊

一層一層的通路，是以一般用廣度優先周遊。

======================================================================================================

樹結點順序存儲結構（tree node sequence）

結點：

包括一個資料元素及若幹個指向其它子樹的分支；例如，A，B，C，D等。

在資料結構的圖形表示中，對于資料集合中的每一個資料元素用中間标有元素值的方框表示，一般稱之為資料結點，簡稱結點。

在C語言中，連結清單中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為使用者需要用的實際資料；二為下一個結點的位址，即指針域和資料域。

資料結構中的每一個資料結點對應于一個儲存單元，這種儲存單元稱為儲存結點，也可簡稱結點

樹結點（樹節點）：

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

樹節點相關術語：

節點的度：一個節點含有的子樹的個數稱為該節點的度；
葉節點或終端節點：度為0的節點稱為葉節點；
非終端節點或分支節點：度不為0的節點；
雙親節點或父節點：若一個結點含有子節點，則這個節點稱為其子節點的父節點；
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
節點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推；
堂兄弟節點：雙親在同一層的節點互為堂兄弟；
節點的祖先：從根到該節點所經分支上的所有節點；
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。

根據樹結點的相關定義，采用“雙親孩子表示法”。其屬性如下：

DWORD								m_dwLevel;				//Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	T									m_data;					//the friend class can use it directly

	AL_TreeNodeSeq<T>*					m_pParent;				//Parent position
	AL_ListSeq<AL_TreeNodeSeq<T>*>		m_listChild;			//All Child tree node

樹的幾種表示法

在實際中，可使用多種形式的存儲結構來表示樹，既可以采用順序存儲結構，也可以采用鍊式存儲結構，但無論采用何種存儲方式，都要求存儲結構不但能存儲各結點本身的資料資訊，還要能唯一地反映樹中各結點之間的邏輯關系。

1．雙親表示法

由于樹中的每個結點都有唯一的一個雙親結點，是以可用一組連續的存儲空間（一維數組）存儲樹中的各個結點，數組中的一個元素表示樹中的一個結點，每個結點含兩個域，資料域存放結點本身資訊，雙親域訓示本結點的雙親結點在數組中位置。

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

2．孩子表示法

1.多重連結清單：每個結點有多個指針域，分别指向其子樹的根

1）結點同構：結點的指針個數相等，為樹的度k,這樣n個結點度為k的樹必有n(k-1)+1個空鍊域.

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

2）結點不同構：結點指針個數不等，為該結點的度d

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

2.孩子連結清單：每個結點的孩子結點用單連結清單存儲，再用含n個元素的結構數組指向每個孩子連結清單

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

3．雙親孩子表示法

1.雙親表示法，PARENT（T，x）可以在常量時間内完成，但是求結點的孩子時需要周遊整個結構。

2.孩子連結清單表示法，适于那些涉及孩子的操作，卻不适于PARENT（T，x）操作。

3.将雙親表示法和孩子連結清單表示法合在一起，可以發揮以上兩種存儲結構的優勢，稱為帶雙親的孩子連結清單表示法

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

4．雙親孩子兄弟表示法（二叉樹專用）

又稱為二叉樹表示法，以二叉連結清單作為樹的存儲結構。

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

順序存儲結構

在計算機中用一組位址連續的存儲單元依次存儲線性表的各個資料元素,稱作線性表的順序存儲結構.　

順序存儲結構是存儲結構類型中的一種，該結構是把邏輯上相鄰的節點存儲在實體位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來展現。由此得到的存儲結構為順序存儲結構，通常順序存儲結構是借助于計算機程式設計語言（例如c/c++）的數組來描述的。

順序存儲結構的主要優點是節省存儲空間，因為配置設定給資料的存儲單元全用存放結點的資料（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關系沒有占用額外的存儲空間。采用這種方法時，可實作對結點的随機存取，即每一個結點對應一個序号，由該序号可以直接計算出來結點的存儲位址。但順序存儲方法的主要缺點是不便于修改，對結點的插入、删除運算時，可能要移動一系列的結點。

優點：

随機存取表中元素。缺點：插入和删除操作需要移動元素。

本代碼預設list可以容納的item數目為100個，使用者可以自行設定item數目。當list飽和時，由于Tree是非線性結構，動态擴充記憶體相當麻煩。是以示例中的Demo及代碼将不會動态擴充記憶體。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

以後的筆記潇汀會盡量詳細講解一些相關知識的，希望大家繼續關注我的部落格。

本節筆記到這裡就結束了。

潇汀一有時間就會把自己的學習心得，覺得比較好的知識點寫出來和大家一起分享。

程式設計開發的路很長很長，非常希望能和大家一起交流，共同學習，共同進步。

如果文章中有什麼疏漏的地方，也請大家指正。也希望大家可以多留言來和我探讨程式設計相關的問題。

最後，謝謝你們一直的支援~~~

C++完整個代碼示例（代碼在VS2005下測試可運作）

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）

繼續閱讀

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

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裝置模型（中）之上層容器

※資料結構※→☆非線性結構（tree）☆============二叉樹 順序存儲結構（tree binary sequence）（十九）

繼續閱讀

※資料結構※→☆非線性結構（tree）☆============二叉樹順序存儲結構（tree binary sequence）（十九）