柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu)——二叉樹

http://yzkb.51969.com/

1.樹

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n 個(gè)有限結(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋?lái)像一棵倒掛的樹。

——有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。

——除了根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)被分為M個(gè)互不相交的集合，其中每一個(gè)集合又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或者多個(gè)后繼。因此，樹是遞歸定義的。

——樹形結(jié)構(gòu)中，?樹之間不能有交集，否則就不是樹形結(jié)構(gòu)。

?例如：

（注：該圖片來(lái)自于百度）

1.1 各種概念

——父結(jié)點(diǎn)/雙親結(jié)點(diǎn)：若?個(gè)結(jié)點(diǎn)含有?結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其?結(jié)點(diǎn)的?結(jié)點(diǎn)。

——子結(jié)點(diǎn)/孩子結(jié)點(diǎn)：?個(gè)結(jié)點(diǎn)含有的?樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的?結(jié)點(diǎn)。

——結(jié)點(diǎn)的度：有幾個(gè)孩子，就為幾度。

——樹的度：最大結(jié)點(diǎn)的度就為樹的度。

——葉子結(jié)點(diǎn)/終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)就為葉子結(jié)點(diǎn)。

——分支結(jié)點(diǎn)/非終端結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。

——兄弟結(jié)點(diǎn)：具有相同的父結(jié)點(diǎn)。

——結(jié)點(diǎn)的層次：有幾層層次就為多少。

——樹的高度/深度：樹的最大層次。

——結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。

——路徑：?條從樹中任意節(jié)點(diǎn)出發(fā)，沿?節(jié)點(diǎn)-?節(jié)點(diǎn)連接，達(dá)到任意節(jié)點(diǎn)的序列。

——子孫：以某結(jié)點(diǎn)為根的?樹中任?結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的?孫。

——森林：由多棵互不相交的樹組成的。

1.2 樹的表示

用孩子兄弟表示法：

struct TreeNode

{

struct Node* child; //左邊開(kāi)始的第一個(gè)孩子的結(jié)點(diǎn)

struct Node* brother; //指向其右邊的下一個(gè)兄弟結(jié)點(diǎn)

int data; //結(jié)點(diǎn)中的數(shù)據(jù)域

};

用圖片來(lái)進(jìn)行分析：

（注：上述圖片來(lái)自于比特就業(yè)課）

通過(guò)上述的圖片我們可以比較清晰地了解該方法。

1.3 應(yīng)用

?件系統(tǒng)是計(jì)算機(jī)存儲(chǔ)和管理?件的?種?式，它利?樹形結(jié)構(gòu)來(lái)組織和管理?件和?件夾。在?件系統(tǒng)中，樹結(jié)構(gòu)被?泛應(yīng)?，它通過(guò)?結(jié)點(diǎn)和?結(jié)點(diǎn)之間的關(guān)系來(lái)表?不同層級(jí)的?件和?件夾之間的關(guān)聯(lián)。

2.二叉樹

2.1 概念與結(jié)構(gòu)

二叉樹是樹形結(jié)構(gòu)的一種。

一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合由一個(gè)根結(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成。

例如：

（注：該圖片來(lái)自于比特就業(yè)課）

二叉樹的特點(diǎn)：

——二叉樹不存在度大于2的結(jié)點(diǎn)

——二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

2.2 特殊的二叉樹

2.2.1 滿二叉樹

每一層的結(jié)點(diǎn)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。結(jié)點(diǎn)的總數(shù)就是?2^k - 1

（注：圖片來(lái)自于百度）

2.2.2 完全二叉樹

完全?叉樹是效率很?的數(shù)據(jù)結(jié)構(gòu)，完全?叉樹是由滿?叉樹?引出來(lái)的。要注意的是滿?叉樹是?種特殊的完全?叉樹。

例如：

（注：圖片來(lái)自比特就業(yè)課）

則該結(jié)構(gòu)的特點(diǎn)是：假設(shè)二叉樹的層次為K層，則除了第K層外，每層結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最大結(jié)點(diǎn)數(shù)，第K層不一定達(dá)到最大結(jié)點(diǎn)數(shù)。

且完全二叉樹結(jié)點(diǎn)的順序是從左到右順序放置的。

2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)：一種是順序結(jié)構(gòu)，一種是鏈?zhǔn)浇Y(jié)構(gòu)。

