數據結構入門————樹（C語言/零基礎/小白/新手+模擬實現+例題講解）

1. 樹的概念及其結構

? ? ? ? 1.1 樹的概念：

? ? ? ? 1.2 樹的相關概念：

? ? ? ? 1.3 樹的表示方法：

?編輯

? ? ? ? 1.4 樹的應用：

2. 二叉樹的概念及其結構????????

? ? ? ? 2.1 概念:

? ? ? ? 2.2 特點：

? ? ? ? 2.3 特殊二叉樹：

? ? ? ? 2.4 二叉樹的性質：

3. 二叉樹的順序存儲結構?

? ? ? ? 3.1 二叉樹的順序存儲結構

? ? ? ? 3.2 堆的概念及其結構

? ? ? ? 3.3 堆的實現

4. 二叉樹的鏈式存儲

? ? ? ? 4.1 前序，中序，后序遍歷

? ? ? ? 4.2 層序遍歷

1. 樹的概念及其結構

? ? ? ? 1.1 樹的概念：

? ? ? ? 樹（Tree）是n（n>=0）個結點的有限集。n=0時稱為空樹。在任意一棵非空樹中：1.有且僅有一個特定的稱為根(Root)的結點；2.當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2...，Tm，其中每一個集合本身又是一顆樹，稱為根的子樹（Sub Tree）,如下圖所示。

注：

? ? ? ? 1. 子樹是不相交的。

? ? ? ? 2. 除了根節點以外，每個節點有且只有一個父節點

? ? ? ? 3. 一棵有N個節點的樹有N-1條邊。

? ? ? ? 1.2 樹的相關概念：

? ? ?a.結點的分類

????????結點的度：結點擁有的子樹的個數。例如，A的度為6。

? ? ? ? 樹的度：最大結點的度為樹的度。例如，上圖結點的度為6,。

? ? ? ? 葉結點/終端結點：度為0的結點。例如，結點B。

? ? ? ?非終端結點/分支結點：度不為0的結點。例如，結點D,E....

? ? b.結點的關系

? ? ? ? 雙親結點/父結點：若一個結點含有子結點，那么該結點就是父結點。例如,A是B的父結點。

? ? ? ? 孩子結點/子結點：結點子樹的根稱為該結點的孩子(Child)。例如,B是A的孩子。

? ? ? ? 兄弟結點：具有相同父結點的結點稱為兄弟結點。例如,B和C是兄弟結點。

????????堂兄弟結點：雙親在同一層的結點稱為堂兄弟結點。例如,H和I是堂兄弟結點。

? ? ? ? 結點的祖先：從根結點到該結點的分支上的所有結點，稱為該結點的祖先。例如，A時所有結點的祖先

? ? ? ? 子孫：以某結點為根的子樹中的任意結點都是該結點的子孫，例如，所有結點都是A的子孫。

? ? c.樹的相關概念

? ? ? ? 結點的層次：從根結點開始定義，根結點為第1層，根結點的子結點為第2層，以此類推。

? ? ? ? 樹的高度或深度：樹中結點的最大層次。上圖，樹的高度為4。

? ? ? ? 森林：由m棵互不相交的樹的集合稱為森林。

? ? ? ? 1.3 樹的表示方法：

? ? ? ? ? ? ? ? 這里我們簡單了解一下比較常用的：孩子兄弟表示法。

typedef int DataType;
struct Node
{struct Node*  LeftChild;    // 指向左邊第一個孩子節點struct Node*  RightBrather; // 指向右邊的兄弟節點DataType _data; // 結點中的數據域
};

? ? ? ? 1.4 樹的應用：

? ? ? ? ? ? ? ? 我們在Linux系統中（操作系統的一種），使用的目錄結構就是樹狀結構。

2. 二叉樹的概念及其結構????????

? ? ? ? 2.1 概念:

? ? ? ? ? ? ? ? 二叉樹（Binary Tree）是n(n>=0)個結點的有限集，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的，分別稱為根結點的左子樹和右子樹的二叉樹組成。

? ? ? ? 2.2 特點：

? ? ? ? ? ? ? ? a. 二叉樹不存在度大于2的結點。

? ? ? ? ? ? ? ? b. 二叉樹有左子樹右子樹之分，是有順序的，不能顛倒，即使只有一棵子樹，也要區分左子樹還是右子樹。

? ? ? ? 2.3 特殊二叉樹：

? ? ? ? ? ? ? ? a. 滿二叉樹：一個二叉樹，每一層的結點數都達到最大值，則這個二叉樹稱為滿二叉樹。也就是說，如果一個滿二叉樹一共有h層，那么它的結點個數為 2^h-1。

