第C語言詳解實現鏈式二叉樹的遍歷與相關接口目錄前言一、二叉樹的鏈式結構二、二叉樹的遍歷方式1.1遍歷方式的規則1.2前序遍歷1.3中序遍歷1.4后序遍歷1.5層序遍歷三、二叉樹的相關接口實現3.1二叉樹節點個數3.2二叉樹葉子節點個數3.3二叉樹第k層節點個數3.4二叉樹的深度(高度)3.5二叉樹查找值為x的節點3.6總結注意四、二叉樹的創建和銷毀4.1通過前序遍歷的字符串來構建二叉樹4.2二叉樹銷毀4.3判斷二叉樹是否是完全二叉樹

前言

二叉樹的順序結構就是用數組來存儲，而「數組」一般只適合表示「滿二叉樹」或「完全二叉樹」，因為不是完全二叉樹會有「空間的浪費」。

普通二叉樹的增刪查改沒有意義，主要學習它的結構，要加上搜索樹的規則，才有價值。

一、二叉樹的鏈式結構

在學習二叉樹的基本操作前，需先要創建一棵二叉樹，此處我們手動快速創建一棵簡單的二叉樹，快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創建方式。

#includestdio.h//perror,printf

#includestdlib.h//malloc

typedefcharBTDataType;

//定義二叉樹的節點

typedefstructBinaryTreeNode

BTDataTypedata;

structBinaryTreeNode*left;

structBinaryTreeNode*right;

}BTNode;

//動態申請一個新節點

BTNode*BuyNode(BTDataTypex)

BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));

if(newnode==NULL)

perror("malloc");

exit(-1);

newnode-data=x;

newnode-left=newnode-right=NULL;

returnnewnode;

//二叉樹的鏈式結構

BTNode*CreatBinaryTree()

//創建多個節點

BTNode*node_A=BuyNode('A');

BTNode*node_B=BuyNode('B');

BTNode*node_C=BuyNode('C');

BTNode*node_D=BuyNode('D');

BTNode*node_E=BuyNode('E');

BTNode*node_F=BuyNode('F');

//用鏈來指示節點間的邏輯關系

node_A-left=node_B;

node_A-right=node_C;

node_B-left=node_D;

node_C-left=node_E;

node_C-right=node_F;

returnnode_A;

}

注意：上述代碼并不是創建二叉樹的方式，真正創建二叉樹方式后續講解。

二、二叉樹的遍歷方式

1.1遍歷方式的規則

學習二叉樹結構，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次。訪問結點所做的操作依賴于具體的應用問題。遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷和層序遍歷：

前序遍歷(PreorderTraversal)：訪問根結點的操作發生在遍歷其左右子樹之前。

根--左子樹--右子樹

（比如上圖中，訪問的路徑為：ABDNULLNULLNULLCENULLNULLFNULLNULL）

中序遍歷(InorderTraversal)：訪問根結點的操作發生在遍歷其左右子樹之中（間）。

左子樹--根--右子樹

（比如上圖中，訪問的路徑為：NULLDNULLBNULLANULLENULLCNULLFNULL）

計算中序遍歷訪問路徑可以用簡單直觀的投影法：

后序遍歷(PostorderTraversal)：訪問根結點的操作發生在遍歷其左右子樹之后。

左子樹--右子樹--根

（比如上圖中，訪問的路徑為：NULLNULLDNULLBNULLNULLENULLNULLFCA）

層序遍歷(LevelOrdertraversal)：一層一層的走

（比如上圖中，訪問的路徑為：ABCDNULLEFNULLNULLNULLNULLNULLNULL）

