2.5. 二叉搜索树和平衡二叉树

本文参考:

二叉搜索树

平衡二叉树

2.5.1. 二叉搜索树

二叉搜索树（BST,binary search tree) 也称二叉查找树。满足一下性质。

  • 非空左子树的所有键值小于其根节点的键值。

  • 非空柚子树的所有键值大于其根节点的键值。

  • 左右子树都是二叉搜索树。

抽象数据结构描述

类型名称： 二叉搜索树
数据对象集： 一个有穷的节点集合
操作集：
    Position Find(ElementType item , BinTree bst): 从二叉树查找元素，返回节点地址。
    Position FinMin(BinTree bst): 查找并返回最小值所在节点地址。
    Position FinMax(BinTree bst): 查找并返回最大值所在节点地址。
    BinTree  Insert(ElementType item , BinTree bst): 插入元素。
    BinTree  Delete(ElementType item , BinTree bst): 删除元素。

2.5.2. 二叉搜索树实现

 1// bitree_link_base.h
 2#pragma once
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6#define ElementType int
 7typedef struct  TreeNode *BsTree ;
 8typedef BsTree  Position ;
 9struct  TreeNode{
10    ElementType Data ;
11    BsTree  Left;
12    BsTree  Right;
13};

  1// bstree_link_base.c
  2#include <stdio.h>
  3#include <stdlib.h>
  4#include "bitree_link_base.h"
  5
  6
  7// 判断树是否为空
  8int TreeIsEmpty(BsTree bt) {
  9    if (bt == NULL) {
 10        return 1;
 11    }
 12    return 0;
 13}
 14
 15// 创建树
 16BsTree CreateBsTree() {
 17    BsTree bt = (BsTree) malloc(sizeof(struct TreeNode));
 18    return bt;
 19}
 20
 21Position FindByRecursive(ElementType item, BsTree bst) {
 22    if (!bst) {
 23        return NULL;
 24    }
 25    if (item == bst->Data) {
 26        return bst;
 27    }
 28    if (item > bst->Data) {
 29        return FindByRecursive(item, bst->Right);
 30    }
 31    if (item < bst->Data) {
 32        return FindByRecursive(item, bst->Left);
 33    }
 34}
 35
 36Position FindByIterate(ElementType item, BsTree bst) {
 37
 38    BsTree pst = bst;
 39    while (pst) {
 40        if (pst->Data == item) {
 41            return pst;
 42        }
 43        if (item > pst->Data) {
 44            pst = pst->Right;
 45        } else {
 46            pst = pst->Left;
 47        }
 48    }
 49    return NULL;
 50}
 51
 52Position FindMax(BsTree bst) {
 53    BsTree pst = bst;
 54    while (pst && pst->Right) {
 55        pst = pst->Right;
 56    }
 57    return pst;
 58
 59}
 60
 61Position FindMin(BsTree bst) {
 62    BsTree pst = bst;
 63    while (pst && pst->Left) {
 64        pst = pst->Left;
 65    }
 66    return pst;
 67
 68}
 69
 70// 前序递归
 71void PreOrderTraversalByRecursive(BsTree bt) {
 72    if (bt) {
 73        printf("%d ", bt->Data);
 74        PreOrderTraversalByRecursive(bt->Left);
 75        PreOrderTraversalByRecursive(bt->Right);
 76    }
 77}
 78
 79BsTree InsertByIterate(ElementType item, BsTree bst) {
 80    // BsTree  pst = bst ;
 81    BsTree parent = bst;
 82    BsTree current = bst;
 83    while (current) {
 84        parent = current ;
 85        if (item > current->Data) {
 86            current = current->Right;
 87
 88        } else {
 89            current = current->Left;
 90        }
 91    }
 92
 93    BsTree node = malloc(sizeof(struct TreeNode));
 94    node->Data = item;
 95    node->Left = NULL;
 96    node->Right = NULL;
 97    if (item > parent->Data) {
 98        parent->Right = node;
 99    } else {
100        parent->Left = node;
101    }
102
103    return bst;
104
105}
106
107BsTree InsertByRecursive(ElementType item, BsTree bst) {
108    if ( ! bst ){
109        BsTree node = malloc(sizeof(struct TreeNode));
110        node->Data = item;
111        node->Left = node->Right = NULL;
112        return node;
113    }
114    if (item > bst->Data ){
115        bst->Right = InsertByRecursive(item,bst->Right);
116    }else{
117        bst->Left = InsertByRecursive(item,bst->Left);
118    }
119    return bst ;
120    // == 这个咱不考虑
121}
122
123BsTree DeleteByRecursive(ElementType item, BsTree bst) {
124    if ( !bst ){
125       printf("找不到删除元素");
126       return NULL;
127    }
128    if (item > bst->Data ){
129        bst->Right = DeleteByRecursive(item,bst->Right);
130    }else if(item < bst->Data ){
131        bst->Left = DeleteByRecursive(item,bst->Left);
132    }else{
133        // 左节点为空的删除
134        if (!bst->Left  ){
135            bst = bst->Right;
136        }else if (!bst->Right){   // 右节点为空。
137            bst = bst->Left ;
138        }else{
139            // 左右都有的。
140            Position  tmp = FindMin(bst->Right);
141            bst->Data = tmp->Data;
142            bst->Right = DeleteByRecursive(bst->Data,bst->Right);
143        }
144    }
145   return bst ;
146}
147
148BsTree CreateDemoTree() {
149    /*
150            40
151         20      60
152       10  30   50
153
154
155    * */
156    BsTree bt1 = CreateBsTree();
157    bt1->Data = 40;
158    BsTree bt2 = CreateBsTree();
159    bt2->Data = 20;
160    BsTree bt3 = CreateBsTree();
161    bt3->Data = 60;
162    BsTree bt4 = CreateBsTree();
163    bt4->Data = 10;
164    BsTree bt5 = CreateBsTree();
165    bt5->Data = 30;
166    BsTree bt6 = CreateBsTree();
167    bt6->Data = 50;
168
169    bt1->Left = bt2;
170    bt1->Right = bt3;
171
172    bt2->Left = bt4;
173    bt2->Right = bt5;
174
175    bt3->Left = bt6;
176    return bt1;
177}
178
179int mainByIterate() {
180    Position pos;
181    BsTree bst = CreateDemoTree();
182    printf("PreOrderTraversal\n");
183    PreOrderTraversalByRecursive(bst);
184    printf("\n");
185
186    pos = FindByIterate(20, bst);
187    PreOrderTraversalByRecursive(pos);
188    printf("\n");
189
190    pos = FindMax(bst);
191    PreOrderTraversalByRecursive(pos);
192    printf("\n");
193
194    pos = FindMin(bst);
195    PreOrderTraversalByRecursive(pos);
196    printf("\n");
197
198
199//    bst = InsertByIterate(33, bst);
200//    PreOrderTraversalByRecursive(bst);
201//    printf("\n");
202
203//    bst = DeleteByRecursive(70, bst);
204//    PreOrderTraversalByRecursive(bst);
205//    printf("\n");
206//    bst = DeleteByRecursive(80, bst);
207//    PreOrderTraversalByRecursive(bst);
208//    printf("\n");
209
210    bst = DeleteByRecursive(20, bst);
211    PreOrderTraversalByRecursive(bst);
212    printf("\n");
213}
214int mainByRecursive() {
215    Position pos;
216    BsTree bst = CreateDemoTree();
217    printf("PreOrderTraversal\n");
218    PreOrderTraversalByRecursive(bst);
219    printf("\n");
220
221    pos = FindByRecursive(20, bst);
222    PreOrderTraversalByRecursive(pos);
223    printf("\n");
224
225
226
227    pos = FindMax(bst);
228    PreOrderTraversalByRecursive(pos);
229    printf("\n");
230
231    pos = FindMin(bst);
232    PreOrderTraversalByRecursive(pos);
233    printf("\n");
234
235    bst = InsertByRecursive(70, bst);
236    PreOrderTraversalByRecursive(bst);
237    printf("\n");
238
239
240
241    bst = DeleteByRecursive(40, bst);
242    PreOrderTraversalByRecursive(bst);
243    printf("\n");
244
245
246
247}
248
249int main(){
250    mainByRecursive();
251   // mainByIterate()
252}

