一個标題哼哼啊啊啊啊啊啊
- 樹是什麼
- 樹的相關概念
- 樹的表示
- 二叉樹
- 一些特殊的二叉樹
- 二叉樹的性質
- 用性質來做點題目吧
- 二叉樹的順序結構
- 堆
- 堆的實作
- 堆的插入
- 堆的删除
- 堆排序
- topK問題
- 二叉樹的鍊式結構
- 你以為是增删查改吧？不，是周遊！
- 前序、中序以及後序周遊
- 層序周遊
- 劈裡啪啦吓人的題目
- 樹的節點個數
- 樹的葉子節點個數
- 第k層的節點個數
- 二叉樹銷毀
- 二叉樹的最大深度
- 二叉樹尋找值為x的節點
- 單值二叉樹
- 相同的樹
- 對稱二叉樹
- 反轉二叉樹
- 二叉樹的前序周遊
- 另一棵樹的子樹
- 判斷二叉樹是不是完全二叉樹
- 二叉樹周遊
- 最後
稍微介紹一下自己吧:
雙非非科班（其實也沾點邊）大一菜鳥，自學C++中，是以不要問咱太複雜的問題啊。
寫部落格都是記錄學習，也是督促自己不要摸魚，沒啥想法，學到哪寫到哪，有問題，指，都可以指。
沒了。
菜雞大學生門前有兩棵樹，一棵是高數，一棵是二叉樹。
上學期在高強度預習下，大學生沒挂在高數上面，真是萬幸。
這學期我看懸。
總之在菜雞大學生的講解下，大家都不會挂在二叉樹上面的！
我們開始吧！
樹是什麼
樹（左一）
毫無疑問這個是樹，但不是我們要講的樹。
我們要講的樹是這個：
由于它長得像一棵倒挂的樹是以就給它起名叫樹。
注意，子樹是不相交的，每一個節點隻有一個父節點。
違反上述規則的都不是樹。
點名批評這倆。
[資料結構初階收尾篇]一篇文章帶你把二叉樹撕成二叉樹條
樹的相關概念
- 根結點：簡單來說最頂上的就是根節點，根節點沒有前驅節點，圖示根節點為A。
- 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的度為6。
- 葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點。
- 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點。
- 孩子節點或子節點：父節點概念反過來就是孩子節點，如圖，B是A的孩子節點。
- 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4。
樹的表示
先簡單了解一下孩子兄弟表示法吧，畢竟我們主要講的是二叉樹，樹啥的，目前…不重要。
typedef int DataType;
struct Node
{
struct Node* firstChild; // 第一個孩子結點
struct Node* NextBrother; // 指向其下一個兄弟結點
DataType data; // 結點中的資料域
}; 實際表示是這樣的。
這樣可以既兼顧值和節點之間的關系，還是很不錯的。
二叉樹
啥是二叉樹，根據樸素的按照名字去推斷的方法，二叉樹有兩個叉。
再說明白一點，就是一個節點最多有兩個子節點。
還有一個特點，左右節點是有順序的。比如上圖左邊的二叉樹，将4，5兩個節點換一個位置，就會變成一個新的二叉樹。
一些特殊的二叉樹
- 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。
- 完全二叉樹：對于深度為K的有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編号從1至n的結點一一對應時稱之為完全二叉樹。
滿二叉樹是一種特殊的完全二叉樹。
啥意思？
先放一張滿二叉樹的圖檔：
圖很好懂，用我的話說就是除了最後一層全是葉子節點其他所有節點都是度為二的節點。
完全二叉樹呢？
我們先給這個滿二叉樹标個号。
如果一個二叉樹有6個節點，且分别對應節點1，2，3，4，5，6就是完全二叉樹。
其餘任何情況都不是。
簡單來說隻要中間不斷就是完全二叉樹了。
二叉樹的性質
這三條都邦邦重要，做題十分管用，務必要記住。
用性質來做點題目吧
-
某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
A 不存在這樣的二叉樹
B 200
C 198
D 199
我們根據第三條結論，可以直接算出n0=200。
-
下列資料結構中，不适合采用順序存儲結構的是（ ）
A 非完全二叉樹
B 堆
C 隊列
D 棧
A. 原因我們下面講。
-
在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A n
B n+1
C n-1
D n/2
我們假設n2=x，n0就是x+1，n2+n0=2x+1由于完全二叉樹，n1的個數不是1就是0，又因為2x+1肯定是奇數，是以n1=1，2x+1+1=2n，就可以算出n0=n了，選A。
-
一棵完全二叉樹的節點數位為531個，那麼這棵樹的高度為（ ）
A 11
B 10
C 8
D 12
2^9-1<531< 2^10-1高度是10，選B。
-
一個具有767個節點的完全二叉樹，其葉子節點個數為（）
A 383
B 384
C 385
D 386
和第三題一樣的思路，選B。
二叉樹的順序結構
假設我們有一棵完全二叉樹，
康康這完美的序号！這麼漂亮的結構不用數組說不過去吧！
我們用數組的下标形式重新标一下：
amazing啊，我們可以發現下标和它們的父母孩子都是有關系的。
- 一個節點的兩個孩子等于節點下标*2+1和下标*2+2.
- 節點的父親等于（孩子-1）/2.
非完全二叉樹也可以這麼搞，但肯定沒有完全二叉樹實用不是嗎？
那麼我們順勢引入堆的概念。
堆
堆的性質：
- 堆中某個節點的值總是不大于或不小于其父節點的值；
- 堆總是一棵完全二叉樹。
按照堆的定義可以把堆分成大堆或者小堆。
- 大堆：堆中父親都大于等于孩子。
- 小堆：堆中父親都小于等于孩子。
堆的實作
既然是數組就好操作了。
先把正常操作整了：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
// 堆的初始化
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
//堆的銷毀
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->size = php->capacity = 0;
}
//交換函數
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
//堆的列印
void HeapPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
//判斷堆是否為空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//傳回堆的大小
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
//傳回堆頂資料
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
} 堆的插入
為了保證堆的結構不被破壞，我們選擇講資料先插入到最後然後慢慢向上調整的方法，如圖：
- 先将資料放在最後。
- 将資料和父節點對比根據堆的類型判斷是否要交換。
- 如果是大堆，就是比父親大，交換。
- 如果是小堆，就是比父親小，交換。
- 直到交換結束，此時數組依然是個堆。
void AdjustUp(HPDataType* a, size_t child)
{
size_t 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;
}
}
}
// 插入x以後，保持他依舊是(大/小)堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
// 向上調整，控制保持是一個(大/小)堆
AdjustUp(php->a, php->size - 1);
} 堆的删除
一般我們删除是删除堆頂的資料，但是，如果我們把堆頂資料删掉了，誰是堆頂呢？堆的結構是不是就亂了呢？
此時有一個天才般的方法，先把堆頂的資料和最後一個資料交換，删掉最後一個資料，然後将堆頂慢慢往下調整。
看圖：
- 先将堆頂和最後一個資料交換。
- 删除最後一個資料
- 将資料和子節點對比根據堆的類型判斷是否要交換。
- 如果是大堆，就是和較大的子節點比，如果子節點大，交換。
- 如果是小堆，就是和較小的子節點比，如果子節點小，交換。
- 直到交換結束，此時數組依然是個堆。
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = root*2+1;
while (child < size)
{
// 1、選出左右孩子中小的那個
if (child + 1 < size && a[child] > a[child + 1])
++child;
// 2、如果孩子小于父親，則交換，并繼續往下調整
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 删除堆頂的資料。(最小/最大)
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
AdjustDown(php->a, php->size, 0);
} 堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種資料結構所設計的一種排序算法，它是選擇排序的一種。
它是通過堆來進行選擇資料。需要注意的是排升序要建大堆，排降序建小堆。
我們先不管這些，我們可以先用上面的代碼寫一個粗糙的堆排序試試看。
由于大/小堆堆頂的資料是堆裡面最大/小的資料，我們隻要不停出堆頂的資料放入數組就可以保證數組有序了。
思路：
- 建堆。
- 在隊裡一個一個插入資料，使之還是一個堆。
- 出堆頂的資料，然後向下調整。
- 繼續出堆頂的資料直到堆為空。
void HeapSort1(int* a, int size)
{
HP hp;
HeapInit(&hp);
for (int i = 0; i < size; i++)
{
HeapPush(&hp, a[i]);
}
int j = 0;
while (!HeapEmpty(&hp))
{
a[j++] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestroy(&hp);
} 這個方法不錯是吧？可不可以優化呢？
由于我們額外建立了一個堆導緻有O（n）的空間複雜度，我們是不是可以考慮直接在數組裡面建堆呢？
可以。
再次強調： 排升序要建大堆，排降序建小堆。
如果是建小堆的話第一個就已經是最小的了，後面的資料還需要重建立堆，那麼堆排序的意義就不存在了。
思路：
- 假設要排的資料有n個。
- 建大堆找到最大的資料和最後一個資料交換。
- 堆頂資料向下調整，此時新的堆頂資料是n-1個資料裡面最大的數。
- 堆頂和第n-1個資料交換。
- 直到隻剩一個資料。
我們先不急着建堆，先把後面的代碼寫出來。
for (size_t i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
} 順便畫個不太好了解的圖。
然後在嘗試建堆康康。
我們可以采取向上建堆和向下建堆兩種建堆方式。
向上建堆就類似于一個個向數組裡面插入資料。
向下建堆從倒數第一個非葉子節點開始向下調整。
//建大堆
// 向上建堆
for (int i = 0; i < n; i++)
{
AdjustUp(a, i);
}
//向下建堆
for (int i = (n-1-1)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
} 既然有兩種建堆方式我們就要比較一下效率了。
我們假設是滿二叉樹：
顯然向下建堆效率更高。
将代碼整合一下：
void HeapSort(int* a, int n)
{
//向下建堆
for (int i = (n-1-1)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
for (size_t i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
} topK問題
即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大。
如果資料量比較小的話我們可以使用排序，但是如果資料很大呢？
這個時候我們可以用堆解決：
- 用資料集合中前K個元素來建堆
- 前k個最大的元素，則建小堆。
- 前k個最小的元素，則建大堆。
- 用剩餘的N-K個元素依次與堆頂元素來比較，決定是否替換：
- 前k個最大的元素，如果堆頂元素比比較元素小，就替換。
- 前k個最小的元素，如果堆頂元素比比較元素大，就替換。
- 将剩餘N-K個元素依次與堆頂元素比完之後，堆中剩餘的K個元素就是所求的前K個最小或者最大的元素。
代碼：
void PrintTopK(int* a, int n, int k)
{
int* kminHeap = (int*)malloc(sizeof(int) * k);
assert(kminHeap);
for (int i = 0; i < k; ++i)
{
kminHeap[i] = a[i];
}
// 建小堆
for (int j = (k - 1 - 1) / 2; j >= 0; --j)
{
AdjustDown(kminHeap, k, j);
}
// 2. 将剩餘n-k個元素依次與堆頂元素交換，不滿則則替換
for (int i = k; i < n; ++i)
{
if (a[i] > kminHeap[0])
{
kminHeap[0] = a[i];
AdjustDown(kminHeap, k, 0);
}
}
for (int j = 0; j < k; ++j)
{
printf("%d ", kminHeap[j]);
}
printf("\n");
free(kminHeap);
} 注：時間複雜度：O（K+logK*（N-K））） 空間複雜度：O（K）。
如果N非常大，K很小，時間複雜度就可以看作O（N）。
二叉樹的鍊式結構
我們可以考慮用連結清單來存儲二叉樹，如圖：
也就是說每個節點包含三個部分：
- 該節點儲存的資料。
- 指向左孩子節點的指針。
- 指向右孩子節點的指針。
typedef int BTDataType;
typedef struct BinaryTreeNode {
struct BinaryTreeNode* left; //指向左孩子的指針
struct BinaryTreeNode* right; //指向右孩子的指針
BTDataType data; //資料
}BTNode; 你以為是增删查改吧？不，是周遊！
二叉樹增删查改沒啥價值，我的評價是不如線性表。
題目也不會出增删查改。
總之題目出啥我學啥（驕傲）。
二叉樹的周遊主要可以分為前序周遊，中序周遊，後序周遊和層序周遊。
我們一個個來講。
前序、中序以及後序周遊
- 前序周遊的順序是：根節點，左子樹，右子樹。
- 中序周遊的順序是：左子樹，根節點，右子樹。
- 後序周遊的順序是：左子樹，右子樹，根節點。
通過觀察我們發現所謂的前中後其實就是根節點在順序中的位置，
前序就是根在前，中序就是根在中間，後序就是根在最後。
明白了思想之後，我們就可以考慮寫代碼了。
在周遊的時候我們考慮使用遞歸的方法。
把每一個問題拆成更小的問題，直到我們可以輕松解決。
- 對于二叉樹來說，什麼是最小的問題。
- 隻要遞歸到NULL一切的問題都不是問題。
前中後序周遊唯一的差別就是列印根的時機，是以代碼一并放出來：
//前序周遊
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return NULL;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
//中序周遊
void InOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//後序周遊
void PostOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
} 也許有好朋友沒看懂。
這個時候就需要畫圖了，我們以前序為例：
遞歸題目看不懂的話就多畫畫遞歸展開圖，會有奇效。
層序周遊
啥是層序周遊捏？
就是一層一層周遊。
以上圖為例，層序周遊結果是：A，B，C，D，E，F。
解題思路：
- 根節點先入隊。
- 開始循環：
- 儲存隊頭節點位址front。
- 出隊頭節點。
- front如果有子節點，則入隊。
- 隊為空則結束循環。
//層序周遊
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestory(&q);
} 劈裡啪啦吓人的題目
做點題玩玩吧，會講一些大緻思路或者直接擺爛放代碼。
遞歸這個東西很玄，要是繞不過來就畫圖吧。
樹的節點個數
樹的節點個數等于左子樹+右子樹+1.
空節點直接傳回0.
//樹的節點個數
int BTreeSize(BTNode* root) {
return root == NULL ? 0 :
BTreeSize(root->left)
+ BTreeSize(root->right) + 1;
} 樹的葉子節點個數
還是把它分成左子樹和右子樹。
隻有左子樹和右子樹都是NULL是葉子節點。
//葉子節點個數
int BTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
} 第k層的節點個數
// 第k層的節點的個數，k >= 1
int BTreeKLevelSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeKLevelSize(root->left, k - 1)
+ BTreeKLevelSize(root->right, k - 1);
} 二叉樹銷毀
分治啊，分治。
累了，毀滅吧。
// 二叉樹銷毀
void BTreeDestory(BTNode* root)
{
if (root == NULL)
{
return;
}
BTreeDestory(root->left);
BTreeDestory(root->right);
free(root);
} 二叉樹的最大深度
左子樹的最大深度和右子樹的最大深度中最大的那一個。
int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return left>right?left+1:right+1;
} 二叉樹尋找值為x的節點
// 二叉樹查找值為x的結點
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
//return BTreeFind(root->right, x);
BTNode* ret2 = BTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
} 單值二叉樹
連結：965. 單值二叉樹 - 力扣（LeetCode）
如果二叉樹每個節點都具有相同的值，那麼該二叉樹就是_單值_二叉樹。
隻有給定的樹是單值二叉樹時，才傳回
true
；否則傳回
false
。
這道題是的情況比不是的情況要多很多，是以我們隻要在意不是的情況就行。
不是的情況很簡單：父節點和子節點不一樣。（子節點存在）
bool isUnivalTree(struct TreeNode* root){
if(root==NULL)
return true;
if(root->right&&root->val!=root->right->val)
return false;
if(root->left&&root->val!=root->left->val)
return false;
return isUnivalTree(root->left)&&isUnivalTree(root->right);
} 相同的樹
連結：100. 相同的樹 - 力扣（LeetCode）
給你兩棵二叉樹的根節點
p
和
q
，編寫一個函數來檢驗這兩棵樹是否相同。
如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。
- 如果倆節點都是空，肯定是相同的。
- 如果一個是空，一個不是，肯定不相同。
- 如果值不相等，肯定不是。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL&&q==NULL)
return true;
//此時兩個節點肯定都不為空
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(q->right,p->right);
} 對稱二叉樹
連結：101. 對稱二叉樹 - 力扣（LeetCode）
給你一個二叉樹的根節點
root
， 檢查它是否軸對稱。
什麼是對稱？
簡單來說，除了根節點，左子樹的左子樹等于右子樹的右子樹。
是以我們要先撇掉根節點再寫。
思路與上一題一緻。
bool _isSymmetric(struct TreeNode* p,struct TreeNode* q)
{
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return _isSymmetric(q->left,p->right)&&_isSymmetric(q->right,p->left);
}
bool isSymmetric(struct TreeNode* root){
if(root==NULL)
return true;
return _isSymmetric(root->left,root->right);
} 反轉二叉樹
連結：226. 翻轉二叉樹 - 力扣（LeetCode）
給你一棵二叉樹的根節點
root
，翻轉這棵二叉樹，并傳回其根節點。
也和上一題有點像，二叉樹的左節點和右節點互換就行，用分治就能換掉整棵樹。
struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
return NULL;
invertTree(root->left);
invertTree(root->right);
struct TreeNode* tmp=root->left;
root->left=root->right;
root->right=tmp;
return root;
} 二叉樹的前序周遊
之前講過了對吧，但是題目稍微變了一下。
連結：144. 二叉樹的前序周遊 - 力扣（LeetCode）
它要求你把值放到數組裡面了。
是以我們要先計算一下節點個數再去操作。
注意注釋部分的代碼。
int TreeSize(struct TreeNode* root)
{
if(root==NULL)
return 0;
return TreeSize(root->left)+TreeSize(root->right)+1;
}
void PreOrder(struct TreeNode* root, int* a,int* i)
{
if(root==NULL)
return ;
a[(*i)++]=root->val; //
PreOrder(root->left,a,i);
PreOrder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
int size=TreeSize(root);
int* arr=(int*)malloc(sizeof(int)*size);
int i=0;
PreOrder(root,arr,&i); //
*returnSize=size;
return arr;
} 另一棵樹的子樹
連結：572. 另一棵樹的子樹 - 力扣（LeetCode）
給你兩棵二叉樹 root 和 subRoot 。檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。如果存在，傳回 true ；否則，傳回 false 。
二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有後代節點。tree 也可以看做它自身的一棵子樹。
相同的樹promax版。
我們隻要康康它是不是有子樹和subroot相等就行。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL&&q==NULL)
return true;
if(p==NULL||q==NULL)
return false;
if(p->val!=q->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(q->right,p->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return NULL;
return isSameTree(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
} 判斷二叉樹是不是完全二叉樹
這題和層序周遊有關。
我們隻需要：
- 将層序周遊裡面的空節點也存進隊列。
- 出隊列時遇到空節點跳出循環。
- 檢查隊列裡面有無非空節點，有就不是完全二叉樹。
// 判斷二叉樹是否是完全二叉樹
bool BTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
// 空後面出到非空，那麼說明不是完全二叉樹
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
} 二叉樹周遊
連結：二叉樹周遊_牛客網
編一個程式，讀入使用者輸入的一串先序周遊字元串，根據此字元串建立一個二叉樹（以指針方式存儲）。 例如如下的先序周遊字元串： ABC##DE#G##F### 其中“#”表示的是空格，空格字元代表空樹。建立起此二叉樹以後，再對二叉樹進行中序周遊，輸出周遊結果。
前序周遊力扣版本的變種。
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BinaryCreate(char* s,int* i)
{
if(s[*i]=='#')
{
(*i)++;
return NULL;
}
BTNode* Node=(BTNode*)malloc(sizeof(BTNode));
Node->data=s[(*i)++];
Node->left=BinaryCreate(s, i);
Node->right=BinaryCreate(s, i);
return Node;
}
void InOrder(BTNode* root)
{
if(root==NULL)
return;
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
int main()
{
char arr[100];
scanf("%s",arr);
int len=strlen(arr);
int i=0;
BTNode* root=BinaryCreate(arr,&i);
InOrder(root);
return 0;
} 最後
下一篇就是C++篇了。