數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)

二叉樹(shù)

1.一些特殊的二叉樹(shù)

1.滿二叉樹(shù)

滿二叉樹(shù)：一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿二叉樹(shù)。也就是
說(shuō)，如果==一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k-1== ，則它就是滿二叉樹(shù)。

2.完全二叉樹(shù)

完全二叉樹(shù)：完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K
的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一 一對(duì)
應(yīng)時(shí)稱之為完全二叉樹(shù)。 **要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)**。

2.手動(dòng)創(chuàng)建一顆二叉樹(shù)

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 手動(dòng)快速創(chuàng)建一棵簡(jiǎn)單的二叉樹(shù)來(lái)測(cè)試三種深度優(yōu)先遍歷方式（前中后序遍歷）（后續(xù)學(xué)習(xí)遞歸構(gòu)建二叉樹(shù)才是真正常用的方法）
typedef int BinaryTreeDataType;typedef struct BinaryTreeNode
{BinaryTreeDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;BTNode* CreateBTNode(BinaryTreeDataType x)
{BTNode* NewBTNode = (BTNode*)malloc(sizeof(BTNode));if (NewBTNode == NULL){perror("malloc fail");exit(-1);}NewBTNode->val = x;NewBTNode->left = NULL;NewBTNode->right = NULL;return NewBTNode;
}
BTNode* CreatBinaryTree()
{BTNode* root = CreateBTNode(1);BTNode* node2 = CreateBTNode(2);BTNode* node3 = CreateBTNode(3);BTNode* node4 = CreateBTNode(4);BTNode* node5 = CreateBTNode(5);BTNode* node6 = CreateBTNode(6);root->left = node2;root->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return root;
}

3.二叉樹(shù)深度優(yōu)先遍歷

前序、中序和后序遍歷都屬于「深度優(yōu)先遍歷 depth-first traversal, DFS」，它體現(xiàn)了一種“先走到盡頭，再回溯繼續(xù)”的遍歷方式。

// 前序遍歷
void Preorder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->val);Preorder(root->left);Preorder(root->right);
}// 中序遍歷
void Inorder(BTNode* root)
{if (root == NULL){printf("N ");return;}Inorder(root->left);printf("%d ", root->val);Inorder(root->right);
}
// 后序遍歷
void Postorder(BTNode* root)
{if (root == NULL){printf("N ");return;}Postorder(root->left);Postorder(root->right);printf("%d ", root->val);
}

4.二叉樹(shù)層序遍歷

層序遍歷本質(zhì)上屬于「廣度優(yōu)先遍歷 breadth-first traversal, BFS」，它體現(xiàn)了一種“一圈一圈向外擴(kuò)展”的逐層遍歷方式。

利用隊(duì)列先進(jìn)先出的性質(zhì)：父親先進(jìn)隊(duì)列，父親出來(lái)時(shí)再帶孩子進(jìn)隊(duì)列

void BinaryTreeLevelOrder(BTNode* root)
{// 利用隊(duì)列   實(shí)現(xiàn)二叉樹(shù)的層序遍歷   (隊(duì)列先進(jìn)先出性質(zhì))Queue* queuehead = Init();Push(&queuehead, root);while (!Empty(queuehead)){// 遍歷二叉樹(shù)入隊(duì)列并挨個(gè)打印值BTNode* front = Peek(&queuehead);printf("%c ", front->data);Pop(&queuehead);if (front->left != NULL){Push(&queuehead, front->left);}if (front->right != NULL){Push(&queuehead, front->right);}}// 銷毀隊(duì)列Destroy(&queuehead);
}

5.二叉樹(shù)基礎(chǔ)操作

1.創(chuàng)建二叉樹(shù)

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
// 通過(guò) 前序遍歷 的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)BTNode* BinaryTreeCreate(BTDataType* parray, int* pi)
{// 前序遍歷創(chuàng)建二叉樹(shù)if (parray[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = parray[(*pi)++];root->left = BinaryTreeCreate(parray, pi);root->right = BinaryTreeCreate(parray, pi);return root;
}

2.二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)

/*
寫(xiě)法一：遍歷計(jì)數(shù)
*/
int BinaryTreeSize(BTNode* root)
{// 遍歷二叉樹(shù)計(jì)算節(jié)點(diǎn)個(gè)數(shù)static int size = 0;// 函數(shù)中使用靜態(tài)不能完全解決問(wèn)題，無(wú)法處理多次計(jì)算的情況if (root == NULL){return 0;}size++;BinaryTreeSize(root->left);BinaryTreeSize(root->right);return size;
}/*
寫(xiě)法二：遞歸分治子問(wèn)題
*/
int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//節(jié)點(diǎn)個(gè)數(shù) = 左子樹(shù)節(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)節(jié)點(diǎn)個(gè)數(shù) + 1
}

3.二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}// 葉子節(jié)點(diǎn)個(gè)數(shù) = 左子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)return root->left == NULL && root->right == NULL ? 1 : BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

4.二叉樹(shù)的高度

