樹的概念及其堆的實現
- 1.樹的概念
- 2.樹的相關概念
- 3.二叉樹的概念
- 4. 滿二叉樹和完全二叉樹
- 5.二叉樹的存儲結構
- 6.二叉樹順序結構的實現的
- 7.堆的結構及其實現
1.樹的概念
??樹是一種非線性的數據結構,它是由n(n>=0)個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。
有一個特殊的結點,稱為根結點,根節點沒有前驅結點除根節點外,其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm,其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅,可以有0個或多個后繼,因此,樹是遞歸定義的。
注意:樹形結構中,子樹之間不能有交集,否則就不是樹形結構.
2.樹的相關概念
??*節點的度:一個節點含有子樹的個數稱為該節點的度。如上圖:A的為6
??*葉節點或終端節點:度為0的節點稱為葉節點; 如上圖:B、C、H、I…等節點為葉節點
??* 非終端節點或分支節點:度不為0的節點; 如上圖:D、E、F、G…等節點為分支節點
??*孩子節點或子節點:一個節點含有的子樹的根節點稱為該節點的子節點; 如上圖:B是A的孩子節點
??* 兄弟節點:具有相同父節點的節點互稱為兄弟節點; 如上圖:B、C是兄弟節點
??* 樹的度:一棵樹中,最大的節點的度稱為樹的度; 如上圖:樹的度為6
??* 節點的層次:從根開始定義起,根為第1層,根的子節點為第2層,以此類推;
??* 樹的高度或深度:樹中節點的最大層次; 如上圖:樹的高度為4
??* 堂兄弟節點:雙親在同一層的節點互為堂兄弟;如上圖:H、I互為兄弟節點
?? * 節點的祖先:從根到該節點所經分支上的所有節點;如上圖:A是所有節點的祖先
?? * 子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖:所有節點都是A的子孫
3.二叉樹的概念
?一棵二叉樹是結點的一個有限集合,該集合:
?1.或者為空
?2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成.
從上圖可以看出:
1. 二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左右之分,次序不能顛倒,因此二叉樹是有序樹.
?注意:對于任意的二叉樹都是由以下幾種情況復合而成的:
4. 滿二叉樹和完全二叉樹
?1. 滿二叉樹:一個二叉樹,如果每一個層的結點數都達到最大值,則這個二叉樹就是滿二叉樹。也就是說,如果一個二叉樹的層數為K,且結點總數是2^k-1,則它就是滿二叉樹。
?2.完全二叉樹:完全二叉樹是效率很高的數據結構,完全二叉樹是由滿二叉而引出來的。對于深度為K的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
5.二叉樹的存儲結構
1. 順序存儲
?順序結構存儲就是使用數組來存儲,一般使用數組只適合表示完全二叉樹,因為不是完全二叉樹會有空間的浪費。而現實中使用中只有堆才會使用數組來存儲。二叉樹順序存儲在物理上是一個數組,在邏輯上是一顆二叉樹。
2. 鏈式存儲
?二叉樹的鏈式存儲結構是指,用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成,數據域和左右指針域,左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈,當前我們學習中一般都是二叉鏈。
6.二叉樹順序結構的實現的
?普通的二叉樹是不適合用數組來存儲的,因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲,需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事,一個是數據結構,一個是操作系統中管理內存的一塊區域分段。
7.堆的結構及其實現
?堆是一個完全二叉樹,用數據來實現,結構和實現的接口如下:
#define HeapDataType int
typedef struct Heap {
HeapDataType* a;
int size;
int capacity;
}Heap;
void HeapInit(Heap* php);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
HeapDataType HeapTop(Heap* php);
void HeapPop(Heap* php);
bool HeapEmpty(Heap* php);
堆初始化和堆銷毀接口如下
void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
?HeapPush接口的實現,先插入數據,再用向上調整算法,調成堆,以調成小堆為列,介紹向上調整算法。
??以滿二叉樹,插入10為例,進行調整,10是孩子,先找到父親,由于是滿二叉樹,孩子與父親的關系為:
?LeftChild = (Parent2)+1;
?RightChild = (Parent2)+2;
?Parent = (child - 1)/2;
然后,如果孩子比父親小,則交換,孩子比父親大,則成立。這兒再說一下循環怎么寫,寫循環結構就兩件事,1.寫循環體 2.寫循環條件,一定要先寫循環體,根據循環體寫循環條件,例如上面向上調整算法.
?循環體是什么?
?已經知道最后一個孩子的位置,則通過孩子算出父親位置,然后孩子與父親的大小比較,進行交換。若成立,則退出循環。盡管做這樣一件事情,那什么時候結束,孩子走到頭,父親沒有了,就結束,很自然就找到循環條件。
?具體代碼如下:
void Swap(HeapDataType* px, HeapDataType* py)
{HeapDataType tmp = *px;*px = *py;*py = tmp;
}void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapPush(Heap* php, HeapDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
?寫接口獲得堆頂數據,堆的刪除。
?堆的刪除,首先堆頭和堆位進行交換,然后向下調整,調整成堆。
?首先,把10和28交換,交換之后,把堆頂元素10刪除,把在0位置的28這個元素,向下調整成堆,具體就是找孩子中兩個較小的一個跟父親比較,進行交換,父親走到頭,循環結束,這是孩子已經越界,用孩子來寫循環條件。
?代碼如下。
void AdjustDown(HeapDataType* a, int parent, int n)
{int child = (parent * 2) + 1;if (a[child] > a[child + 1] && child+1<n){child += 1;}while (child<n){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;if (a[child] > a[child + 1] && child + 1 < n){child += 1;}}else{break;}}
}void HeapPop(Heap* php)
{assert(php);assert(php->a);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
?判空很簡單
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}
?完結!