建站
咨詢
售后
建站咨詢
新聞中心
目錄
定義
滿二叉樹
完全二叉樹
性質(zhì)
應(yīng)用
計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)
計(jì)算葉子結(jié)點(diǎn)的個(gè)數(shù)
第?k 層結(jié)點(diǎn)的個(gè)數(shù)
查找值為x的節(jié)點(diǎn)
遍歷
前序遍歷
中序遍歷
后序遍歷
層序遍歷
判斷是否為完全二叉樹
定義
🦄二叉樹是由樹發(fā)展過來的，即度大為2的樹，且子樹有左右之分，可以這么理解，二叉樹是空結(jié)點(diǎn)跟左右子樹的結(jié)合體。
🦄下面這張圖可能更好理解一點(diǎn)，任何二叉樹都是下列幾種情況復(fù)合而成的。因此只要這個(gè)樹的度超過?2?，那么它就不是二叉樹。
🦄滿二叉樹是一種特殊的二叉樹，即每一層結(jié)點(diǎn)都到達(dá)大值。舉個(gè)簡單的例子，假設(shè)這個(gè)二叉樹根結(jié)點(diǎn)在?1?層且一共有?i?層，若結(jié)點(diǎn)總數(shù)為(2^i)?-1?個(gè)那么這個(gè)二叉樹就是滿二叉樹。
🦄可以說滿二叉樹也是一種特殊的完全二叉樹，完全二叉樹的底層的結(jié)點(diǎn)的排序從左到右都是連續(xù)的。若假設(shè)下面這張圖里的F結(jié)點(diǎn)還有一個(gè)左結(jié)點(diǎn)，那么這個(gè)二叉樹就不是完全二叉樹了。
應(yīng)用1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有?2 ^ (i - 1)?個(gè)結(jié)點(diǎn)。
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的大結(jié)點(diǎn)數(shù)是(2 ^ h) - 1。
3. 對(duì)任何一棵二叉樹, 如果度為?0?其葉結(jié)點(diǎn)個(gè)數(shù)為?n0?, 度為?2?的分支結(jié)點(diǎn)個(gè)數(shù)為?n2?,則有??n0＝ n2＋1?。
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為?1?，具有?n?個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h = log （n +?1）?。(ps： 是?log?以2為底，n+1?為對(duì)數(shù))
5. 對(duì)于具有?n?個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從?0?開始編號(hào)，則對(duì)于序號(hào)為?i?的結(jié)點(diǎn)有：
1. 若?i>0?，i?位置節(jié)點(diǎn)的雙親為：( i - 1 ) / 2?。
2. 若?2i + 1< n?，左孩子為：2i+1?，2i + 1 >= n否則無左孩子。
3. 若2i + 2< n，右孩子為：2i + 2，2i + 2 >= n否則無右孩子。
🦄與堆不同，二叉樹是多個(gè)結(jié)點(diǎn)鏈接起來的鏈?zhǔn)浇Y(jié)構(gòu)，因此對(duì)應(yīng)其特性，每一個(gè)根節(jié)點(diǎn)都指向左右兩個(gè)結(jié)點(diǎn)。
typedef int BTdatatype;
typedef struct BinaryTreeNode
{
BTdatatype data; //數(shù)據(jù)
struct BinaryTreeNode* left; //左結(jié)點(diǎn)
struct BinaryTreeNode* right; //右結(jié)點(diǎn)
}BTNode;計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)🦄而這里二叉樹的實(shí)現(xiàn)主要依靠的是遞歸，為的便是能夠在訪問完一個(gè)子樹后還能返回到它原來的根結(jié)點(diǎn)。
🦄這里開始遞歸就初見雛形，需要一次次遞歸遍歷整個(gè)二叉樹來計(jì)算結(jié)點(diǎn)個(gè)數(shù)，通過返回值的方式將數(shù)值統(tǒng)計(jì)起來。(若使用全局變量，在多次調(diào)用該函數(shù)的時(shí)候就會(huì)出現(xiàn)全局變量未初始化的情況而導(dǎo)致結(jié)果出錯(cuò))
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0; //遇到空結(jié)點(diǎn)就返回0（代表0個(gè)結(jié)點(diǎn)）
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; //左右子樹結(jié)點(diǎn)加上自己的總個(gè)數(shù)
}🦄這題跟上一題類似，但還需要加上一個(gè)條件篩選葉子結(jié)點(diǎn)。
// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL) //判斷是否為葉子結(jié)點(diǎn)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); //兩邊葉子結(jié)點(diǎn)的個(gè)數(shù)
}🦄這題的關(guān)鍵在于對(duì)?k?層的檢索，既要找到?k?層的結(jié)點(diǎn)又要在?k?層前遇到空返回，則需要兩個(gè)判斷。舉個(gè)例子而言，根節(jié)點(diǎn)距離?k?層的長度為?k-1?，即第?2?層的結(jié)點(diǎn)距離?k?層的長度為?k-2?，因此每次進(jìn)一層的時(shí)候就把?k--?當(dāng)?k==1?的時(shí)候該結(jié)點(diǎn)就是?k?層的結(jié)點(diǎn)，因此只需要統(tǒng)計(jì)這些結(jié)點(diǎn)的個(gè)數(shù)就可以了。
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL) //空結(jié)點(diǎn)不計(jì)數(shù)
{
return 0;
}
if (k == 1 && root != NULL) //到k層且結(jié)點(diǎn)不為空則計(jì)數(shù)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); //統(tǒng)合數(shù)量
}🦄這題要注意的是對(duì)結(jié)點(diǎn)的值的返回，我們都知道一次的結(jié)果并不一定會(huì)影響到最終返回的結(jié)果，因此處理好一找到點(diǎn)就立刻返回的方法非常重要。這里就通過對(duì)返回值的判斷，只有找到目標(biāo)結(jié)點(diǎn)時(shí)才會(huì)直接層層返回。
// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTdatatype x)
{
if (root == NULL)
{
return 0;
}
if (root->data == x) //找到值為x的結(jié)點(diǎn)返回
{
return root;
}
BTNode* ret1 = BinaryTreeFind(root->left, x); //往左找x
if (ret1) //有返回值則繼續(xù)返回
{
return ret1;
}
BTNode* ret2 = BinaryTreeFind(root->right, x); //往右找x
if(ret2) //有返回值繼續(xù)返回
{
return ret2;
}
}前序遍歷🦄遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。根據(jù)規(guī)則的不同，二叉樹的遍歷可以分作四種，分別是前序、中序、后序以及層序遍歷。
傳送門：144.二叉樹的前序遍歷
🦄口訣：根 左 右，即先訪問根結(jié)點(diǎn)后再依次訪問左右結(jié)點(diǎn)，倒也像一個(gè)人從根結(jié)點(diǎn)繞著外圍跑遍了整個(gè)二叉樹。
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL) //為空返回
{
printf("NULL ");
return 0;
}
printf("%d ", root->data); //先打印根節(jié)點(diǎn)的數(shù)據(jù)
BinaryTreePrevOrder(root->left); //訪問左子樹
BinaryTreePrevOrder(root->right); //訪問右子樹
}傳送門：94.二叉樹的中序遍歷
🦄口訣：左 根 右，中序遍歷則需要先訪問左子樹之后再訪問根結(jié)點(diǎn)，最后才是右子樹。簡單地看就是從左到右依次把結(jié)點(diǎn)拿下來并訪問。
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL) //為空返回
{
printf("NULL ");
return 0;
}
BinaryTreeInOrder(root->left); //先訪問左子樹
printf("%d ", root->data); //打印根結(jié)點(diǎn)
BinaryTreeInOrder(root->right); //再訪問右子樹
}傳送門：145.二叉樹的后序遍歷
🦄口訣：左 右 根?，后序遍歷則是先遍歷兩個(gè)子樹之后才是訪問根結(jié)點(diǎn)。即要訪問這個(gè)結(jié)點(diǎn)它的左右子樹都必須先遍歷一遍。可以看成一個(gè)結(jié)點(diǎn)必須是葉結(jié)點(diǎn)才能對(duì)其訪問，若非葉結(jié)點(diǎn)就先訪問并“刪除”左右結(jié)點(diǎn)后讓原結(jié)點(diǎn)變成葉結(jié)點(diǎn)之后再進(jìn)行訪問。
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL) //為空返回
{
printf("NULL ");
return 0;
}
BinaryTreePostOrder(root->left); //先遍歷左子樹
BinaryTreePostOrder(root->right); //再遍歷右子樹
printf("%d ", root->data); //最后打印根結(jié)點(diǎn)
}傳送門：102. 二叉樹的層序遍歷
🦄正如其名，層序遍歷就是以層為單位進(jìn)行遍歷。若要實(shí)現(xiàn)層序遍歷的話，所需的思想與上面的遍歷就完全不同。因?yàn)橹暗谋闅v是以深度優(yōu)先進(jìn)行的，而層序遍歷需要的是廣度優(yōu)先的遍歷。
🦄為了實(shí)現(xiàn)依層遍歷的功能，我們需要使用隊(duì)列來輔助實(shí)現(xiàn)。第一次傳入的是根結(jié)點(diǎn)，每次訪問完根結(jié)點(diǎn)之后把隊(duì)頭刪除，再把隊(duì)頭對(duì)應(yīng)的左右子樹對(duì)應(yīng)的指針傳入隊(duì)列之中，根據(jù)隊(duì)列先進(jìn)先出的性質(zhì)，所以后傳入的結(jié)點(diǎn)就會(huì)較后地被訪問。
typedef BTNode* Qdatatype;
typedef struct Qnode
{
Qdatatype data; //數(shù)據(jù)
struct Queue* next; //指向下個(gè)結(jié)點(diǎn)
}Qnode;
typedef struct Queue
{
Qnode* head; //隊(duì)列的頭
Qnode* tail; //隊(duì)列的尾
int size; //大小
}Queue;
void Queueinit(Queue* p)
{
p->head = NULL; //頭尾結(jié)點(diǎn)制空
p->tail = NULL;
p->size = 0; //數(shù)據(jù)量為0
}
bool QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL || p->tail == NULL; //二者一個(gè)為空則隊(duì)列為空
}
void Queuepush(Queue* p, Qdatatype x)
{
assert(p); //斷言
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode)); //開辟新結(jié)點(diǎn)
if (newnode == NULL) //開辟失敗返回
{
perror(malloc);
exit(-1);
}
newnode->data = x; //賦值
newnode->next = NULL;
if (p->head == NULL) //隊(duì)列為空的情況
{
p->head = p->tail = newnode;
}
else
{
p->tail->next = newnode; //鏈接
p->tail = newnode;
}
p->size++; //對(duì)size進(jìn)行處理
}
void Queuepop(Queue* p)
{
assert(p); //斷言p不為空
assert(!QueueEmpty(p)); //斷言隊(duì)列不為空
Qnode* next = p->head->next; //存儲(chǔ)下一結(jié)點(diǎn)
free(p->head); //釋放當(dāng)先頭結(jié)點(diǎn)
p->head = next; //下一結(jié)點(diǎn)變成頭結(jié)點(diǎn)
p->size--; //對(duì)size進(jìn)行處理
}
Qdatatype Queuefront(Queue* p)
{
assert(p);
assert(!QueueEmpty(p)); //斷言不為空
return p->head->data; //頭結(jié)點(diǎn)存儲(chǔ)的就是隊(duì)頭的數(shù)據(jù)
}
void QueueDestroy(Queue* p)
{
assert(p);
Qnode* cur = p->head;
while (cur)
{
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->head = p->tail = NULL; //頭尾結(jié)點(diǎn)制空
p->size = 0; //大小歸0
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
assert(root);
Queue q;
Queueinit(&q); //構(gòu)建隊(duì)列
Queuepush(&q, root); //根結(jié)點(diǎn)入隊(duì)
while (!QueueEmpty(&q)) //隊(duì)列為空遍歷完成
{
BTNode* front = Queuefront(&q); //取隊(duì)頭
printf("%d ",front->data);
Queuepop(&q); //刪隊(duì)頭
if (front->left)
{
Queuepush(&q, front->left); //插入隊(duì)頭的左結(jié)點(diǎn)
}
if (front->right)
{
Queuepush(&q, front->right); //插入隊(duì)頭的右結(jié)點(diǎn)
}
}
printf("\n");
QueueDestroy(&q); //銷毀隊(duì)列
}🦄這個(gè)問題是在層序遍歷的基礎(chǔ)之上實(shí)現(xiàn)的，我們知道判斷是否為完全二叉樹的關(guān)鍵在于最后一層前都為滿，最后一層的結(jié)點(diǎn)必須連續(xù)。因此我們可以這樣想，只要層序遍歷直到遇到空指針就停止，之后判斷隊(duì)列里面還有沒有非空結(jié)點(diǎn)。若隊(duì)列里都是空指針則說明這棵樹為完全二叉樹。
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{
assert(root);
Queue q;
Queueinit(&q);
Queuepush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = Queuefront(&q); //取隊(duì)頭
if (front == NULL) //隊(duì)頭不為空則繼續(xù)循環(huán)
{
break;
}
Queuepop(&q);
Queuepush(&q, front->left); //插入左右結(jié)點(diǎn)
Queuepush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = Queuefront(&q);
if (front != NULL) //只要判斷隊(duì)列之后還有沒有非空結(jié)點(diǎn)
{
QueueDestroy(&q);
return -1;
}
Queuepop(&q);
}
QueueDestroy(&q);
return 1;
}🦙那么，今天二叉樹的基本操作與遍歷就告一段落，如果這篇文章對(duì)你有幫助的話，不妨留下三連支持以下博主，謝謝大家!!!
? ? ? ? ? ? ??
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
新聞名稱：【數(shù)據(jù)結(jié)構(gòu)】二叉樹的基本操作與遍歷（C語言）-創(chuàng)新互聯(lián)
本文鏈接：http://www.ef60e0e.cn/article/pdieo.html
