神奇的樹
- 引言---樹的故事
- 樹的基本性質和描述
- 樹的基本特點
- 樹的關鍵字決議
- 樹的表示方法
- 二叉樹的概念結構
- 特殊二叉樹
- 二叉樹的性質
- 二叉樹的存盤結構
- 二叉樹與堆
- 堆的實作
- 堆排序
- 堆的功能實作
- 堆的插入
- TOPK問題
- 二叉樹的結構以及實作
- 二叉樹的遍歷
- 代碼實作
- 程式實作方法 以及遞回小技巧
引言—樹的故事
在自然界中有很多樹 它們是這樣的
但是在我們的眼中 他是這樣的
顯而易見 樹的特點就是一對多 ，我們利用這個一對多的特點，可以讓我們更好的解決編程中的問題，在樹中 ，最基礎的二叉樹是我們的重點研究物件，
在看一眼神奇的堆排序的動態圖
做事情，先求對，在求巧，一步一步才可有所成就，所以讓我們從基礎開始吧！
樹的基本性質和描述
樹是一個一對多的特殊資料型別，樹的根在上 葉子在上 ，有種一生二，二生三，三生萬物的感覺，
樹的基本特點
-
樹有且只有一個根，且根沒有后繼結點，
-
樹是互不相交的
ps： 圖可知 不構成閉合回路則不相交， -
每一個結點可在分為一個子樹，
-
樹的定義是一個遞回定義，即樹在定義時又會用到樹的概念，他道出了樹的固有特性，
樹的關鍵字決議
樹有一大段關鍵字很讓人頭疼
結點的分類：
ps：
- 結點的度： 結點擁有的子樹數稱為結點的度，度為0的點成為葉節點或終端結點，度不為0的節點稱為非終端結點，樹的度是樹內各個結點的最大值，此圖 D為最大的結點，
- 結點的層次：從根開始為第一層，依次遞增
簡單對比 樹形結構與線性結構：
樹的表示方法
- 雙親表示法
typedef struct
{
int data;
int parent; // 雙親位置
}PtNode;
typedef struct
{
PtNode nodes[10];
int root ;
int n;
}PTree;
此圖數字表示父親的結點
通過“父親的下標”即可找到父親的位置
注：
-
找雙親時間復雜度 O(1);找結點兒子需要遍歷樹
-
資料的增刪查改，
-
左孩子右兄弟
typedef struct CSNode
{
int data;
struct CSNode* firstchild, * rightsib;
};
左孩子右兄弟的方式就是 多一個指標 一個指標指向自己最左側的孩子 另一個指標指向自己右側兄弟
這種表示法是我們常用的表示法，
二叉樹的概念結構
二叉樹
二叉樹是一種特殊的樹，他的特點是一個根節點兩個子節點，這兩個子節點又分別叫做左子樹和右子樹，
注意
- 二叉樹的度不超過二
- 二叉樹左右子樹不可顛倒
- 二叉樹有且只有一個子樹時，也需要區分左右，
特殊二叉樹
滿二叉樹
一個二叉樹每一層都是滿的，那么這個二叉樹就是滿二叉樹，如果一個二叉樹的層數為k，且結點總數是（2^k）-1
完全二叉樹
一個完全二叉樹的前k層都是滿的第k層可以不滿 ，但是必須連續，及滿足先左后右，
注意
- 滿二叉樹一定是完全二叉樹，反之就不對，
- 完全二叉樹一定是先左后右，如下圖則不對
- 完全二叉樹葉子的結點都在最后兩層，左側集中最后第k層的葉子，右側集中第k-1層的葉子
二叉樹的性質
-
在二叉樹的第i層上至多有2^(i-1)的結點i>0
-
深度為k的二叉樹至多有2^k-1個結點
-
對任何一個二叉樹T，如果其終端結點樹為n0，度為2的結點樹為n2則no=n2+1；
-
具有n個結點的完全二叉樹的深度為log2(n)+1
-
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序從0開始編號，則對與序號為i的結點有：
1. 若i>0,i位置結點的雙親序號為(i-1)/2；
2. 若2i+1<n,左孩子序號：2i+1,2i+1>=n則無左孩子
3. 若2i+2<n,右孩子序號；2i+2,2i+2>=n則無有孩子假設父親的結點序號為parent，左孩子為leftchild，右孩子為ringhtchild， 有： leftchild=parent*2+1 rightchild=parent*2+2
e~g
- 在具有2n個結點的完全二叉樹中，葉子的結點個數為
解 在完全二叉樹中有且只有3種情況
-
度為0
度為0，即只有根結點 葉子的結點個數也為n -
有且只有一個度為1的結點
設 x等于讀為2的結點數 ，y等于葉子節點數 x+y+1=2n 又由葉子數等于度為2的加1得 y=x+1
得 y=n -
沒有度為1的結點
由圖可知 顯然不能構成偶數個結點 故舍棄，
綜上所述：葉子節點個數為n
一個具有完全二叉樹的節點數為531個，那么這棵樹的高度是
解： 直接帶公式得 10；
一個具有767個結點的完全二叉樹，其葉子節點個數為，
解 由前面的結論可知 此二叉樹必定是
所以 設雙結點為x 葉子為y y=x+1 且 y+y-1=767 解得 y=384
一顆度為2的樹和二叉樹有什么區別
解：
- 度為2的樹是無序樹 不區分左右 ，而二叉樹必須先左后右，
- 度為2的樹 一定有一個結點度為2，二叉樹可以沒有
證明 一個滿k叉樹上的葉子結點數n0和非葉子結點數n1瞞住*n0=(k-1)n1+1
首先，我們知道了滿二叉樹 ，滿k叉樹就是第n層以上的所有個結點的度都為k
總分支結點數=k倍的n1
總結點數=n0+n1
總分支結點數+1=總結點數
kn1+1=no+n1
二叉樹的存盤結構
二叉樹的存盤是按照自上而下，從左往右的排序的
如果將該二叉樹存入陣列中 就會得到
二叉樹與堆
堆是一種特殊的數，即是完全二叉樹，
觀察這個樹 他的父結點都小于子結點，我們稱之為最小堆，反之如果所有的父結點都比子結點大，這樣的完全二叉樹就被成為最大堆
注意：
- 堆是一顆完全二叉樹
- 堆只有大堆和小堆兩種
- 每個子樹都是堆
堆的實作
有如下陣列
int arr[] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
如何將其調整成最小堆呢？
由圖可知，最小堆的特點就是父親小于兒子 ，而此樹圈起來的地方兒子大于父親，所以我們需要把最小的兒子換上去，
換下來后 我們發現還是不滿足 所以還得交換
畫圈處該二叉樹任然不滿足 只需要在交換一次，便是最小堆了
此時二叉樹滿足了最小堆，
此程序的演算法，我們稱之為向下調整演算法，如果我們將一顆二叉樹磁區 即
向下調整的本質就是先滿足上面的，在滿足下面的
注意：
- 向下調整演算法，被調整元素的左右字樹都必須是最小堆，
- 向下調整演算法，調整到葉子結點時，即可停止
- 如果小的孩子比父親打，則不需要處理，整個樹已經是最小堆，
附上代碼
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;//套用公式可得
while (child < n)
{
if (child+1<n&&a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
AdjustDown(arr, n, 0);
return 0;
}
代碼解讀
那么更一般的情況 左右子樹都不是小堆的情況 ，怎么調整呢？
我們只需自下而上，由小的堆樹變成大的堆樹
即是 先滿足下面在滿足上面
先滿足下面的堆 在滿足上面 那么 只需要給函式依次傳進去所有的父親結點即可
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<=n && a[child] >a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
return 0;
}
堆排序
以升序為例 ，我們首先會想到小堆 但是 小堆不適合，我們看
我們知道 堆頂元素一定是最小的 那么我們只需要依次拿走堆頂
當我們拿走2 后 7成了堆頂 之后
當去掉堆頂后 下一個元素補上 小堆蕩然無存，順序全亂了 ，所以，小堆不適合排升序，
大堆排升序又該怎么辦呢？
此時 ，我們只需要把10和80互換，不把80考慮在堆內
那么代碼實作又當如何呢？
附上整體代碼
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<n && a[child] <a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n =14 ;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int end = n - 1;
while (end > 0)
{
int tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
AdjustDown(arr, end, 0);
end--;
}
return 0;
}
堆排序是一種高效的排序
堆的總結：
- 物理結構是一個陣列
- 邏輯結構是完全二叉樹
- 大堆與小堆關系
- 堆排序
- 插入元素
- 快速找出最大或最小
堆的功能實作
堆的插入
堆的插入，要求插入之后還是堆， 這里我們引入堆的向上調整
那么代碼如何實作呢？ 和向下排序類似
附上代碼
void AdjustUp(int* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
插入元素后經過一次向上排序即可，
也可以使用向下排序 但麻煩許多，
TOPK問題
TopK問題的本質就是取小堆取頂操作 建堆 ，然后取頂，甚至你可以說就是一個排順序，把前四個放進別的陣列，但是排序就意味著時間復雜度的加重 ， 請讀者使用建堆知識，取堆頂資料的方式，拿到最小資料， 這里給出題目和答案
* Note: The returned array must be malloced, assume caller calls free().
*/
/* 交換 */
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
/* 從堆下層向上交換元素，使得堆為大根堆 */
void swim(int* nums, int k) {
while (k > 1 && nums[k] > nums[k / 2]) {
swap(&nums[k], &nums[k / 2]);
k /= 2;
}
}
/* 從堆上層向下層交換元素，使得堆為大根堆 */
void sink(int* nums, int k, int numsSize) {
while (2 * k < numsSize) {
int child = 2 * k;
if (child < numsSize && nums[child] < nums[child + 1]) {
child++;
}
if (nums[k] > nums[child]) {
break;
}
swap(&nums[k], &nums[child]);
k = child;
}
}
/* 定義堆的結構體 */
typedef struct Heap {
int* data;
int szie;
int capacity;
}T_Heap, *PT_Heap;
/* 初始化一個堆 */
PT_Heap createHeap(int k) {
PT_Heap obj = (PT_Heap)malloc(sizeof(T_Heap));
obj->data = (int*)malloc(sizeof(int) * (k + 1));
obj->szie = 0;
obj->capacity = k + 1;
return obj;
}
/* 判斷堆是否為空 */
bool isEmpty(PT_Heap obj) {
return obj->szie == 0;
}
/* 獲得堆的當前大小 */
int getHeapSize(PT_Heap obj) {
return obj->szie;
}
/* 將元素入堆 */
void pushHeap(PT_Heap obj, int elem) {
/* 新加入的元素放入堆的最后 */
obj->data[++obj->szie] = elem;
/* 對當前堆進行排序,使其成為一個大根堆 */
swim(obj->data, obj->szie);
}
/* 獲得堆頂元素 */
int getHeapTop(PT_Heap obj) {
return obj->data[1];
}
/* 將堆頂元素出堆 */
int popHeap(PT_Heap obj) {
/* 保存堆頂元素 */
int top = obj->data[1];
/* 將堆頂元素和堆底元素交換,同時堆長度減一 */
swap(&obj->data[1], &obj->data[obj->szie--]);
/* 將原先的堆底元素賦值為INT_MIN */
obj->data[obj->szie + 1] = INT_MIN;
/* 從堆頂開始重新堆化 */
sink(obj->data, 1, obj->szie);
return top;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
/* 若陣列為空、或k為0，回傳NULL */
if (arrSize == 0 || k == 0) {
*returnSize = 0;
return NULL;
} else {
*returnSize = k;
}
/* 回傳陣列長度為k */
int* ret = (int*)calloc(k, sizeof(int));
/* 初始化一個大小為k的堆 */
PT_Heap heap = createHeap(k);
/* 將輸入陣列前k個元素堆化 */
for (int i = 0; i < k; i++) {
pushHeap(heap, arr[i]);
}
/* 將輸入陣列剩下的元素依次插入堆，得出最小的k個數 */
for (int i = k; i < arrSize; i++) {
if (arr[i] < getHeapTop(heap)) {
popHeap(heap);
pushHeap(heap, arr[i]);
}
}
/* 將堆中元素傳入回傳陣列 */
for (int i = 0; i < k; i++) {
ret[i] = popHeap(heap);
}
return ret;
}
二叉樹的結構以及實作
二叉樹的遍歷
-
先序遍歷
若二叉樹為空，則空操作；否則
訪問根節點；
先序遍歷左子樹
先序遍歷右子樹； -
中序遍歷
若二叉樹為空，則空操作；否則
中序遍歷左子樹
訪問根節點；
中序遍歷右子樹；
- 后序遍歷
后序遍歷左子樹
后序遍歷右子樹；
訪問根節點；
代碼實作
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf(" NULL ");
return;
}
printf(" %c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL");
return;
}
InOrder(root->left);
printf(" %c ", root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
const BTNode* a = root;
if (root == NULL)
{
printf(" NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf(" %c ", root->data);
}
程式實作方法 以及遞回小技巧
- 遞回先確定你要遞回的函式的功能 比如：他回傳什么，他傳入什么，他干了什么
- 分情況討論 盡可能分清楚，
- 設計好函式出口
以本題為例
只要這三行代碼 順序變化 那么遍歷方式也變化，這是為什么呢，
首先 函式的出口為root為空 而PostOrder(root->left);則是一直往左子樹方向走，走到什么時候進行下一句呢？ 走到底，走到底之后 就如圖
此時根據函式出口，return ； 回回到上一層 如圖
此時進入 PostOrder(root->right); 如圖
此時又滿足了 函式出口 回傳上一層 回到 19 往下走 列印 如此往復 我們得出結論，遍歷只需要換即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286195.html
標籤：AI