数据结构

一、二叉查找树的特性：

性质：①左子树<根节点    ②右子树>根节点

用途：解决与排名相关的检索需求。

1.二叉查找树复杂度？

①最优/平均                O(nlogn)

②最差                        O(n)

code:

#include 
#include 

#define KEY(n) (n ? n->key : 0)

typedef struct Node
{
    int key;
    Node *lchild, *rchild;
} Node;

Node *getNewNode(int key)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->lchild = p->rchild = NULL;
    return p;
}

Node *insert(Node *root, int key)
{
    if (root == NULL) return getNewNode(key);
    if (root->key == key) return root;
    if (root->key > key) root->lchild = insert(root->lchild, key);
    else root->rchild = insert(root->rchild, key);
    return root;
}

void clear(Node *root)
{
    if (root == NULL) return;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return;
}

void print_node(Node *root)
{
    printf("(%3d | %3d, %3d )\n", KEY(root), KEY(root->lchild), KEY(root->rchild));
}

void output(Node *root)
{
    if (root == NULL) return;
    print_node(root);
    output(root->lchild);
    output(root->rchild);
    return;    
}

int main(int argc, char const *argv[])
{
    Node *root = NULL;
    int key;
    while (~scanf("%d", &key)) {
        root = insert(root, key);
        printf("\n=== insert %d to BST ===\n", key);
        output(root);
    }
    return 0;
}

 

2.重复节点的插入如何处理？

①重复的节点部分拉一链条出来，类似链表。

②把新插入的数据当作大于这个节点的值处理。

3.查找固定值

Node *search(Node *root, int key)
{
    if (root == NULL) return NULL;
    if (root->key == key) return root;
    if (root->key > key) return search(root->lchild, key);
    return search(root->rchild, key);
}

// search
    while (~scanf("%d", &key))
    {
        if (key == -1) break;
        ret = search(root, key);
        if (ret) printf("find %d from BST\n", key);
        else printf("%d not found\n", key);
    }

4.查找第K小元素

#define CNT(n) (n ? n->cnt : 0)

Node *__find_k(Node *root, int k)
{
    if (CNT(root->lchild) >= k) return __find_k(root->lchild, k);
    if (CNT(root->lchild) + 1 == k) return root;
    return __find_k(root->rchild, k - CNT(root->lchild) - 1);
}

Node *find_k(Node *root, int k)
{
    if (k <= 0 || k > CNT(root)) return NULL;
    return __find_k(root, k);
}

5.输出二叉查找树中一个范围的值[l, r]

void output_range(Node *root, int l, int r)
{
    if (root == NULL) return;
    output_range(root->lchild, l, r);
    if (root->key <= r && root->key >= l) printf("%d ", root->key);
    output_range(root->rchild, l, r);
    return;
}

// outoput range element
    int l, r;
    while (~scanf("%d%d", &l, &r))
    {
        if (l == -1) break;
        printf("find range [%d, %d] : ", l, r);
        output_range(root, l, r);
        printf("\n");
    }