二叉排序树，中序遍历，二分查找代码

读取10个元素 87 7 60 80 59 34 86 99 21 3，然后建立二叉查找树，中序遍历输出3 7 21 34 59 60 80 86 87 99，针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BiTree;

int insertBST(BiTree &T, KeyType k) {
    BiTree treeNew = (BiTree) calloc(1, sizeof(BSTNode));// 给新节点申请空间
    treeNew->key = k;
    if (NULL == T) {  // T 是树根
        T = treeNew;
        return 1;
    }
    BiTree p = T, parent; // 用来查找树
    while (p) {
        parent = p; // parent用来存储p的父亲
        if (k > p->key) {
            p = p->rchild;
        } else if (k < p->key) {
            p = p->lchild;
        } else {
            return -1;  // 相等的元素不可以放入查找树
        }
    }
    // 接下来要判断放到父亲的左边还是右边
    if (k > parent->key) {
        parent->rchild = treeNew;
    } else {
        parent->lchild = treeNew;
    }
    return 0;
}

// 创建二叉查找树
void createBST(BiTree &T, KeyType *str, int len) {
    for (int i = 0; i < len; i++) {
        insertBST(T, str[i]);
    }
}

// 创建二叉树排序
void createBSTOrder(BiTree &T, KeyType *str, int len) {
    T = NULL; // T 是树根
    int i;
    while (i < len) {
        insertBST(T, str[i]);
        i++;
    }
}


// 中序遍历，从小到大
void inOrder(BiTree T, int arr[]) {
    static int pos = 0;  // 局部静态变量只会初始化一次
    if (T != NULL) {
        inOrder(T->lchild, arr);
        printf("%3d", T->key);
        arr[pos] = T->key; // 输出的同时存入数组
        pos += 1;// 下标加一
        inOrder(T->rchild, arr);
    }
}

// 二分查找（折半查找） 时间复杂度 logN
int binarySearch(int arr[], KeyType key, int len) {
    int low = 0, mid, high = len - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key > arr[mid]) {
            low = mid + 1;//等于就找到了
        } else if (key < arr[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

// 二叉排序树，中序遍历，二分查找
int main() {
    BiTree T = NULL;//树根
    KeyType str[10] = {87, 7, 60, 80, 59, 34, 86, 99, 21, 3};//将要进入二叉排序树的元素值
    // 创建二叉树
    createBST(T, str, 10);
    // 中序遍历
    inOrder(T, str);
    printf("\n");
    // 折半查找（二分查找，必须排序后才能使用）
    int val = binarySearch(str, 21, 10);
    printf("%d", val);
    return 0;
}