寫在前面
二叉樹的幾乎所有實(shí)現(xiàn)都是依靠遞歸實(shí)現(xiàn)，遞歸的核心思路是把任何一個(gè)二叉樹看成根和左右子樹，而二叉樹遞歸的核心玩法就是把二叉樹的左右子樹再看成根，再找左右子樹，再看成根…
因此，解決二叉樹問題實(shí)際上要把二叉樹轉(zhuǎn)換成一個(gè)一個(gè)子樹的過程，找到一個(gè)一個(gè)的子樹再組裝起來就形成了二叉樹
二叉樹的創(chuàng)建
二叉樹建立的正統(tǒng)方法是利用遞歸，這里展示遞歸的一種寫法
BTNode* BuyNode(BTDataType a)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->data = a;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi]);
(*pi)++;
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
如果你對(duì)遞歸的認(rèn)識(shí)并不熟悉，下面我畫了一幅遞歸展開圖，更好解釋這其中的原理
(右子樹的部分過程由于空間原因不夠完全展開，但如果看懂左子樹的構(gòu)建過程，右子樹不難自己畫出)
這里注意的是，函數(shù)棧幀的創(chuàng)建并不是每一個(gè)都不一樣的位置，當(dāng)一個(gè)棧幀被銷毀后，另外一個(gè)棧幀創(chuàng)建就會(huì)在原來的位置，因此在計(jì)算空間復(fù)雜度的時(shí)候需要考慮這個(gè)問題：
空間是可以重復(fù)利用的，時(shí)間是一去不復(fù)返的
從這幅圖中，相信可以理解這段代碼的含義了
首先創(chuàng)建一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)去尋找左子樹進(jìn)入遞歸，而進(jìn)入遞歸后繼續(xù)尋找左子樹…直到遇到NULL截止，而遇到空后就尋找右子樹，右子樹也找到空后返回，這樣就構(gòu)建出了二叉樹中最小的一棵樹，而這棵樹會(huì)返回，作為根的左子樹，然后繼續(xù)進(jìn)入遞歸尋找根的右子樹…
由于是借助鏈表進(jìn)行實(shí)現(xiàn)的，因此我們可以理解為首先創(chuàng)建好根，而根的左右子樹用函數(shù)創(chuàng)建好后再連接起來…當(dāng)遇到#就返回，形成了一個(gè)一個(gè)的小樹，小樹最后組成大樹，就形成了二叉樹
二叉樹的遍歷
二叉樹的遍歷主要有前序遍歷，中序遍歷，后序遍歷，層序遍歷
前序遍歷
前序遍歷是指遍歷時(shí)先訪問根，再訪問左子樹，再訪問右子樹
代碼實(shí)現(xiàn)如下
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
下面依舊畫出它的遞歸展開圖
中序遍歷
中序遍歷是先訪問左子樹，再訪問根，最后訪問右子樹
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
遞歸圖和上面基本類似，就不做畫出了
后序遍歷
后序遍歷是先訪問左子樹，再訪問右子樹，最后訪問根
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
遞歸圖和上面基本類似，就不做畫出了
層序遍歷
層序遍歷指的是對(duì)二叉樹進(jìn)行一層一層的遍歷，每一層分別遍歷，這里借助隊(duì)列進(jìn)行遍歷，基本思路把根放到隊(duì)列中，當(dāng)某一個(gè)根要出隊(duì)列時(shí)，就令該根的左子樹和右子樹進(jìn)隊(duì)列，這樣就能實(shí)現(xiàn)一層一層遍歷，畫法如下：
代碼實(shí)現(xiàn)相較于前面來說簡單一些，但需要引入隊(duì)列的，關(guān)于隊(duì)列的介紹：
數(shù)據(jù)結(jié)構(gòu)—手撕隊(duì)列棧并相互實(shí)現(xiàn)
下面展示要使用的隊(duì)列的相關(guān)函數(shù)實(shí)現(xiàn)
// queue.h
typedef struct BinaryTreeNode* QDataType;
typedef struct QNode
{
QDataType data;
struct QNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
// queue.c
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
QNode* BuyQnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = BuyQnode(x);
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
bool QueueEmpty(Queue* pq)
{
if (pq->size == 0)
{
return true;
}
return false;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* newhead = pq->phead->next;
free(pq->phead);
pq->phead = newhead;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
那么借助隊(duì)列我們來實(shí)現(xiàn)剛才的層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%c ", front->data);
QueuePop(&q);
if (front->left)
QueuePush(&q, front->left);
if(front->right)
QueuePush(&q, front->right);
}
printf("\n");
//BinaryTreeDestory(&q);
}
二叉樹的銷毀
在知道了遍歷的多種途徑后，二叉樹的銷毀就很簡單了，在確定代碼如何實(shí)現(xiàn)前，先思考問題：應(yīng)該選用哪種遍歷來進(jìn)行二叉樹的銷毀？
結(jié)果是很明顯的，選用后序遍歷是最方便的，原因在于銷毀是需要進(jìn)行節(jié)點(diǎn)的釋放的，如果使用前序或者中序遍歷，那么在遍歷的過程中根節(jié)點(diǎn)會(huì)被先銷毀，那么找左子樹或者右子樹就帶來了不便(可以定義一個(gè)變量保存位置)，因此最好用后序遍歷，把子樹都銷毀了最后銷毀根
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
二叉樹節(jié)點(diǎn)個(gè)數(shù)
二叉樹節(jié)點(diǎn)個(gè)數(shù)也是轉(zhuǎn)換成子樹來解決，如果為NULL就返回0，其他情況返回左右相加再加上節(jié)點(diǎn)本身
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)
葉子節(jié)點(diǎn)個(gè)數(shù)求解和上述方法相似，也是找最小的子樹，但不同的地方是，葉子節(jié)點(diǎn)找到的條件是葉子作為根，它的左右子樹都為空，符合這樣的就是葉子節(jié)點(diǎn)，那么根據(jù)這個(gè)想法求得代碼不難得到：
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
int leftleave = BinaryTreeSize(root->left);
int rightleave = BinaryTreeSize(root->right);
return leftleave + rightleave;
}
二叉樹查找值為x的節(jié)點(diǎn)
這個(gè)相對(duì)較麻煩一點(diǎn)，先上展開圖和代碼
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
這里的關(guān)鍵動(dòng)作就是判斷ret1和ret2是否為空，如果是，則說明找到正確的值，那么就會(huì)一路被送出函數(shù)，相反會(huì)一直返回NULL，因此就不必?fù)?dān)心送出其他元素的情況
二叉樹是否為完全二叉樹
這個(gè)思路也較為復(fù)雜，首先，需要解決的問題是用什么思路，基本思路是一個(gè)一個(gè)看，如果在某一個(gè)節(jié)點(diǎn)已經(jīng)為空的前提下，它后面的節(jié)點(diǎn)還不為空，那么就說明這個(gè)不是完全二叉樹
因此這個(gè)思路是不是和層序遍歷很像呢？我們借助這樣的思路繼續(xù)寫下去
當(dāng)隊(duì)列不為空就繼續(xù)入隊(duì)列出隊(duì)列進(jìn)行層序遍歷，當(dāng)遇到空就跳出，跳出循環(huán)后此時(shí)隊(duì)列并不為空，繼續(xù)出隊(duì)列，如果發(fā)現(xiàn)某個(gè)元素不為空，那么就證明這并不是完全二叉樹
代碼實(shí)現(xiàn)如下：
int BinaryTreeComplete(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
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)
{
BinaryTreeDestory(&q);
return 0;
}
}
BinaryTreeDestory(&q);
return 1;
}
至此，二叉樹的基本功能實(shí)現(xiàn)就都結(jié)束了，很明顯，二叉樹的實(shí)現(xiàn)并不容易，它不僅需要對(duì)遞歸有一定深度的認(rèn)識(shí)，還需要你對(duì)隊(duì)列有足夠的理解，才能解決層序遍歷和判斷完全二叉樹
這需要進(jìn)行更多的練習(xí)，也為后面更復(fù)雜的樹打基礎(chǔ)和鋪墊文章來源：http://www.zghlxwxcb.cn/news/detail-576796.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-576796.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)---手撕圖解二叉樹(含大量遞歸圖解)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