? ? ? ? ? ? ? ? b. 完全二叉樹：前h-1層結點數都達到最大值，最后一層不一定是滿的，但一定從左往右有序。滿二叉樹是一個特殊的完全二叉樹。

? ? ? ? 2.4 二叉樹的性質：

? ? ? ? ? ? ? ? 1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^( i - 1 ) 個節點。?

? ? ? ? ? ? ? ? 2. 若規定根節點的層數為1，則深度為h的二叉樹的最大節點數是 2^( h )? - 1 。

? ? ? ? ? ? ? ? 3. 對任何一棵二叉樹，度為0的葉子節點個數為n0，度為2的分支節點個數為n2，則有n0 = n2 + 1。

? ? ? ? ? ? ? ? 4. 若貴定根節點的層數為1，具有n個節點的滿二叉樹的深度，h = log?(n + 1)。

? ? ? ? ? ? ? ? 5. 對具有n個節點的完全二叉樹，如果按照從上到下從左至右的數組順序對所有節點開始編號，嘖對于序號為i的節點有：

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

? ? ? ? ? ? ? ? b. 若2 * i + 1 < n,左孩子序號： 2 * i + 1，若 2 * i + 1 >= n ,則無左孩子節點。

? ? ? ? ? ? ? ? c. 若2 * i + 2 < n,右孩子序號： 2 * i + 2，若 2 * i + 1 >= n,則無右孩子節點。?

1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ B ）

A 不存在這樣的二叉樹

B 200

C 198

D 199

解析：

葉子節點：度為0的節點，n0 = n2 +1

2. 在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ A ）

A n

B n+1

C n-1

D n/2

解析：

完全二叉樹的節點度分為3種情況：度=1 or 度 =2 or 度 = 0；

2n = n0 + n1 + n2

n0 = n2 + 1 ,且 n1 = 0 或 n1 =0

2n0 + n1 = 2n? ? 這里 n1只能為0 （偶數 + 奇數? !=? 偶數）

所以葉子節點個數 = n

4.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ B ）

A 11

B 10

C 8

D 12

解析：

滿二叉樹的節點個數 = 2*h -1

完全二叉樹中，葉子節點個數不確定，區間為：[ 2^( h - 1 ) + 1 ,?2^( h ) -1 ]

將選項代入，得出高度為10

5.在一顆度為3的樹中，度為3的結點有2個，度為2的結點有1個，度為1的結點有2個，則葉子結點有（ ?C ）個

A.4

B.5

C.6

D.7

解析：

? ? ? ? 度為i的節點為ni，樹的節點個數為n,則 n = n0 + n1 + n2 + n3;

? ? ? ? 有n個節點的樹的總邊數為： n-1 條。

? ? ? ? 根據度的定義，總邊數與度的關系: n -1 = 0 * n0 + 1 * n1 + 2 * n2 + 3 *?n3

? ? ? ? 聯立方程可得，n0 = n2 +2 *n3 +1 , n0 = 6

3. 二叉樹的順序存儲結構?

? ? ? ? 3.1 二叉樹的順序存儲結構

? ? ? ? ? ? ? ? 普通的二叉樹不適合用順序存儲結構，會造成大量空間浪費，但完全二叉樹適合用順序存儲結構，現實中我們常把堆（一種二叉樹）使用順序結構存儲。

? ? ? ? 3.2 堆的概念及其結構

????????堆中某個節點的值總是不大于或不小于其父節點的值；

????????堆總是一棵完全二叉樹。

? ? ? ? 3.3 堆的實現

//Heap.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity; 
}Heap;// 堆的構建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂的數據
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

