鏈?zhǔn)蕉鏄涞膶?shí)現(xiàn)
1.了解三種遍歷方式
學(xué)習(xí)鏈?zhǔn)蕉鏄湟廊N遍歷方式，便于對(duì)二叉樹的節(jié)點(diǎn)以及左子樹和右子樹進(jìn)行操作。
前序遍歷：根、左子樹、右子樹
中序遍歷：左子樹、根、右子樹
后序遍歷：左子樹、右子樹、根
以下圖為例：
得到的結(jié)果：
前序遍歷：1 2 3 4 5 6
中序遍歷：3 2 1 5 4 6
后序遍歷：3 2 5 6 4 1
2.構(gòu)建二叉樹
構(gòu)建二叉樹有兩種方式，一種是手動(dòng)構(gòu)建，另一種是前序遍歷構(gòu)建
（1）手動(dòng)構(gòu)建
創(chuàng)建需要的節(jié)點(diǎn)，然后把它們按照自己想要的結(jié)構(gòu)連接起來即可
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
（2）前序遍歷構(gòu)建
首先函數(shù)參數(shù)傳過來一個(gè)數(shù)組，數(shù)組可以是數(shù)字也可以是字符，這里用字符數(shù)組進(jìn)行演示。
char arr[] = “ABD##E#H##CF##G##”;// # 代表空
我們還需要一個(gè)變量 i 來記錄數(shù)組下標(biāo)的位置，i 初始化為0。
注意：傳變量 i 的時(shí)候要傳它的地址，因?yàn)榈葧?huì)函數(shù)遞歸 i 的值也要改變，改變函數(shù)參數(shù)的值要有它的地址才行。
進(jìn)入函數(shù)，首先判斷當(dāng)前 i 下標(biāo)指向的位置是不是 # ，如果是，返回空指針，i 位置往后走；不是，開辟空間創(chuàng)建一個(gè)節(jié)點(diǎn)（記得判空），把當(dāng)前位置的字符賦給節(jié)點(diǎn)的值，i 位置往后走。
以上是前序遍歷的根左右中的根部分，即當(dāng)前節(jié)點(diǎn)創(chuàng)建完畢，接著要連接它的孩子節(jié)點(diǎn)。用函數(shù)遞歸的方式使當(dāng)前節(jié)點(diǎn)進(jìn)入它的孩子節(jié)點(diǎn)，孩子節(jié)點(diǎn)可以返回（連接）上一層節(jié)點(diǎn)。最后返回根節(jié)點(diǎn)。
樹的形狀：
BTNode* TreeCreate(char* a, int* pi)
{
//如果是 # 說明為空返回上一層函數(shù)
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//不是空，開辟一個(gè)節(jié)點(diǎn)大小的空間，創(chuàng)建一個(gè)節(jié)點(diǎn)
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc fail");
exit(-1);
}
//賦值
root->val = a[*pi];
(*pi)++;
//當(dāng)前節(jié)點(diǎn)連接孩子節(jié)點(diǎn)
root->left = TreeCreate(a, pi);
root->right = TreeCreate(a, pi);
//當(dāng)前節(jié)點(diǎn)連接上一個(gè)節(jié)點(diǎn) || 返回根節(jié)點(diǎn)
return root;
}
3.二叉樹的銷毀
銷毀二叉樹從葉子節(jié)點(diǎn)開始銷毀，采用后續(xù)遍歷的思路。遞歸到樹的最下層，也就是葉子節(jié)點(diǎn)，當(dāng)遞歸到空指針時(shí)返回上一層函數(shù)，當(dāng)前節(jié)點(diǎn)的左子樹和右子樹都遞歸好了，就銷毀當(dāng)前節(jié)點(diǎn)，然后返回上一層函數(shù)，以此類推。
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
4.二叉樹節(jié)點(diǎn)個(gè)數(shù)
當(dāng)前節(jié)點(diǎn)如果是空指針，返回0；不是空指針，先進(jìn)入它的左函數(shù)（左子樹），在左函數(shù)中還是先判斷是否為空指針，是，返回0，不是，接著還是先進(jìn)入它的左函數(shù)，如果次時(shí)它的左函數(shù)的這個(gè)節(jié)點(diǎn)為空，就返回0，然后進(jìn)入它的右函數(shù)，也是空，返回0。當(dāng)前節(jié)點(diǎn)的左右都是空但這個(gè)節(jié)點(diǎn)不為空，返回1，到上一層函數(shù)，以此類推，每返回一個(gè)節(jié)點(diǎn)加1
int TreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
5.二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
葉子節(jié)點(diǎn)的特點(diǎn)是它的左右子樹都為空指針，還是用遞歸的思路，當(dāng)節(jié)點(diǎn)遞歸到空指針，返回0；如果當(dāng)前節(jié)點(diǎn)的左右子樹都滿足為空指針，說明當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，返回1
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
{
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
}
6.二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
傳進(jìn)一個(gè)參數(shù)k，k的值就是二叉樹的某一層（根節(jié)點(diǎn)為第一層）。當(dāng)k等于1時(shí)，在第一層；k等于2時(shí)，在第二層；k等于3時(shí)，在第三層……可以使用一個(gè)方法，當(dāng)k等于1時(shí)，就是在第k層，用函數(shù)遞歸，每遞歸到下一層，k的值減1，直到k等于1；當(dāng)前節(jié)點(diǎn)k為1時(shí)，就返回1，最后可以統(tǒng)計(jì)出第k層的節(jié)點(diǎn)個(gè)數(shù)。
int TreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
7.二叉樹查找值為x的節(jié)點(diǎn)
查找值為x的節(jié)點(diǎn)，找到則返回這個(gè)節(jié)點(diǎn)，否則返回空。當(dāng)前節(jié)點(diǎn)如果是空指針，返回空到上一層函數(shù)。如果當(dāng)前節(jié)點(diǎn)不為空，判斷這個(gè)節(jié)點(diǎn)的值是否是x，如果是，返回這個(gè)節(jié)點(diǎn)到上一層函數(shù)；不是，創(chuàng)建一個(gè)變量，讓這個(gè)變量接收遞歸的下一個(gè)函數(shù)的返回值，然后下面判斷這個(gè)變量是否為空，是空進(jìn)入另一個(gè)函數(shù)遞歸，不是返回這個(gè)變量到上一層函數(shù)（這個(gè)變量就是找到的節(jié)點(diǎn)）。如果沒有要找的節(jié)點(diǎn)，返回空。
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
{
return ret;
}
ret = TreeFind(root->right, x);
if (ret)
{
return ret;
}
return NULL;
}
8.二叉樹的前、中、后序遍歷
根據(jù)二叉樹的三種遍歷方式打印節(jié)點(diǎn)，每種方式的打印順序不同。
//二叉樹前序遍歷
void TreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%c ", root->val);
TreePrevOrder(root->left);
TreePrevOrder(root->right);
}
//二叉樹中序遍歷
void TreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeInOrder(root->left);
printf("%c ", root->val);
TreeInOrder(root->right);
}
//二叉樹后序遍歷
void TreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
TreePostOrder(root->left);
TreePostOrder(root->right);
printf("%c ", root->val);
}
9.二叉樹的層序遍歷
層序遍歷是一層一層的打印節(jié)點(diǎn)數(shù)據(jù)，需要用隊(duì)列，隊(duì)列的特點(diǎn)是先進(jìn)先出。我們可以先往隊(duì)列里放入根節(jié)點(diǎn)，此時(shí)隊(duì)列不為空，然后用一個(gè)臨時(shí)變量獲取隊(duì)列的頭元素（此時(shí)就是根節(jié)點(diǎn)），判斷它的左孩子是不是空，不是空，往隊(duì)列放入左孩子節(jié)點(diǎn)，是空就跳過；右孩子同理。接著打印這個(gè)臨時(shí)變量節(jié)點(diǎn)的值，再把從隊(duì)列里刪除掉。因?yàn)榍懊嬗蟹湃牍?jié)點(diǎn)，所以隊(duì)列不為空，就繼續(xù)前面的步驟，這樣就可以一層一層的打印每個(gè)節(jié)點(diǎn)的值，直到隊(duì)列為空跳出結(jié)束。
void TreeLevelOrder(BTNode* root)
{
Que q;
QueInit(&q);
QuePush(&q, root);
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front->left)
{
QuePush(&q, front->left);
}
if (front->right)
{
QuePush(&q, front->right);
}
printf("%c ", front->val);
QuePop(&q);
}
}
10.判斷二叉樹是否是完全二叉樹
判斷是不是完全二叉樹還是用隊(duì)列的結(jié)構(gòu)，隊(duì)列可以層序遍歷，一層一層的進(jìn)入數(shù)據(jù)。完全二叉樹的特點(diǎn)是前h-1層是滿的，最后一層可能是滿的，也可能是不滿的，并且它的最后一層必須從左到右是連續(xù)的。
這里要有兩個(gè)循環(huán)控制，第一個(gè)循環(huán)里層序往隊(duì)列中放入節(jié)點(diǎn)（包括空），定義一個(gè)臨時(shí)變量獲取隊(duì)列的頭元素，判斷它是不是空，是空，就跳出第一個(gè)循環(huán)，到第二個(gè)循環(huán)；不是空，往隊(duì)列放入它的左右孩子節(jié)點(diǎn)（空也放入）。
到第二個(gè)循環(huán)，如果這個(gè)二叉樹是完全二叉樹，就不會(huì)進(jìn)入第二個(gè)循環(huán)，因?yàn)槭峭耆鏄涞脑挘诘谝粋€(gè)循環(huán)它遇到空才跳出，此時(shí)這個(gè)空的后面就沒有節(jié)點(diǎn)了，到第二個(gè)循環(huán)時(shí)，由于空后面沒有節(jié)點(diǎn)，所以隊(duì)列已經(jīng)是空的，不會(huì)進(jìn)入第二個(gè)循環(huán)，直接返回0，是完全二叉樹。
如果這個(gè)二叉樹不是完全二叉樹，那么在第一個(gè)循環(huán)遇到空跳出后，它的后面還有節(jié)點(diǎn)，此時(shí)隊(duì)列不為空，繼續(xù)用前面的方法，定義一個(gè)臨時(shí)變量獲取隊(duì)列頭元素，判斷是不是空，是空，刪除這個(gè)空，繼續(xù)判斷（不管空與節(jié)點(diǎn)之間隔多少，它們都在隊(duì)列里，因此隊(duì)列不為空繼續(xù)判斷、刪除，直到隊(duì)列為空才停下）；不是空，說明還有節(jié)點(diǎn)，直接返回1，不是完全二叉樹。文章來源：http://www.zghlxwxcb.cn/news/detail-715781.html
int TreeComplete(BTNode* root)
{
Que q;
QueInit(&q);
QuePush(&q, root);
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front == NULL)
{
break;
}
QuePush(&q, front->left);
QuePush(&q, front->right);
QuePop(&q);
}
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front != NULL)
{
return 1;
}
QuePop(&q);
}
return 0;
}
全部代碼
1.BinaryTree.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;
//構(gòu)建二叉樹
BTNode* TreeCreate(char* a, int* pi);
//二叉樹銷毀
void TreeDestroy(BTNode* root);
//二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root);
//二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(BTNode* root);
//二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int TreeLevelKSize(BTNode* root, int k);
//二叉樹查找值為x的節(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x);
//二叉樹前序遍歷
void TreePrevOrder(BTNode* root);
//二叉樹中序遍歷
void TreeInOrder(BTNode* root);
//二叉樹后序遍歷
void TreePostOrder(BTNode* root);
//層序遍歷
void TreeLevelOrder(BTNode* root);
//判斷二叉樹是否是完全二叉樹
int TreeComplete(BTNode* root);
//初始化
void QueInit(Que* pq);
//銷毀
void QueDestroy(Que* pq);
//入隊(duì)
void QuePush(Que* pq, QDataType x);
//出隊(duì)
void QuePop(Que* pq);
//獲取頭部元素
QDataType QueFront(Que* pq);
//獲取隊(duì)尾元素
QDataType QueBack(Que* pq);
//獲取元素個(gè)數(shù)
int QueSize(Que* pq);
//檢查是否為空
bool QueEmpty(Que* pq);
2.BinaryTree.c
#include "BinaryTree.h"
//構(gòu)建二叉樹
BTNode* TreeCreate(char* a, int* pi)
{
//如果是 # 說明為空返回上一層函數(shù)
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//不是空，開辟一個(gè)節(jié)點(diǎn)大小的空間，創(chuàng)建一個(gè)節(jié)點(diǎn)
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("malloc fail");
exit(-1);
}
root->val = a[*pi];
(*pi)++;
//當(dāng)前節(jié)點(diǎn)連接孩子節(jié)點(diǎn)
root->left = TreeCreate(a, pi);
root->right = TreeCreate(a, pi);
//當(dāng)前節(jié)點(diǎn)連接上一個(gè)節(jié)點(diǎn) || 返回根節(jié)點(diǎn)
return root;
}
//二叉樹銷毀
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
//二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
{
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
}
//二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int TreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
//二叉樹查找值為x的節(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
{
return ret;
}
ret = TreeFind(root->right, x);
if (ret)
{
return ret;
}
return NULL;
}
//二叉樹前序遍歷
void TreePrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%c ", root->val);
TreePrevOrder(root->left);
TreePrevOrder(root->right);
}
//二叉樹中序遍歷
void TreeInOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeInOrder(root->left);
printf("%c ", root->val);
TreeInOrder(root->right);
}
//二叉樹后序遍歷
void TreePostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
TreePostOrder(root->left);
TreePostOrder(root->right);
printf("%c ", root->val);
}
//層序遍歷
void TreeLevelOrder(BTNode* root)
{
Que q;
QueInit(&q);
QuePush(&q, root);
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front->left)
{
QuePush(&q, front->left);
}
if (front->right)
{
QuePush(&q, front->right);
}
printf("%c ", front->val);
QuePop(&q);
}
}
//判斷二叉樹是否是完全二叉樹
int TreeComplete(BTNode* root)
{
Que q;
QueInit(&q);
QuePush(&q, root);
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front == NULL)
{
break;
}
QuePush(&q, front->left);
QuePush(&q, front->right);
QuePop(&q);
}
while (!QueEmpty(&q))
{
BTNode* front = QueFront(&q);
if (front != NULL)
{
return 1;
}
QuePop(&q);
}
return 0;
}
//初始化
void QueInit(Que* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
//銷毀
void QueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//入隊(duì)
void QuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
//出隊(duì)
void QuePop(Que* pq)
{
assert(pq);
assert(!QueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
//獲取頭部元素
QDataType QueFront(Que* pq)
{
assert(pq);
assert(!QueEmpty(pq));
return pq->head->data;
}
//獲取隊(duì)尾元素
QDataType QueBack(Que* pq)
{
assert(pq);
assert(!QueEmpty(pq));
return pq->tail->data;
}
//獲取元素個(gè)數(shù)
int QueSize(Que* pq)
{
assert(pq);
return pq->size;
}
//檢查是否為空
bool QueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}
3.test.c
#include "BinaryTree.h"
int main()
{
char arr[] = "ABD##E#H##CF##G##";
int i = 0;
//構(gòu)建二叉樹
BTNode* root = TreeCreate(arr, &i);
//二叉樹節(jié)點(diǎn)個(gè)數(shù)
printf("二叉樹節(jié)點(diǎn)個(gè)數(shù)：");
printf("%d ", TreeSize(root));
printf("\n");
//二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
printf("二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)：");
printf("%d ", TreeLeafSize(root));
printf("\n");
//二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
printf("二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)：");
int k = 3;
printf("%d ", TreeLevelKSize(root, k));
printf("\n");
//二叉樹查找值為x的節(jié)點(diǎn)
char x = 'G';
BTNode* rec = TreeFind(root, x);
if (rec)
{
printf("找到了\n");
}
else
{
printf("沒找到\n");
}
//二叉樹前序遍歷
printf("前：");
TreePrevOrder(root);
printf("\n");
//二叉樹中序遍歷
printf("中：");
TreeInOrder(root);
printf("\n");
//二叉樹后序遍歷
printf("后：");
TreePostOrder(root);
printf("\n");
//層序遍歷
printf("層序：");
TreeLevelOrder(root);
printf("\n");
//判斷二叉樹是否是完全二叉樹
if (0 == TreeComplete(root))
{
printf("是完全二叉樹\n");
}
else
printf("不是完全二叉樹\n");
//二叉樹銷毀
TreeDestroy(root);
return 0;
}
感謝觀看~文章來源地址http://www.zghlxwxcb.cn/news/detail-715781.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
