文章目錄

• 基本術(shù)語
• 二叉樹
• 滿二叉樹與完全二叉樹
• 二叉樹的存儲(chǔ)（略）
• 順序存儲(chǔ)（略）
• 鏈?zhǔn)酱鎯?chǔ)（略）
• 二叉樹的遍歷
• 先左后右的遍歷算法
• 先（根）序遍歷
• 中（根）序遍歷
• 后（根）序遍歷
• 先序、中序、后序遍歷的非遞歸實(shí)現(xiàn)
• 構(gòu)造二叉樹

基本術(shù)語

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

二叉樹

二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別被稱為左子樹和右子樹的、互不相交的二叉樹組成。
二叉樹的性質(zhì)：

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

滿二叉樹與完全二叉樹

滿二叉樹：深度為K且含有2^K - 1個(gè)結(jié)點(diǎn)的二叉樹

完全二叉樹：樹中所含的結(jié)點(diǎn)與滿二叉樹的結(jié)點(diǎn)編號(hào)一一對(duì)應(yīng)

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

二叉樹的存儲(chǔ)（略）

順序存儲(chǔ)（略）

鏈?zhǔn)酱鎯?chǔ)（略）

二叉樹的遍歷

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

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

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

先左后右的遍歷算法

先（根）序遍歷

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

中（根）序遍歷

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

后（根）序遍歷

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

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

先序遍歷非遞歸：

中序遍歷非遞歸：

后序遍歷非遞歸：

層次遍歷非遞歸：

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

構(gòu)造二叉樹

已知二叉樹的先序序列和中序序列可以唯一確定一棵樹
已知二叉樹的后序序列和中序序列可以唯一確定一棵樹
已知二叉樹的先序序列和后序序列不可以唯一確定一棵樹，因?yàn)闊o法確定左右子樹。