2.3.1 順序結(jié)構(gòu)

順序結(jié)構(gòu)是使用數(shù)組來(lái)進(jìn)行存儲(chǔ)的，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)，完全二叉樹使用順序結(jié)構(gòu)進(jìn)行存儲(chǔ)。

2.3.2 鏈?zhǔn)浇Y(jié)構(gòu)

?叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，?鏈表來(lái)表??棵?叉樹，即?鏈來(lái)指?元素的邏輯關(guān)系。 通常的?法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e?來(lái)給出該結(jié)點(diǎn)左孩?和右孩?所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)?分為?叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中?般都是?叉鏈。后?課程學(xué)到?階數(shù)據(jù)結(jié)構(gòu)如紅?樹等會(huì)?到三叉鏈。

3.實(shí)現(xiàn)順序結(jié)構(gòu)二叉樹

堆是一種特殊的二叉樹，具有二叉樹的特性的同時(shí)，還具備其他的特性。

3.1 堆的概念與結(jié)構(gòu)

分為小跟堆和大根堆，我們通過(guò)圖片來(lái)進(jìn)行了解：

堆具有以下的性質(zhì)：

——堆中某個(gè)結(jié)點(diǎn)的值總是不大于或者不小于其父結(jié)點(diǎn)的值

——堆總是一棵完全二叉樹

二叉樹的性質(zhì)：

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下、從左至右的數(shù)組順序?qū)λ薪Y(jié)點(diǎn)從0開(kāi)始編號(hào)（例如上述的圖片），則對(duì)于序號(hào)為i的結(jié)點(diǎn)有：

?1）若i > 0 , i 位置結(jié)點(diǎn)的雙親序號(hào)為：( i - 1 ) / 2 ；i = 0， i為根結(jié)點(diǎn)編號(hào)，無(wú)雙親編號(hào)。

?2）若2i + 1 < n，左孩子序號(hào)：2i + 1，2i + 1 >= n，否則無(wú)左孩子。

?3）若2i + 2 < n，右孩子序號(hào)：2i + 2，2i + 2 >= n，否則無(wú)右孩子。

3.2 堆的實(shí)現(xiàn)

3.2.1 堆的初始化與銷毀

與前幾次實(shí)現(xiàn)基本相同，這里省略分析過(guò)程。最終的代碼會(huì)匯合在一起。

3.2.2?堆數(shù)據(jù)的插入

?由于插入的數(shù)據(jù)是隨機(jī)的，我們不確定插入數(shù)據(jù)的大小，而大堆和小堆之間的數(shù)據(jù)的順序是有一定規(guī)律的，因此，我們要通過(guò)適當(dāng)?shù)姆椒▉?lái)進(jìn)行插入。用堆的向上調(diào)整方法。

這里對(duì)于堆的向上調(diào)整算法不再做過(guò)多的介紹，直接上代碼：

void Swap(int* x, int* y)

{

int tmp = *x;

*x = *y;

*y = tmp;

}

void AdustUp(HPDataType* arr, int child)

{

int parent = (child - 1) / 2;

while (child > 0)//不需要等于0，child只要走到了根結(jié)點(diǎn)的位置，根結(jié)點(diǎn)不需要交換了

{

if (arr[child] < arr[parent])

{

Swap(&arr[child], &arr[parent]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

void HPPush(HP* php, HPDataType x)

{

assert(php);

//判斷空間是否足夠

if (php->capacity == php->size)

{

//擴(kuò)容

int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;

HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));

if (tmp == NULL)

{

perror("realloc fail!");

exit(1);

}

php->arr = tmp;

php->capacity = newCapacity;

}

php->arr[php->size] = x;

AdustUp(php->arr, php->size);

++php->size;

}

3.2.3 堆數(shù)據(jù)的刪除

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

與之前不同的是，在堆的刪除中，我們刪除的是堆頂?shù)臄?shù)據(jù)。

代碼如下：

void AdjustDown(HPDataType* arr, int parent, int n)