/*
寫(xiě)法1：
*/
int BinaryTreeHight(BTNode* root)
{if (root == NULL){return 0;}// 此處遞歸分治多次重復(fù)導(dǎo)致效率過(guò)低(原因是此邏輯中比較時(shí)候進(jìn)行了遞歸分治，計(jì)算的時(shí)候又重復(fù)進(jìn)行了計(jì)算)return BinaryTreeHight(root->left) > BinaryTreeHight(root->right)|| BinaryTreeHight(root->left) == BinaryTreeHight(root->right)? BinaryTreeHight(root->left) + 1: BinaryTreeHight(root->right) + 1;// 二叉樹(shù)的高度 = 左子樹(shù)與右子樹(shù)相比，高度更高的那棵樹(shù)的高度 + 1
}/*
寫(xiě)法2：
*/
int BinaryTreeHight(BTNode* root)
{if (root == NULL){return 0;}//提前記錄高度int lefthight = BinaryTreeHight(root->left);int righthight = BinaryTreeHight(root->right);// 二叉樹(shù)的高度 = 左子樹(shù)與右子樹(shù)相比，高度更高的那棵樹(shù)的高度 + 1return lefthight > righthight|| lefthight == righthight? lefthight + 1: righthight + 1;}

5.二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (root != NULL && k == 1){return 1;}// 問(wèn)題拆分：第k層節(jié)點(diǎn)個(gè)數(shù) = 左子樹(shù)第k-1層節(jié)點(diǎn)數(shù) + 右子樹(shù)第k-層節(jié)點(diǎn)數(shù)return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}

6.二叉樹(shù)查找值為x的節(jié)點(diǎn)

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}// 前序遍歷二叉樹(shù)尋找該節(jié)點(diǎn)if (root->data == x){return root;}else{BTNode* leftnode = BinaryTreeFind(root->left, x);if (leftnode){return leftnode;}BTNode* rightnode = BinaryTreeFind(root->right, x);if (rightnode){return rightnode;}//如果左右節(jié)點(diǎn)都不是我們要找的該節(jié)點(diǎn)則返回空if (leftnode == NULL && rightnode == NULL){return NULL;}}
}

7.層序遍歷

void BinaryTreeLevelOrder(BTNode* root)
{// 利用隊(duì)列   實(shí)現(xiàn)二叉樹(shù)的層序遍歷   (隊(duì)列先進(jìn)先出性質(zhì))Queue* queuehead = Init();Push(&queuehead, root);while (!Empty(queuehead)){// 遍歷二叉樹(shù)入隊(duì)列并挨個(gè)打印值BTNode* front = Peek(&queuehead);printf("%c ", front->data);Pop(&queuehead);if (front->left != NULL){Push(&queuehead, front->left);}if (front->right != NULL){Push(&queuehead, front->right);}}// 銷毀隊(duì)列Destroy(&queuehead);
}

變形：如何控制一層一層打印并換行？

// 層序遍歷變形換行打印
void BinaryTreeLevelOrder(BTNode* root)
{// 利用隊(duì)列   實(shí)現(xiàn)二叉樹(shù)的層序遍歷   (隊(duì)列先進(jìn)先出性質(zhì))Queue* queuehead = Init();Push(&queuehead, root);// 根據(jù)每一層的數(shù)據(jù)的個(gè)數(shù)得出打印多少次后進(jìn)行一次換行int levelsize = 1;while (!Empty(queuehead)){// 一層一層出while (levelsize--){// 遍歷二叉樹(shù)入隊(duì)列BTNode* front = Peek(&queuehead);printf("%c ", front->data);Pop(&queuehead);if (front->left != NULL){Push(&queuehead, front->left);}if (front->right != NULL){Push(&queuehead, front->right);}}printf("\n");levelsize = Size(queuehead);}// 銷毀隊(duì)列Destroy(&queuehead);
}

8.二叉樹(shù)銷毀

// 二叉樹(shù)銷毀
void BinaryTreeDestory(BTNode* root)
{// 走后序遍歷更方便銷毀if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

9.判斷二叉樹(shù)是否是完全二叉樹(shù)

思路：完全二叉樹(shù)只有最后一層會(huì)出現(xiàn) NULL 值，而且出現(xiàn)了 NULL 值，則后面不會(huì)再出現(xiàn)非空的值。我們可以通過(guò)層序遍歷的思想，一層一層遍歷，如果遇到空結(jié)點(diǎn)，記錄一下，然后繼續(xù)遍歷，若是后面出現(xiàn)了非空值，則說(shuō)明該二叉樹(shù)不是完全二叉樹(shù)。

// 判斷二叉樹(shù)是否是完全二叉樹(shù)
// 參數(shù)：root，一個(gè)指向二叉樹(shù)根節(jié)點(diǎn)的指針
bool BinaryTreeComplete(BTNode* root)
{Queue* queuehead = Init();// 將二叉樹(shù)的根節(jié)點(diǎn)入隊(duì)列Push(&queuehead, root);while (!Empty(queuehead)){BTNode* front = Peek(&queuehead);if (front == NULL){break;}Pop(&queuehead);Push(&queuehead, front->left);Push(&queuehead, front->right);}// 當(dāng)?shù)谝淮伪闅v的時(shí)候出道空代表應(yīng)當(dāng)結(jié)束了，第二次繼續(xù)往后遍歷如果隊(duì)列中還有非空代表不是完全二叉樹(shù)while (!Empty(queuehead)){BTNode* front = Peek(&queuehead);Pop(&queuehead);if (front != NULL){return false;}}return true;
}