數(shù)據(jù)結(jié)構(gòu)04-樹

4：樹（QUEUE）

樹.png

4.1：樹的定義和性質(zhì)

1. 樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu);
2. 樹是由一個或多個結(jié)點組成的有限集合;

樹必有一個特定的稱為根(ROOT)的結(jié)點；

剩下的結(jié)點被分成ｎ>=0個互不相交的集合T1、T2姆坚、......Tn，而且性湿， 這些集合的每一個又都是樹纬傲。樹T1、T2窘奏、......Tn被稱作根的子樹(Subtree)嘹锁。

樹的遞歸定義如下：
1. 至少有一個結(jié)點（稱為根）
2. 其它是互不相交的子樹。

樹的度：結(jié)點的最大分支數(shù)着裹。以組成該樹各結(jié)點中最大的度作為該樹的度;

樹中度為零的結(jié)點稱為葉結(jié)點或終端結(jié)點。樹中度不為零的結(jié)點稱為分枝結(jié)點或非終端結(jié)點米同。除根結(jié)點外的分枝結(jié)點統(tǒng)稱為內(nèi)部結(jié)點骇扇。

樹的深度：組成該樹各結(jié)點的最大層次，從1開始計數(shù)面粮；

有序樹：指樹中同層結(jié)點從左到右有次序排列少孝，它們之間的次序不能互換，這樣的樹稱為有序樹熬苍，否則稱為無序樹稍走。

二叉樹：每個節(jié)點至多只有兩棵子樹，度不能大于2柴底，并且二叉樹的子樹有左右之分婿脸，左右次序不能改變。

image.png

二叉樹五種基本形態(tài)(如上圖 依次分別為)：

1. 空二叉樹
2. 只有一個根節(jié)點的二叉樹
3. 只有左子樹
4. 只有右子樹
5. 完全二叉樹

image.png

1. 滿二叉樹：一顆深度為K且有2^(k-1)個結(jié)點的二叉樹.
2. 完全二叉樹：對二叉樹的結(jié)點進行連續(xù)編號柄驻，約定編號從根節(jié)點起狐树，自上而下，自左至右鸿脓。深度為k抑钟，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)

二叉樹的第i層上至多有2^i-1個結(jié)點(i>=1)

深度為k的二叉樹至多有2^k-1個結(jié)點(k>=1)

具有n個結(jié)點的完全二叉樹的深度為：

image

4.1：樹的創(chuàng)建

//二叉樹存儲結(jié)構(gòu)
typedef struct _treeNode {
    int value;
    struct _treeNode *left;
    struct _treeNode *right;
} tree, *pTree;

//二叉樹的創(chuàng)建,遞歸創(chuàng)建
tree *creat_tree() {
    int value = 0;
    scanf("%d", &value);
    
    if (value == 0)//輸入零野哭，表示左或右子樹為空
        return NULL;
    
    tree *node = (tree *)malloc(sizeof(tree));
    
    if (node == NULL) 
        return NULL;
        
    memset(node, 0, sizeof(tree));
    node->value = value;
     
    //遞歸創(chuàng)建左右子樹
    printf("Please create the left tree of %d\n",value);
    node->left = create_tree();
    printf("Please create the right tree of %d\n",value);
    node->right = create_tree();
    
    return node;
}

4.2：樹的遍歷

遍歷：對樹的一種最基本的運算(二叉樹是非線性結(jié)構(gòu)在塔，但在遍歷時是按一定規(guī)則和順序走遍二叉樹的所有結(jié)點，使每一個結(jié)點都被訪問一次拨黔，而且只被訪問一次)蛔溃。

樹的遍歷實質(zhì)上是將二叉樹的各個結(jié)點轉(zhuǎn)換成為一個線性序列來表示。

1. L：遍歷左子樹
2. D：訪問根結(jié)點
3. R：遍歷右子樹

對一棵二叉樹遍歷分三種情況(下面先序蓉驹，中序和后序都是以根為標準)：

1. DLR（稱為先根次序遍歷城榛，即先序遍歷）
2. LDR（稱為中根次序遍歷，即中序遍歷）
3. LRD（稱為后根次序遍歷态兴，即后序遍歷）

4.2.1：樹的先序遍歷

image.png

先序遍歷的方法：訪問根狠持；按先序遍歷左子樹；按先序遍歷右子樹瞻润。