{

int child = parent * 2 + 1;

while (child < n)

{

//找左右孩子中最小的那一個(gè)

if (child + 1 < n && arr[child] > arr[child + 1])

{

child++;

}

if (arr[child] < arr[parent])

{

Swap(&arr[child], &arr[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

void HPPop(HP* php)

{

assert(php && php->size);

Swap(&php->arr[0], &php->arr[php->size - 1]);

--php->size;

AdjustDown(php->arr, 0, php->size);

}

3.3 堆的應(yīng)用---TOP-K問(wèn)題

TOP-K問(wèn)題：即求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。

當(dāng)數(shù)據(jù)量太大的時(shí)候，就不能用排序的方法，這時(shí)，我們可以用堆來(lái)解決問(wèn)題。

思路：拿K個(gè)數(shù)據(jù)來(lái)建堆，然后讓取到的數(shù)據(jù)分別與原始的K個(gè)數(shù)據(jù)進(jìn)行比較，最后所得即為所求。時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(K)。根據(jù)上述的分析可得，找最小的K個(gè)數(shù)據(jù)，建大堆，找最大的K個(gè)數(shù)據(jù)，建小堆。

代碼實(shí)現(xiàn)如下：

void CreateNDate()

{

//造數(shù)據(jù)

int n = 100000;

srand(time(0));

const char* file = "data.txt";

FILE* fin = fopen(file, "w");

if (fin == NULL)

{

perror("fopen error");

return;

}

for (int i = 0; i < n; i++)

{

int x = (rand() + i) % 1000000;

fprintf(fin, "%d\n", x);

}

fclose(fin);

}

void TOPK()

{

int k = 0;

printf("請(qǐng)輸入K:");

scanf("%d", &k);

//從文件中讀取前K個(gè)數(shù)據(jù)

const char* file = "data.txt";

FILE* fout = fopen(file, "r");

if (fout == NULL)

{

perror("fopen fail!");

exit(1);

}

int* minHeap = (int*)malloc(k * sizeof(int));

if (minHeap == NULL)

{

perror("malloc fail!");

exit(0);

}

for (int i = 0; i < k; i++)

{

fscanf(fout, "%d", &minHeap[i]);

}

//建堆

for (int i = (k - 1 - 1) / 2; i >= 0; i--)

{

AdjustDown(minHeap, i, k);

}

int x = 0;

while (fscanf(fout, "%d", &x) != EOF)

{

if (x > minHeap[0])

{

minHeap[0] = x;

AdjustDown(minHeap, 0, k);

}

}

for (int i = 0; i < k; i++)

{

printf("%d ", minHeap[i]);

}

fclose(fout);

}

int main()

{

//test01();

CreateNDate();

TOPK();

return 0;

}

4.實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)二叉樹

用鏈表來(lái)表示一棵二叉樹，即用鏈來(lái)指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。

一般來(lái)說(shuō)，我們用的是二叉鏈表的結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

?4.1 前中后序遍歷

1）前序遍歷(Preorder Traversal 亦稱先序遍歷)：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。 訪問(wèn)順序?yàn)椋焊Y(jié)點(diǎn)、左子樹、右子樹 2）中序遍歷(Inorder Traversal)：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。 訪問(wèn)順序?yàn)椋鹤笞訕洹⒏Y(jié)點(diǎn)、右子樹 3）后序遍歷(Postorder Traversal)：訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。 訪問(wèn)順序?yàn)椋鹤笞訕洹⒂易訕?、根結(jié)點(diǎn)

4.1.1 前序遍歷

代碼實(shí)現(xiàn)如下：

void PreOrder(BTNode* root)

{

if (root == NULL)

{

return;

}

printf("%d ", root->data);

PreOrder(root->left);

PreOrder(root->right);

}

其本質(zhì)是應(yīng)用遞歸的方法。?

可以用圖像的方法來(lái)進(jìn)行驗(yàn)證，這里省略~

4.1.2 中序遍歷

代碼如下：

//中

void InOrder(BTNode* root)

{

if (root == NULL)

{

return;

}

InOrder(root->left);

printf("%d ", root->data);

InOrder(root->right);

}

4.1.3 后序遍歷

代碼如下：

//后

void PostOrder(BTNode* root)

{

if (root == NULL)

{

return;

}

PostOrder(root->left);

PostOrder(root->right);

printf("%d ", root->data);

}

4.2 結(jié)點(diǎn)個(gè)數(shù)以及高度等

實(shí)現(xiàn)下列問(wèn)題：

// 二叉樹結(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeSize(BTNode* root);

// 二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeLeafSize(BTNode* root);

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

int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉樹的深度/高度

int BinaryTreeDepth(BTNode* root);

// 二叉樹查找值為x的結(jié)點(diǎn)

BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 二叉樹銷毀

void BinaryTreeDestory(BTNode** root);

這里省略各問(wèn)題的分析（提示：均運(yùn)用遞歸的方式使得解決問(wèn)題的方法更加簡(jiǎn)便）

代碼實(shí)現(xiàn)如下：

// 二叉樹結(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeSize(BTNode* root)

{

if (root == NULL)

{

return 0;

}

return (1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right));

}

