文章目錄

• 基本術語
• 二叉樹
• 滿二叉樹與完全二叉樹
• 二叉樹的存儲（略）
• 順序存儲（略）
• 鏈式存儲（略）
• 二叉樹的遍歷
• 先左后右的遍歷算法
• 先（根）序遍歷
• 中（根）序遍歷
• 后（根）序遍歷
• 先序、中序、后序遍歷的非遞歸實現(xiàn)
• 構造二叉樹

基本術語

結點：數(shù)據元素 若干指向子樹的分支
結點的度：分支的個數(shù)
樹的度：樹中所有結點的度的最大值
葉子結點：度為零的結點
分支結點：度大于零的結點
路徑：從根到該結點所經過的分支和結點
孩子結點：結點的子樹的根
雙親結點：上一層的直系結點
結點的層次：根節(jié)點的層次為1，第L層的結點的子樹的根節(jié)點的層次為L 1
樹的深度：樹中葉子結點的最大層次
森林：m(m>=0)棵互不相交的樹的集合
樹：任何一棵非空樹是一個二元組Tree=（root,F），其中，root稱為根結點，F(xiàn)是子樹森林

二叉樹

二叉樹或為空樹；或是由一個根結點加上兩棵分別被稱為左子樹和右子樹的、互不相交的二叉樹組成。
二叉樹的性質：

• 在二叉樹的第i層上最多有2^i-1（2的i-1次方）個結點（i>=1）
• 深度為k的二叉樹上最多含有2^k - 1（2的k次方減一）個結點
• 對任何一棵二叉樹，若它含有n0個葉子結點，n2個度為2的結點，則必然存在關系式：n0 = n2 1

滿二叉樹與完全二叉樹

滿二叉樹：深度為K且含有2^K - 1個結點的二叉樹

完全二叉樹：樹中所含的結點與滿二叉樹的結點編號一一對應

• 具有n個結點的完全二叉樹的深度為 (log2n) 1
• 若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點：
  (1) 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編號為 i/2 的結點為其雙親結點
  (2) 若 2i>n，則該結點無左孩子，否則，編號為 2i 的結點為其左孩子結點；
  (3) 若 2i 1>n，則該結點無右孩子結點， 否則，編號為2i 1 的結點為其右孩子結點

二叉樹的存儲（略）

順序存儲（略）

鏈式存儲（略）

二叉樹的遍歷

對二叉樹而言，可以有以下三種遍歷路徑：
（1）先上后下的按層次遍歷（使用隊列）
（2）先左（子樹）后右（子樹）的遍歷

• 先序遍歷（使用棧）
• 中序遍歷（使用棧）
• 后序遍歷（使用棧）

（3）先右（子樹）后左（子樹）的遍歷

先左后右的遍歷算法

先（根）序遍歷

若二叉樹為空樹，則空操作，否則：（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

中（根）序遍歷

若二叉樹為空樹，則空操作；否則：（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。

后（根）序遍歷

若二叉樹為空樹，則空操作；否則：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。

先序、中序、后序遍歷的非遞歸實現(xiàn)

先序遍歷非遞歸：

中序遍歷非遞歸：

后序遍歷非遞歸：

層次遍歷非遞歸：

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
    	//樹為空，直接返回
    	if (root == NULL)
    	{
		return;
	}
	QueueInit(&q);
    	//先將根節(jié)點入隊
    	QueuePush(&q, root);
    	while (QueueEmpty(&q))
    	{
        	//出隊保存隊頭并訪問
        	BTNode* front = QueueFront(&q);
        	printf("%c", front->_data);
        	QueuePop(&q);
        	//將出隊結點的左子樹根入隊
        	if (front->_left)
            		QueuePush(&q, front->_left);
        	//將出隊結點的右子樹根入隊
        	if (front->_right)
            		QueuePush(&q, front->_right);  
    	} 	
}

構造二叉樹

已知二叉樹的先序序列和中序序列可以唯一確定一棵樹
已知二叉樹的后序序列和中序序列可以唯一確定一棵樹
已知二叉樹的先序序列和后序序列不可以唯一確定一棵樹，因為無法確定左右子樹。