C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)詳解
1. 樹(shù)概念及結(jié)構(gòu)
1.1樹(shù)概念
樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù),也就是說(shuō)它是根朝上,而葉朝下的。
- 根結(jié)點(diǎn):根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
- 除根節(jié)點(diǎn)外,其余結(jié)點(diǎn)被分成是一棵結(jié)構(gòu)與樹(shù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū),可以有0個(gè)或多個(gè)后繼。
- 因此,樹(shù)是遞歸定義的。
- 節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度; 如上圖:A的為2
- 葉節(jié)點(diǎn):度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn); 如上圖:G、H、I節(jié)點(diǎn)為葉節(jié)點(diǎn)
- 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn):度不為0的節(jié)點(diǎn); 如上圖:B、D、C、E、F節(jié)點(diǎn)為分支節(jié)點(diǎn)
- 雙親節(jié)點(diǎn)或父節(jié)點(diǎn):若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn),則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn); 如上圖:A是B的父節(jié)點(diǎn)
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn); 如上圖:B是A的孩子節(jié)點(diǎn)
- 兄弟節(jié)點(diǎn):具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn); 如上圖:B、C是兄弟節(jié)點(diǎn)
- 樹(shù)的度:一棵樹(shù)中,最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度; 如上圖:樹(shù)的度為2
- 節(jié)點(diǎn)的層次:從根開(kāi)始定義起,根為第1層,根的子節(jié)點(diǎn)為第2層,以此類(lèi)推;
- 樹(shù)的高度或深度:樹(shù)中節(jié)點(diǎn)的最大層次; 如上圖:樹(shù)的高度為4
- 堂兄弟節(jié)點(diǎn):雙親在同一層的節(jié)點(diǎn)互為堂兄弟;如上圖:H、I互為兄弟節(jié)點(diǎn)
- 節(jié)點(diǎn)的祖先:從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn);如上圖:A是所有節(jié)點(diǎn)的祖先
- 子孫:以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如上圖:所有節(jié)點(diǎn)都是A的子孫
- 森林:由m棵互不相交的樹(shù)的集合稱(chēng)為森林;
1.2樹(shù)的表示
樹(shù)結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了,要存儲(chǔ)表示起來(lái)就比較麻煩了,實(shí)際中樹(shù)有很多種表示方式,如:雙親表示法,孩子表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。
typedef int DataType; struct Node { struct Node* firstChild1; struct Node* pNextBrother; DataType data; };
2. 二叉樹(shù)概念及結(jié)構(gòu)
2.1概念
一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
二叉樹(shù)的特點(diǎn):
- 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),即二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。
- 二叉樹(shù)的子樹(shù)有左右之分,其子樹(shù)的次序不能顛倒。
2.2數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù)
2.3特殊的二叉樹(shù)
滿(mǎn)二叉樹(shù):一個(gè)二叉樹(shù),如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹(shù)就是滿(mǎn)二叉樹(shù)。也就是說(shuō),如果一個(gè)二叉樹(shù)的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是(2^k) -1 ,則它就是滿(mǎn)二叉樹(shù)。
完全二叉樹(shù):完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的,有n個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿(mǎn)二叉樹(shù)是一種特殊的完全二叉樹(shù)。
2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
二叉樹(shù)一般可以使用兩種存儲(chǔ)結(jié)構(gòu),一種順序結(jié)構(gòu),一種鏈?zhǔn)浇Y(jié)構(gòu)。
2.4.1順序存儲(chǔ)
順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ),一般使用數(shù)組只適合表示完全二叉樹(shù),因?yàn)椴皇峭耆鏄?shù)會(huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來(lái)存儲(chǔ)。二叉樹(shù)順序存儲(chǔ)在物理上是一個(gè)數(shù)組,在邏輯上是一顆二叉樹(shù)。
2.4.2鏈?zhǔn)酱鎯?chǔ)
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指,用鏈表來(lái)表示一棵二叉樹(shù),即用鏈來(lái)指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成,數(shù)據(jù)域和左右指針域,左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈,當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈,后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹(shù)等會(huì)用到三叉鏈。
// 二叉鏈 struct BinaryTreeNode { struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子 struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子 BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域 } // 三叉鏈 struct BinaryTreeNode { struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親 struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子 struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子 BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域 };
2.5二叉樹(shù)的性質(zhì)
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹(shù)的第i層上最多有2^(i-1) 個(gè)結(jié)點(diǎn).
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h- 1.
- 對(duì)任何一棵二叉樹(shù), 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2+1
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度,h=Log2(n+1). (ps:Log2(n+1)是log以2為
- 底,n+1為對(duì)數(shù))
- 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù),如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào),則對(duì)于序號(hào)為i的結(jié)點(diǎn)有:
1. 若i>0,i位置節(jié)點(diǎn)的雙親序號(hào):(i-1)/2;i=0,i為根節(jié)點(diǎn)編號(hào),無(wú)雙親節(jié)點(diǎn)
2. 若2i+1<n,左孩子序號(hào):2i+1,2i+1>=n否則無(wú)左孩子
3. 若2i+2<n,右孩子序號(hào):2i+2,2i+2>=n否則無(wú)右孩子
3. 二叉樹(shù)順序結(jié)構(gòu)及概念
3.1二叉樹(shù)的順序結(jié)構(gòu)
普通的二叉樹(shù)是不適合用數(shù)組來(lái)存儲(chǔ)的,因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹(shù)更適合使用順序結(jié)構(gòu)存儲(chǔ)。現(xiàn)實(shí)中我們通常把堆(一種二叉樹(shù))使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ),需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事,一個(gè)是數(shù)據(jù)結(jié)構(gòu),一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。
3.2堆的概念及結(jié)構(gòu)
如果有一個(gè)關(guān)鍵碼的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中,并滿(mǎn)足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,則稱(chēng)為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆,根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆的性質(zhì):
- 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值;
- 堆總是一棵完全二叉樹(shù)。
3.3堆的實(shí)現(xiàn)
typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; void swap(int *a, int *b); void AdjustDown(int *a, int parent, int n); void AdjustUp(int *a, int child, int n); // 堆的構(gòu)建 void HeapCreate(Heap* hp, HPDataType* a, int n); // 堆的銷(xiāo)毀 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的刪除 void HeapPop(Heap* hp); // 取堆頂?shù)臄?shù)據(jù) HPDataType HeapTop(Heap* hp); // 堆的數(shù)據(jù)個(gè)數(shù) int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp); // 對(duì)數(shù)組進(jìn)行堆排序 void HeapSort(int* a, int n);
void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void AdjustUp(int *a, int child, int n) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void AdjustDown(int *a, int parent,int n) { int child = parent * 2 + 1; while ( child < n) { if (child + 1 < n && a[child]<a[child + 1]) { ++child; } if(a[child]>a[parent]) { swap(&a[child], &a[parent]); parent = child; child = (parent * 2) + 1; } else { break; } } } void HeapCreate(Heap* hp, HPDataType* a, int n) { assert(hp); hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n); if (hp->_a == NULL) { printf("malloc fail"); exit(-1); } for (int i = 0; i < n; ++i) { hp->_a[i] = a[i]; } hp->_size = hp->_capacity = n; for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(hp->_a,i, hp->_size); } } // 堆的銷(xiāo)毀 void HeapDestory(Heap* hp) { assert(hp); hp->_size = hp->_capacity = 0; free(hp); } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_size == hp->_capacity) { HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)* 2 * hp->_capacity); if (tmp == NULL) { printf("realloc fail"); exit(-1); } hp->_a = tmp; hp->_a[hp->_size] = x; ++hp->_size; hp->_capacity *= 2; } else { hp->_a[hp->_size] = x; ++hp->_size; } AdjustUp(hp->_a, hp->_size-1, hp->_size); } // 堆的刪除 void HeapPop(Heap* hp) { assert(hp); assert(hp->_size>0); swap(&hp->_a[hp->_size-1], &hp->_a[0]); --hp->_size; AdjustDown(hp->_a, 0, hp->_size); } // 取堆頂?shù)臄?shù)據(jù) HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->_size>0); return hp->_a[0]; } // 堆的數(shù)據(jù)個(gè)數(shù) int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 堆的判空 int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0 ? 1 : 0; for (int i = 0; i < 3; ++i)} // 對(duì)數(shù)組進(jìn)行堆排序 void HeapSort(int* a, int n) { assert(a); for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(a, i, n); } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); AdjustDown(a, 0, end); --end; } }
4. 二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)及實(shí)現(xiàn)
4.1二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的遍歷
所謂遍歷(Traversal)是指沿著某條搜索路線,依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴(lài)于具體的應(yīng)用問(wèn) 題。 遍歷是二叉樹(shù)上最重要的運(yùn)算之一,是二叉樹(shù)上進(jìn)行其它運(yùn)算之基礎(chǔ)。
前序/中序/后序的遞歸結(jié)構(gòu)遍歷:是根據(jù)訪問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名
NLR:前序遍歷(Preorder Traversal 亦稱(chēng)先序遍歷)——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。
LNR:中序遍歷(Inorder Traversal)——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中(間)。
LRN:后序遍歷(Postorder Traversal)——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。
由于被訪問(wèn)的結(jié)點(diǎn)必是某子樹(shù)的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹(shù)和根的右子樹(shù)。NLR、LNR和LRN分別又稱(chēng)為先根遍歷、中根遍歷和后根遍歷。
層序遍歷:除了先序遍歷、中序遍歷、后序遍歷外,還可以對(duì)二叉樹(shù)進(jìn)行層序遍歷。設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1,層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā),首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn),然后從左到右訪問(wèn)第2層上的節(jié)點(diǎn),接著是第三層的節(jié)點(diǎn),以此類(lèi)推,自上而下,自左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。
4.2二叉樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; typedef BTNode* QDataType; // 鏈?zhǔn)浇Y(jié)構(gòu):表示隊(duì)列 typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode; // 隊(duì)列的結(jié)構(gòu) typedef struct Queue { QNode* _front; QNode* _rear; }Queue; BTNode* CreateBTNode(BTDataType x); // 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù) BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi); // 二叉樹(shù)銷(xiāo)毀 void BinaryTreeDestory(BTNode** root); // 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root); // 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLeafSize(BTNode* root); // 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉樹(shù)查找值為x的節(jié)點(diǎn) BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root); // 二叉樹(shù)中序遍歷 void BinaryTreeInOrder(BTNode* root); // 二叉樹(shù)后序遍歷 void BinaryTreePostOrder(BTNode* root); // 初始化隊(duì)列 void QueueInit(Queue* q); // 隊(duì)尾入隊(duì)列 void QueuePush(Queue* q, QDataType data); // 隊(duì)頭出隊(duì)列 void QueuePop(Queue* q); // 獲取隊(duì)列頭部元素 QDataType QueueFront(Queue* q); // 獲取隊(duì)列隊(duì)尾元素 QDataType QueueBack(Queue* q); // 獲取隊(duì)列中有效元素個(gè)數(shù) int QueueSize(Queue* q); // 檢測(cè)隊(duì)列是否為空,如果為空返回非零結(jié)果,如果非空返回0 int QueueEmpty(Queue* q); // 銷(xiāo)毀隊(duì)列 void QueueDestroy(Queue* q); // 層序遍歷 void BinaryTreeLevelOrder(BTNode* root); // 判斷二叉樹(shù)是否是完全二叉樹(shù) int BinaryTreeComplete(BTNode* root);
// 初始化隊(duì)列 void QueueInit(Queue* q) { assert(q); q->_front = q->_rear = NULL; } // 隊(duì)尾入隊(duì)列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode *newnode = ((QNode*)malloc(sizeof(QNode))); newnode->_data = data; newnode->_next = NULL; if (q->_rear == NULL) { q->_front = q->_rear = newnode; } else { q->_rear->_next = newnode; //q->_rear = q->_rear->_next; q->_rear = newnode; } } // 隊(duì)頭出隊(duì)列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->_front == q->_rear) { free(q->_front); //free(q->_rear); q->_front = q->_rear = NULL; } else { QNode *cur = q->_front->_next; free(q->_front); q->_front = cur; } } // 獲取隊(duì)列頭部元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->_front->_data; } // 獲取隊(duì)列隊(duì)尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->_rear->_data; } // 獲取隊(duì)列中有效元素個(gè)數(shù) int QueueSize(Queue* q) { assert(q); int size = 0; QNode* cur = q->_front; while (cur) { ++size; cur = cur->_next; } return size; } // 檢測(cè)隊(duì)列是否為空,如果為空返回非零結(jié)果,如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->_front == NULL ? 1 : 0; } // 銷(xiāo)毀隊(duì)列 void QueueDestroy(Queue* q) { assert(q); QNode *cur = q->_front; while (cur) { QNode *next = cur->_next; free(cur); cur = next; } q->_front = q->_rear = NULL; } BTNode* CreateBTNode(BTDataType x) { BTNode *node = (BTNode*)malloc(sizeof(BTNode)); node->_data = x; node->_left = NULL; node->_right = NULL; return node; } // 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù) BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (a[*pi] == '#') { return NULL; } BTNode *node = (BTNode*)malloc(sizeof(BTNode)); node->_data = a[*pi]; ++*pi; node->_left = BinaryTreeCreate(a, n, pi); ++*pi; node->_right = BinaryTreeCreate(a, n, pi); return node; } // 二叉樹(shù)銷(xiāo)毀 void BinaryTreeDestory(BTNode** root) { if (*root != NULL) { if ((*root)->_left) // 有左孩子 BinaryTreeDestory(&(*root)->_left); // 銷(xiāo)毀左孩子子樹(shù) if ((*root)->_right) // 有右孩子 BinaryTreeDestory(&(*root)->_right); // 銷(xiāo)毀右孩子子樹(shù) free(*root); // 釋放根結(jié)點(diǎn) *root = NULL; // 空指針賦NULL } } // 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; } // 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->_left == NULL&&root->_right == NULL) { return 1; } return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right); } // 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1); } // 二叉樹(shù)查找值為x的節(jié)點(diǎn) BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->_data == x) { return root; } BTNode* ret=BinaryTreeFind(root->_left,x); if (ret != NULL) { return ret; } ret = BinaryTreeFind(root->_right, x); if (ret != NULL) { return ret; } return NULL; } // 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { //printf("NULL "); return; } printf("%c ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } // 二叉樹(shù)中序遍歷 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { //printf("NULL "); return; } BinaryTreeInOrder(root->_left); printf("%c ", root->_data); BinaryTreeInOrder(root->_right); } // 二叉樹(shù)后序遍歷 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { //printf("NULL "); return; } BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%c ", root->_data); } // 層序遍歷 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode *front = QueueFront(&q); QueuePop(&q); printf("%c ", front->_data); if (front->_left) { QueuePush(&q, front->_left); } if (front->_right) { QueuePush(&q, front->_right); } } } // 判斷二叉樹(shù)是否是完全二叉樹(shù) int BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode *front = QueueFront(&q); QueuePop(&q); if (front == NULL) { break; } printf("%s ", front->_data); if (front->_left) { QueuePush(&q, front->_left); } if (front->_right) { QueuePush(&q, front->_right); } } while (!QueueEmpty(&q)) { BTNode *front = QueueFront(&q); QueuePop(&q); if (front != NULL) { return 0; } } return 1; }
到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲
這篇文章主要為大家詳細(xì)介紹了基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06C語(yǔ)言?xún)?nèi)存分布與heap空間分別詳細(xì)講解
一個(gè)程序本質(zhì)上都是由 BSS 段、data段、text段三個(gè)組成的。這種概念在當(dāng)前的計(jì)算機(jī)程序設(shè)計(jì)中是非常重要的一個(gè)基本概念,并且在嵌入式系統(tǒng)的設(shè)計(jì)中也非常重要,牽涉到嵌入式系統(tǒng)執(zhí)行時(shí)的內(nèi)存大小分配,存儲(chǔ)單元占用空間大小的問(wèn)題2022-11-11C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-02-02C++學(xué)習(xí)之虛函數(shù)表與多態(tài)詳解
這篇文章主要為大家詳細(xì)介紹了C++中虛函數(shù)表與多態(tài)的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C++有一定的幫助,感興趣的小伙伴可以了解一下2023-03-03C++使用WideCharToMultiByte函數(shù)生成UTF-8編碼文件的方法
用來(lái)映射Unicode字符串的WideCharToMultiByte函數(shù)經(jīng)常被用來(lái)進(jìn)行UTF-8編碼的轉(zhuǎn)換,以下我們將看到C++使用WideCharToMultiByte函數(shù)生成UTF-8編碼文件的方法,首先先來(lái)對(duì)WideCharToMultiByte作一個(gè)詳細(xì)的了解:2016-06-06