由于被訪問的結點必是「某子樹的根」，所以N(Node）、L(Leftsubtree）和R(Rightsubtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

深度優先遍歷：前序、中序、后序

廣度優先遍歷：層序

【理解前/中/后序遍歷的思路】

前中后序遍歷中，每一顆子樹都會被分為（根、左子樹、右子樹）三部分來看待，分而治之。

舉個栗子：

校長想要統計全校學生的人數，他并不會自己挨個挨個去數，而是把每個年級的負責人叫過來，各年級負責人又把各班的班主任叫過來，各班主任又把各班班長叫過來，班長統計人數后，大家把結果再層層上報，最終傳回到校長這里，就知道學校總人數了。

1.2前序遍歷

代碼是非常簡單的：

//二叉樹前序遍歷

voidPreOrder(BTNode*root)

if(root)//先判斷樹是否為空

//根--左子樹--右子樹

printf("%c",root-data);

PreOrder(root-left);

PreOrder(root-right);

intmain()

//創建一顆鏈式二叉樹

BTNode*root=CreatBinaryTree();

//前序遍歷

PreOrder(root);//ABDCEF

return0;

前序遍歷函數遞歸調用圖解：每個函數調用，都會建立一個自己的棧幀。

前序遍歷遞歸圖解：

1.3中序遍歷

//二叉樹中序遍歷

voidInOrder(BTNode*root)

if(root)//先判斷樹是否為空

//左子樹--根--右子樹

InOrder(root-left);

printf("%c",root-data);

InOrder(root-right);

1.4后序遍歷

//二叉樹后序遍歷

voidPostOrder(BTNode*root)

if(root)//先判斷樹是否為空

//左子樹--右子樹--根

PostOrder(root-left);

PostOrder(root-right);

printf("%c",root-data);

1.5層序遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

核心思路：

用一個隊列來進行層序遍歷：

先入第一層的節點（根節點）上一層出來后，再入下一層（即它的左右孩子節點）

比如：

先入根節點A

根節點A出來后，再入它的孩子節點B和C

節點B出來后，再入它的孩子節點D和E，節點C出來后，再入它的孩子節點F

//二叉樹的層序遍歷

voidLevelOrder(BTNode*root)

LinkQueueq;//鏈式隊列

QueueInit(//初始化隊列

//樹的根節點root不為空，把根節點入隊

if(root)

QueuePush(q,root);

//當隊列不為空時，不斷的出隊，以及入隊根節點root的左右子樹

while(!QueueEmpty(q))

//當前樹的根節點出隊

BTNode*front=QueueFront(//獲取隊頭元素

printf("%c",front-data);//打印節點值

QueuePop(//出隊

//如果當前樹根的左右孩子不為空，則分別入隊

if(front-left)

QueuePush(q,front-left);

if(front-right)

QueuePush(q,front-right);

printf("\n");

QueueDestroy(//銷毀隊列

三、二叉樹的相關接口實現

3.1二叉樹節點個數

//二叉樹節點個數

/*方法一：

1、遞歸遍歷--用全局變量/靜態局部變量來記錄節點個數

2、遞歸遍歷--函數外定義一個局部變量記錄節點個數，傳址給函數

//方法二：分而治之的思路

intBinaryTreeSize(BTNode*root)

if(root==NULL)//1.先判斷當前訪問的節點是否為空

return0;

//2.當前節點不為空，節點個數累+1，則繼續訪問其左右子樹

return1+BinaryTreeSize(root-left)+BinaryTreeSize(root-right);

3.2二叉樹葉子節點個數

//二叉樹葉子節點個數

/*方法一：

1、遞歸遍歷--用全局變量/靜態局部變量來記錄節點個數

2、遞歸遍歷--函數外定義一個局部變量記錄節點個數，傳址給函數

//方法二：分而治之的思路

intBinaryTreeLeafSize(BTNode*root)

if(root==NULL)//1.先判斷當前訪問的節點是否為空

return0;

//2.當前節點不為空，它的左右孩子都為空，說明該節點是葉子節點

if(root-left==NULLroot-right==NULL)

return1;

//3.當前節點不為空，左右孩子不都為空，則繼續往下遍歷

returnBinaryTreeLeafSize(root-left)

+BinaryTreeLeafSize(root-right);

}

3.3二叉樹第k層節點個數

核心思路：

求當前樹第k層的節點個數=求左子樹第k-1層的節點個數+求右子樹第k-1層的節點個數比如：求當前樹（A）第2層的節點個數=求左子樹（B）第1層的節點個數+求右子樹（C）第1層的節點個數=1+1=2

如何知道這個節點是不是第k層的？我自己復習時是用的這個思路來寫，感覺容易理解些：

求二叉樹第k層的節點個數，我們從根節點開始往下遍歷（我在代碼中是根左右的順序），每遍歷一次k減1一次，當k==1時，說明我們遍歷到了第k層，我們此時訪問該層的節點，如果它不為空，則二叉樹第k層的節點個數就要+1。

//二叉樹第k層節點個數

intBinaryTreeLevelKSize(BTNode*root,intk)

if(root==NULL)//1.先判斷當前訪問的節點是否為空

return0;

if(k==1)//2.當前節點不為空，而k已經減到1了，說明遍歷到了第k層，說明該節點是第k層的

return1;

//3.還沒有遍歷到第k層，我們就繼續往下遍歷

returnBinaryTreeLevelKSize(root-left,k-1)

+BinaryTreeLevelKSize(root-right,k-1);

3.4二叉樹的深度(高度)

核心思想：

當前樹的深度=Max(左子樹的深度，右子樹的深度)+1

root是空節點：height(root)=0root是非空節點：height(root)=max(height(root-left),height(root-right))+1

//二叉樹的深度(高度)

intBinaryTreeDepth(BTNode*root)

//1.先判斷當前樹的根節點是否為空

if(root==NULL)

return0;

//2.當前樹的根節點不為空，分別計算其左右子樹的深度

intleftDepth=BinaryTreeDepth(root-left);

intrightDepth=BinaryTreeDepth(root-right);

//3.比較當前樹左右子樹的深度，最大的那個+1就是當前樹的深度

returnleftDepthrightDepthleftDepth+1:rightDepth+1;

有一道OJ題考到了該算法，鏈接如下：二叉樹的最大深度

3.5二叉樹查找值為x的節點

核心思路：

先判斷是不是當前節點，是就返回，不是就先去該節點的左子樹找，找到了就返回，左子樹沒找到，再去該節點的右子樹找。

//二叉樹查找值為x的節點，若有則返回該節點的地址，若沒有則返回NULL

BTNode*BinaryTreeFind(BTNode*root,BTDataTypex)

if(root==NULL)//1.先判斷當前訪問的節點是否為空

returnNULL;

if(root-data==x)//2.判斷要找的x值節點是不是當前節點

returnroot;

//3.不是當前節點，則繼續去該節點的左子樹中找

BTNode*ret=BinaryTreeFind(root-left,x);

if(ret!=NULL)

returnret;//找到了返回地址

//3.還沒找到，再繼續去該節點的右子樹中找

ret=BinaryTreeFind(root-right,x);

if(ret!=NULL)

returnret;//找到了返回地址

//4.當前節點及其左右子樹中都沒找到，返回NULL

returnNULL;

}

3.6總結注意

二叉樹相關的算法，如果用的是遞歸遍歷，且代碼中需要一個變量在整個遞歸過程中去記錄什么信息，一定要注意，不要把這個變量直接定義成了局部變量。（因為每次遞歸調用，都會建立一個棧幀，各棧幀中的局部變量是彼此獨立的）

所以需要下面這樣做：

1、遞歸遍歷用全局變量/靜態局部變量來記錄節點個數

2、遞歸遍歷函數外定義一個局部變量記錄節點個數，傳址給函數

四、二叉樹的創建和銷毀

4.1通過前序遍歷的字符串來構建二叉樹

//通過前序遍歷的字符串數組arr"ABD##E#H##CF##G##"構建二叉樹

BTNode*BinaryTreeCreate(BTDataType*arr,intsize,int*pi);

4.2二叉樹銷毀

//二叉樹銷毀

//一級指針(頭節點指針)，形參是實參的一份拷貝，函數內改變形參的值，無法改變外部實參的值

//所以我們需要在函數外置頭節點指針為NULL

voidBinaryTreeDestroy(BTNode*root)

//不建議使用前中序遍歷銷毀，如果節點先被銷毀，就變成隨機值了，不知道它的左右子樹位置了

//所以我們采用后序遍歷銷毀

if(root)

BinaryTreeDestroy(root-left);

BinaryTreeDestroy(root-right);

free(root);

intmain()

//創建一顆鏈式二叉樹

BTNode*root=CreatBinaryTree();

//銷毀二叉樹

BinaryTreeDestroy(root);

//頭節點指針置NULL

root=NULL;

return0;

}

4.3判斷二叉樹是否是完全二叉樹

核心思路：

層序遍歷時，把空節點也入隊列

完全二叉樹，「非空節點」是連續的，則「空節點」是連續的。非完全二叉樹，「非空節點」不是連續的，則「空節點」不是連續的。

所以在出隊時，判斷一下，出到第一個「空節點」時，跳出循環；

在下面重新寫一個循環繼續出隊，并檢查出隊元素：

如果「第一個空節點」后面的全是「空節點」，說明是完全二叉樹如果「第一