// 二叉樹葉子結(jié)點(diǎn)個(gè)數(shù),即沒(méi)有孩子結(jié)點(diǎn)的個(gè)數(shù)

int BinaryTreeLeafSize(BTNode* root)

{

if (root == NULL)

{

return 0;

}

if (root->left == NULL && root->right == NULL)

{

return 1;

}

return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);

}

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

int BinaryTreeLevelKSize(BTNode* root, int k)

{

//思路：左子樹第K層結(jié)點(diǎn)的個(gè)數(shù) + 右子樹第K層結(jié)點(diǎn)的個(gè)數(shù)

if (root == NULL)

{

return 0;

}

if (k == 1)

{

return 1;

}

return BinaryTreeLevelKSize(root->left, k - 1)

+ BinaryTreeLevelKSize(root->right, k - 1);

}

//二叉樹的深度/高度（即層數(shù)）

int BinaryTreeDepth(BTNode* root)

{

//1 + 左 + 右

if (root == NULL)

{

return 0;

}

int leftdep = BinaryTreeDepth(root->left);

int rightdep = BinaryTreeDepth(root->right);

return leftdep > rightdep ? leftdep + 1 : rightdep + 1;

}

// 二叉樹查找值為x的結(jié)點(diǎn)

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)

{

if (root == NULL)

{

return NULL;

}

if (root->data == x)

{

return root;

}

BTNode* leftFind = BinaryTreeFind(root->left, x);

if (leftFind)

{

return leftFind;

}

BTNode* rightFind = BinaryTreeFind(root->right, x);

if (rightFind)

{

return rightFind;

}

return NULL;

}

// 二叉樹銷毀

void BinaryTreeDestory(BTNode** root)

{

//先左后右，最后根結(jié)點(diǎn)

if (*root == NULL)

return;

BinaryTreeDestory(&((*root)->left));

BinaryTreeDestory(&((*root)->right));

free(*root);

*root == NULL;

}

4.3 層序遍歷

設(shè)二叉樹的根結(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根結(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹根結(jié)點(diǎn)，然后從左到右訪問(wèn)第2層上的結(jié)點(diǎn)，接著是第三層的結(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問(wèn)樹的結(jié)點(diǎn)的過(guò)就是層序遍歷。

我們借助隊(duì)列來(lái)解決。（先進(jìn)先出）

代碼實(shí)現(xiàn)如下：

//層序遍歷

void LevelOrder(BTNode* root)

{

Queue q;

QueueInit(&q);

QueuePush(&q, root);

while (!QueueEmpty(&q))

{

BTNode* top = QueueFront(&q);

printf("%d ", top->data);

//出隊(duì)

QueuePop(&q);

if (top->left)

{

QueuePush(&q, top->left);

}

if (top->right)

{

QueuePush(&q, top->right);

}

}

QueueDestroy(&q);

}

4.4 判斷是否為完全二叉樹

涉及到層，所以我們還采用隊(duì)列的方法來(lái)進(jìn)行運(yùn)算。

代碼實(shí)現(xiàn)如下：

bool BinaryTreeComplete(BTNode* root)

{

Queue q;

QueueInit(&q);

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 != NULL)

{

QueueDestroy(&q);

return false;

}

}

QueueDestroy(&q);

return true;

}

柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu)——二叉樹

http://yzkb.51969.com/

好文閱讀