二叉排序树

简介: 二叉排序树

1 介绍

本文主要介绍二叉排序树性质/遍历,以及与平衡树,搜索树,AVL树关系,最后简单的实现一个二叉排序树。

森林,树工业用法比较麻烦,都是转成二叉树来实现。

二叉排序树(BST)::也叫二叉搜索树,中序遍历后的数据是按顺序排的

二叉平衡树(AVL):当然二叉排序树有极端情况会蜕化成链表结构,所以引入了左右子树的高度相差指平衡因子

2 二叉树的遍历

遍历的方式:前中后序遍历,以及层次遍历

层次遍历比较好理解,直接按照层次依次遍历即可。

如下图 对于中序遍历会得到一个按照顺序的大小: 3,7,9,11,22

3 简单实现

3.1 数据结构

数据结构与业务要进行分离。`

typedef int KE_VALUE
//二叉树的性质
#define BSTREE_ENTRY(name, type) \
        struct name{ \
        struct type *left;      \
        struct type *right;     \
        }
//结点
struct bstree_node{
        KEY_VALUE data; //业务逻辑
        BSTREE_ENTRY(, bstree_node) bst; //性质
};

将业务与性质分离后,可以在结点里面添加多个状态例如线程调度结构,单个结点有多种状态

struct bstree_node{
        KEY_VALUE data; //业务逻辑
        BSTREE_ENTRY(, bstree_node) ready; //准备状态
        BSTREE_ENTRY(, bstree_node) deter; //唤醒状态
        BSTREE_ENTRY(, bstree_node) wait; //等待状态
        BSTREE_ENTRY(, bstree_node) sleep; //睡眠状态
};

二叉排序树的数据结构:

struct bstree{
        struct bstree_node *root;   //根结点
        struct bstree_node *nil;        //叶子结点,我们不去判断结点为null
}

3.2 api

//创建结点是内部接口,提供给别人使用往二叉排序树里面添加结点:

struct bstree_node *bstree_create_node(KEY_VALUE key){
        struct bstree_node *node = (struct bstree_node*)malloc(sizeof(struct bstree_node));
        if (node == NULL) return NULL;
        node->data = key;
        node->bst.left = node->bst.right = NULL;
        return NULL;
}

//对外使用的接口:插入,删除,搜索,遍历,更新修改

1 插入

int bstree_insert(struct bstree *T, KEY_VALUE key){
        //空树
        if (T == NULL) return -1;
        
        //1 只有根结点,插入到根结点
        if (T->root == NULL){
                T->root = bstree_create_node(key);
                return 0;
        }
        // 2 有结点
        struct bstree_node *node = T->root;
        struct bstree_node *tmp = T->root;
        
        while(node != NULL){//完成后node是指向最下面结点
                //tmp与node成父子结点
                tmp = node;
                if (key < node->data){
                        node = node->bst.left;
                }else if(key > node->data) {
                        node = node->bst.right;
                }else{  //相同的结点一般过滤掉,有重复的不方便查找
                        printf("exit !!!\n");
                        return -2;
                }
        }
        if (key < tmp->data){
                tmp->bst.left = bstree_create_node(key);
        }else{
                tmp->bst.right = bstree_create_node(key);
        }
        return 0;
}

2 遍历

遍历两种方式实现:递归和非递归(需要借助栈实现)

//tranvesl
//前中后  递归/非递归(需要借助栈)
int bstree_tranversal(struct bstree_node *node){
        if (node == NULL) return 0;
        
        bstree_traversal(node->bst.left);
        printf("%4d", node->data);
        bstree_traversal(node->bst.right);
        return 0;
}

3 搜索

//search
struct bstree_node *bstree_search(struct bstree *T ,KEY_VALUE key){
        if (T == NULL || T->root == NULL) return NULL;
        struct bstree_node *node = T->root;
        struct bstree_node *tmp = T->root;
        //完成后node是指向最下面结点
        while(node != NULL){
                //tmp与node成父子结点
                tmp = node;
                if (key < node->data){
                        node = node->bst.left;
                }else if(key > node->data) {
                        node = node->bst.right;
                }else{
                        return node;
                }
        }
        return NULL;
}

完整代码参考:

https://github.com/hengfengyaoren/Data-Structure-Algorithm/blob/main/bin_tree.c

目录
相关文章
|
存储 C++
二叉树搜索树的应用
二叉树搜索树的应用
59 1
|
15天前
|
存储 C++
【C++】二叉搜索树(BST)
二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,其每个节点的左子树所有节点值小于该节点值,右子树所有节点值大于该节点值,且左右子树也均为二叉搜索树。BST支持高效的数据查找、插入和删除操作,时间复杂度通常为O(log n)。本文档详细介绍了BST的基本概念、存储结构及其实现,包括迭代和递归两种方式的查找、插入、删除等操作的具体代码示例。
28 3
|
6月前
|
C++
【c++】二叉搜索树
【c++】二叉搜索树
36 0
二叉排序树(BST)
二叉排序树(BST)
69 0
|
7月前
|
存储 安全 C++
C++【二叉搜索树】
C++【二叉搜索树】
62 0
51 # 二叉搜索树的实现
51 # 二叉搜索树的实现
35 0
|
存储 算法
|
算法 JavaScript 前端开发
|
存储
【二叉搜索树】
【二叉搜索树】
49 0