//先序遍歷的遞歸算法
void preorder(tree *node) {
    if(node == NULL)
        return;

    printf(“%d”, node->data);//7,3,1,4,6,8,5,2

    preorder(node->left);
    preorder(node->right);
}

4.2.2：樹的中序遍歷

image.png

中序遍歷的方法：按中序遍歷左子樹喘垂；訪問根甜刻；按中序遍歷右子樹。

//中序遍歷
void inorder(tree *node) {
    if(node == NULL)
        return;

    inorder(node->left);
    printf(“%d”, node->data);//1,3,6,4,7,5,8,2
    inorder(node->right);
}

4.2.3：樹的后序遍歷

image.png

后序遍歷的方法：按后序遍歷左子樹正勒；按后序遍歷右子樹得院；訪問根。

void postorder(tree *node) {
    if(node == NULL)
        return;

     postorder(t->left);
     postorder(t->right);
     printf(“%d”, t->data);//1,6,4,3,5,2,8,7
}

4.3：樹的銷毀

vode pre_destroy(tree *node) {
    if (node == NULL) 
        return NULL;
        
    tree *left = node->left;
    tree *right = node->right;
    free(node);
    
    pre_destroy(left);
    pre_destroy(right);
}

4.4：平衡二叉樹(AVL)/紅黑樹(rbtree)/B+樹/B-樹

1. 二叉排序樹：所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）章贞；所有結(jié)點存儲一個關(guān)鍵字祥绞；非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹鸭限；
2. 平衡二叉排序樹：一種改進的二叉排序樹蜕径，一棵平衡二叉排序樹或者是一棵空樹，或者是一棵任意一結(jié)點的左子樹與右子樹的高度至多差1的二叉樹排序樹败京。對于二叉排序樹上的任何結(jié)點兜喻，其平衡因子定義為該結(jié)點左子樹的高度減去該結(jié)點右子樹高度。任一結(jié)點的平衡因子只可能是-1赡麦，0朴皆，1。平衡的二叉排序樹的查找方法與一般的二叉排序樹完全一樣泛粹，其優(yōu)點是總能保持查找長度為O(log2n)量級遂铡。往平衡的二叉排序樹插入新結(jié)點時，需要對樹的結(jié)構(gòu)進行必要調(diào)整戚扳，以動態(tài)地保持平衡二叉排序樹的特點忧便。
3. 紅黑樹(RB Tree)：是平衡二叉樹，查找的效率也就一樣帽借，為logN珠增。所以在C++的STL庫中，set/map砍艾，multiset/multimap就是用的紅黑樹作為底層的數(shù)據(jù)結(jié)構(gòu)蒂教，方便查找與插入刪除操作。

image

紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹脆荷，顏色或紅色或黑色凝垛。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹增加了如下的額外要求：

性質(zhì)1： 節(jié)點是紅色或黑色蜓谋。

性質(zhì)2： 根是黑色梦皮。

性質(zhì)3： 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

性質(zhì)4： 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點桃焕。

這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長剑肯。結(jié)果是這個樹大致上是平衡的。因為操作比如插入观堂、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例让网，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的呀忧，而不同于普通的二叉查找樹。

B樹：即二叉排序（搜索）樹

1. 所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）溃睹；
2. 所有結(jié)點存儲一個關(guān)鍵字而账；

3. 非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹因篇；

   
   
   image

B-樹：一種多路搜索樹（并不是二叉的）

1. 定義任意非葉子結(jié)點最多只有M個兒子泞辐；且M>2；
2. 根結(jié)點的兒子數(shù)為[2, M]竞滓；
3. 除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]铛碑；
4. 每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字；（至少2個關(guān)鍵字）
5. 非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1虽界；
6. 非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]涛菠；
7. 非葉子結(jié)點的指針：P[1], P[2], …, P[M]莉御；其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹俗冻，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹礁叔；
8. 所有葉子結(jié)點位于同一層；

image

B+樹：是B-樹的變體迄薄，也是一種多路搜索樹：

1. 其定義基本與B-樹同琅关，除了：
2. 非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；
3. 非葉子結(jié)點的子樹指針P[i]讥蔽，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）涣易；
4. 為所有葉子結(jié)點增加一個鏈指針；
5. 所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)

image