2.5.3. 平衡二叉树（AVL)

平衡因子绝对值小于等于1的搜索树才是平衡二叉树。

平衡因子= 左树高度-右树高度。

2.5.4. 平衡二叉树实现

  1#include <stdio.h>
  2#include <stdlib.h>
  3
  4#define  ElementType int
  5typedef struct AVLNode *AVLTree;
  6struct AVLNode {
  7    ElementType Data;
  8    AVLTree Left;
  9    AVLTree Right;
 10    int Height;
 11};
 12
 13AVLTree CreateAvlTree(){
 14    AVLTree t = (AVLTree)malloc(sizeof(struct AVLNode));
 15    return t ;
 16}
 17
 18int Max(int a, int b) {
 19    if (a > b) {
 20        return a;
 21    }
 22    return b;
 23}
 24
 25int GetHeight(AVLTree t) ;
 26void UpdateHeight(AVLTree t) {
 27    t->Height = Max(GetHeight(t->Left), GetHeight(t->Right)) + 1;
 28    return ;
 29}
 30
 31
 32int GetHeight(AVLTree t) {
 33    int rightHeight;
 34    int leftHeight;
 35    if (!t) {
 36        return 0;
 37    }
 38    UpdateHeight(t);
 39    return t->Height;
 40}
 41
 42AVLTree RR(AVLTree a) {
 43    AVLTree b = a->Right;
 44    a->Right = b->Left;
 45    b->Left = a;
 46
 47    UpdateHeight(a);
 48    UpdateHeight(b);
 49    return b;
 50}
 51
 52AVLTree LL(AVLTree a) {
 53    AVLTree b = a->Left;
 54    a->Left = b->Right;
 55    b->Right = a;
 56
 57    UpdateHeight(a);
 58    UpdateHeight(b);
 59    return b;
 60}
 61
 62AVLTree LR(AVLTree a) {
 63    a->Left = RR(a->Left);
 64    return LL(a);
 65}
 66AVLTree RL(AVLTree a) {
 67    a->Right = LL(a->Right);
 68    return RR(a);
 69}
 70
 71AVLTree Insert(AVLTree t, ElementType item) {
 72    if (!t) {
 73        //  给叶子节点添加一个子节点的时候，走到这个部分。
 74        AVLTree node = (AVLTree)malloc(sizeof(struct AVLNode));
 75        node->Data = item;
 76        node->Left = NULL;
 77        node->Right = NULL;
 78        node->Height = 1;
 79        return node;
 80    }
 81    if (item > t->Data) {
 82        t->Right = Insert(t->Right, item);
 83        if (GetHeight(t->Right) - GetHeight(t->Left) == 2) {
 84            if (item > t->Right->Data) {
 85                t = RR(t);
 86            } else {
 87                t = RL(t);
 88            }
 89        }
 90    } else {
 91        t->Left = Insert(t->Left, item);
 92        if (GetHeight(t->Left) - GetHeight(t->Right) == 2) {
 93            if (item < t->Left->Data) {
 94                t = LL(t);
 95            } else {
 96                t = LR(t);
 97            }
 98        }
 99    }
100    t->Height = Max(GetHeight(t->Left), GetHeight(t->Right)) + 1;
101    return t;
102}
103void PreOrderTraversalByRecursive(AVLTree bt){
104    if (bt){
105        printf("%d ", bt->Data);
106        PreOrderTraversalByRecursive(bt->Left);
107        PreOrderTraversalByRecursive(bt->Right);
108    }
109}
110
111int main(){
112    AVLTree  avlTree= NULL ;
113    //avlTree = CreateAvlTree();
114    avlTree= Insert(avlTree,1);
115    avlTree = Insert(avlTree,2) ;
116    avlTree= Insert(avlTree,3) ;
117    PreOrderTraversalByRecursive(avlTree);
118    printf("\n");
119    avlTree= Insert(avlTree,7) ;
120    PreOrderTraversalByRecursive(avlTree);
121    printf("\n");
122    avlTree= Insert(avlTree,6) ;
123    avlTree= Insert(avlTree,5) ;
124    avlTree= Insert(avlTree,0) ;
125    PreOrderTraversalByRecursive(avlTree);
126}
127/*
128 * =========================================================
129    one          two        three     three_adjust(RR)
130    1            1             1            2
131                    2             2       1     3
132                                    3
133 * =========================================================
134    four        five            five_adjust(RL)
135     2           2                  2
136   1    3      1    3           1      6
137           7           7              3  7
138                     6
139=========================================================
140 six                six_adjust(RL)
141      2                  3
142   1     6            2    6
143       3   7        1     5  7
144        5
145=========================================================
146 seven              seven_adjust(LL)
147        3                   3
148      2   6              1     6
149    1    5  7           0 2   5 7
150  0
151 */