柚子快報邀請碼778899分享：數(shù)據(jù)結構——二叉樹

http://yzkb.51969.com/

1.樹

樹是一種非線性的數(shù)據(jù)結構，它是由 n 個有限結點組成的一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹。

——有一個特殊的結點，稱為根結點，根節(jié)點沒有前驅結點。

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

——樹形結構中，?樹之間不能有交集，否則就不是樹形結構。

?例如：

（注：該圖片來自于百度）

1.1 各種概念

——父結點/雙親結點：若?個結點含有?結點，則這個結點稱為其?結點的?結點。

——子結點/孩子結點：?個結點含有的?樹的根結點稱為該結點的?結點。

——結點的度：有幾個孩子，就為幾度。

——樹的度：最大結點的度就為樹的度。

——葉子結點/終端結點：度為0的結點就為葉子結點。

——分支結點/非終端結點：度不為0的結點。

——兄弟結點：具有相同的父結點。

——結點的層次：有幾層層次就為多少。

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

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

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

——子孫：以某結點為根的?樹中任?結點都稱為該結點的?孫。

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

1.2 樹的表示

用孩子兄弟表示法：

struct TreeNode

{

struct Node* child; //左邊開始的第一個孩子的結點

struct Node* brother; //指向其右邊的下一個兄弟結點

int data; //結點中的數(shù)據(jù)域

};

用圖片來進行分析：

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

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

1.3 應用

?件系統(tǒng)是計算機存儲和管理?件的?種?式，它利?樹形結構來組織和管理?件和?件夾。在?件系統(tǒng)中，樹結構被?泛應?，它通過?結點和?結點之間的關系來表?不同層級的?件和?件夾之間的關聯(lián)。

2.二叉樹

2.1 概念與結構

二叉樹是樹形結構的一種。

一棵二叉樹是結點的一個有限集合，該集合由一個根結點加上兩棵別稱為左子樹和右子樹的二叉樹組成。

例如：

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

二叉樹的特點：

——二叉樹不存在度大于2的結點

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

2.2 特殊的二叉樹

2.2.1 滿二叉樹

每一層的結點都達到最大值，則這個二叉樹就是滿二叉樹。結點的總數(shù)就是?2^k - 1

（注：圖片來自于百度）

2.2.2 完全二叉樹

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

例如：

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

則該結構的特點是：假設二叉樹的層次為K層，則除了第K層外，每層結點的個數(shù)達到最大結點數(shù)，第K層不一定達到最大結點數(shù)。

且完全二叉樹結點的順序是從左到右順序放置的。

2.3 二叉樹的存儲結構

二叉樹一般可以使用兩種結構存儲：一種是順序結構，一種是鏈式結構。

2.3.1 順序結構

順序結構是使用數(shù)組來進行存儲的，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，完全二叉樹使用順序結構進行存儲。

2.3.2 鏈式結構

?叉樹的鏈式存儲結構是指，?鏈表來表??棵?叉樹，即?鏈來指?元素的邏輯關系。 通常的?法是鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別?來給出該結點左孩?和右孩?所在的鏈結點的存儲地址 。鏈式結構?分為?叉鏈和三叉鏈，當前我們學習中?般都是?叉鏈。后?課程學到?階數(shù)據(jù)結構如紅?樹等會?到三叉鏈。

3.實現(xiàn)順序結構二叉樹

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

3.1 堆的概念與結構

分為小跟堆和大根堆，我們通過圖片來進行了解：

堆具有以下的性質：

——堆中某個結點的值總是不大于或者不小于其父結點的值

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

二叉樹的性質：

對于具有n個結點的完全二叉樹，如果按照從上至下、從左至右的數(shù)組順序對所有結點從0開始編號（例如上述的圖片），則對于序號為i的結點有：

?1）若i > 0 , i 位置結點的雙親序號為：( i - 1 ) / 2 ；i = 0， i為根結點編號，無雙親編號。

?2）若2i + 1 < n，左孩子序號：2i + 1，2i + 1 >= n，否則無左孩子。

?3）若2i + 2 < n，右孩子序號：2i + 2，2i + 2 >= n，否則無右孩子。

3.2 堆的實現(xiàn)

3.2.1 堆的初始化與銷毀

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

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

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

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

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只要走到了根結點的位置，根結點不需要交換了

{

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)

{

//擴容

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ù)根最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進行向下調(diào)整算法。

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

代碼如下：

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

{

int child = parent * 2 + 1;

while (child < n)

{

//找左右孩子中最小的那一個

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 堆的應用---TOP-K問題

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

當數(shù)據(jù)量太大的時候，就不能用排序的方法，這時，我們可以用堆來解決問題。

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

代碼實現(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("請輸入K:");

scanf("%d", &k);

//從文件中讀取前K個數(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.實現(xiàn)鏈式結構二叉樹

用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。

一般來說，我們用的是二叉鏈表的結構來實現(xiàn)的。

?4.1 前中后序遍歷

1）前序遍歷(Preorder Traversal 亦稱先序遍歷)：訪問根結點的操作發(fā)生在遍歷其左右子樹之前。 訪問順序為：根結點、左子樹、右子樹 2）中序遍歷(Inorder Traversal)：訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。 訪問順序為：左子樹、根結點、右子樹 3）后序遍歷(Postorder Traversal)：訪問根結點的操作發(fā)生在遍歷其左右子樹之后。 訪問順序為：左子樹、右子樹、根結點

4.1.1 前序遍歷

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

void PreOrder(BTNode* root)

{

if (root == NULL)

{

return;

}

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

PreOrder(root->left);

PreOrder(root->right);

}

其本質是應用遞歸的方法。?

可以用圖像的方法來進行驗證，這里省略~

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 結點個數(shù)以及高度等

實現(xiàn)下列問題：

// 二叉樹結點個數(shù)

int BinaryTreeSize(BTNode* root);

// 二叉樹葉子結點個數(shù)

int BinaryTreeLeafSize(BTNode* root);

// 二叉樹第k層結點個數(shù)

int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉樹的深度/高度

int BinaryTreeDepth(BTNode* root);

// 二叉樹查找值為x的結點

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

// 二叉樹銷毀

void BinaryTreeDestory(BTNode** root);

這里省略各問題的分析（提示：均運用遞歸的方式使得解決問題的方法更加簡便）

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

// 二叉樹結點個數(shù)

int BinaryTreeSize(BTNode* root)

{

if (root == NULL)

{

return 0;

}

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

}

// 二叉樹葉子結點個數(shù),即沒有孩子結點的個數(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層結點個數(shù)

int BinaryTreeLevelKSize(BTNode* root, int k)

{

//思路：左子樹第K層結點的個數(shù) + 右子樹第K層結點的個數(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的結點

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)

{

//先左后右，最后根結點

if (*root == NULL)

return;

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

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

free(*root);

*root == NULL;

}

4.3 層序遍歷

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

我們借助隊列來解決。（先進先出）

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

//層序遍歷

void LevelOrder(BTNode* root)

{

Queue q;

QueueInit(&q);

QueuePush(&q, root);

while (!QueueEmpty(&q))

{

BTNode* top = QueueFront(&q);

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

//出隊

QueuePop(&q);

if (top->left)

{

QueuePush(&q, top->left);

}

if (top->right)

{

QueuePush(&q, top->right);

}

}

QueueDestroy(&q);

}

4.4 判斷是否為完全二叉樹

涉及到層，所以我們還采用隊列的方法來進行運算。

代碼實現(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;

}

柚子快報邀請碼778899分享：數(shù)據(jù)結構——二叉樹

http://yzkb.51969.com/

好文閱讀