#include "Heap.h"void Swap(HPDataType* x1, HPDataType* x2)
{HPDataType x = *x1;*x1 = *x2;*x2 = x;
}void AdjustDown(HPDataType* a, int n, int root)
{int parent = root;int child = parent*2+1;while (child < n){// 選左右孩紙中大的一個if (child+1 < n && a[child+1] > a[child]){++child;}//如果孩子大于父親，進行調整交換 if(a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2+1;}else{break;}}
}void AdjustUp(HPDataType* a, int n, int child)
{int parent;assert(a);parent = (child-1)/2;//while (parent >= 0)while (child > 0){//如果孩子大于父親，進行交換if (a[child] > a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (child-1)/2;}else{break;}}
}void HeapInit(Heap* hp, HPDataType* a, int n)
{int i;assert(hp && a);hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);hp->_size = n;hp->_capacity = n;for (i = 0; i < n; ++i){hp->_a[i] = a[i];}// 建堆： 從最后一個非葉子節點開始進行調整// 最后一個非葉子節點，按照規則： （最后一個位置索引 - 1） / 2// 最后一個位置索引： n - 1// 故最后一個非葉子節點位置： (n - 2) / 2for(i = (n-2)/2; i >= 0; --i){AdjustDown(hp->_a, hp->_size, i);}
}void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_size = hp->_capacity = 0;
}void HeapPush(Heap* hp, HPDataType x)
{assert(hp);//檢查容量if (hp->_size == hp->_capacity){hp->_capacity *= 2;hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*hp->_capacity);}//尾插hp->_a[hp->_size] = x;hp->_size++;//向上調整AdjustUp(hp->_a, hp->_size, hp->_size-1);
}void HeapPop(Heap* hp)
{assert(hp);//交換Swap(&hp->_a[0], &hp->_a[hp->_size-1]);hp->_size--;//向下調整AdjustDown(hp->_a, hp->_size, 0);
}HPDataType HeapTop(Heap* hp)
{assert(hp);return hp->_a[0];
}int HeapSize(Heap* hp)
{return hp->_size;
}int HeapEmpty(Heap* hp)
{return hp->_size == 0 ? 0 : 1;
}void HeapPrint(Heap* hp)
{int i;for (i = 0; i < hp->_size; ++i){printf("%d ", hp->_a[i]);}printf("\n");
}

????????

4. 二叉樹的鏈式存儲

? ? ? ? 先來簡單復習一下二叉樹的概念，二叉樹是：

? ? ? ? 1. 空樹

? ? ? ? 2.非空：根節點，左子樹，右子樹組成

? ? ? ? 從概念中可以看出，二叉樹的定義是遞歸式的，因此后續基本操作都是按照該概念實現的。

? ? ? ? 4.1 前序，中序，后序遍歷

? ? ? ? ? ? ? ? 二叉樹遍歷是按照某種特定的規則，依次對二叉樹的節點進行相應的操作，并且每個節點只操作1次。

? ? ? ? ? ? ? ? 按照規則，二叉樹的遍歷有：前序/中序/后序的遞歸結構遍歷：

?1. 前序遍歷（Preorder Traversal）:訪問根節點的操作發生在遍歷其左右子樹之前。

?2. 后序遍歷（Postorder Traversal）:訪問根節點發生在遍歷其左右子樹之后。

?3. 中序遍歷（Inorder Traversal）:訪問根節點的操作發生在遍歷其左右子樹之間。

? ? ? ? 4.2 層序遍歷

?層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

? ? ? ? ? ? ? ? 層序遍歷中，我們使用隊列來實現，但因為C語言的局限性，需要自己創建輪子，所以實現起來比較復雜，這里如果你對隊列不太熟悉，可以參考下面這篇文章，幫助你更好的理解。

????????

? ? ? ?數據結構入門————棧和隊列（C語言/零基礎/小白/新手+模擬實現+例題講解）

//Tree.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;// 通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);

#include "BTree.h"
#include "queue.h" //參考之前的代碼
#include "stack.h"BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi)
{if (*pi >= n || src[*pi] == '#'){(*pi)++;return NULL;}BTNode * cur = (BTNode *)malloc(sizeof(BTNode));cur->_data = src[*pi];(*pi)++;cur->_left = BinaryTreeCreate(src, n, pi);cur->_right = BinaryTreeCreate(src, n, pi);return cur;
}void BinaryTreePrevOrder(BTNode* root)
{if (root){ putchar(root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}
}void BinaryTreeInOrder(BTNode* root)
{if (root){BinaryTreeInOrder(root->_left);putchar(root->_data);BinaryTreeInOrder(root->_right);}
}void BinaryTreePostOrder(BTNode* root)
{if (root){BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);putchar(root->_data);}
}void BinaryTreeDestory(BTNode** root)
{if (*root){BinaryTreeDestory(&(*root)->_left);BinaryTreeDestory(&(*root)->_right);free(*root);*root = NULL;}
}void BinaryTreeLevelOrder(BTNode* root)
{Queue qu;BTNode * cur;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_left){QueuePush(&qu, cur->_left);}if (cur->_right){QueuePush(&qu, cur->_right);}QueuePop(&qu);}QueueDestory(&qu);
}int BinaryTreeComplete(BTNode* root)
{Queue qu;BTNode * cur;int tag = 0;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_right && !cur->_left){return 0;}if (tag && (cur->_right || cur->_left)){return 0;}if (cur->_left){QueuePush(&qu, cur->_left);}if (cur->_right){QueuePush(&qu, cur->_right);}else{tag = 1;}QueuePop(&qu);}QueueDestory(&qu);return 1;
}