介绍
树结构是数据结构中很重要的一部分；对于森林和树大部分转换成 二叉树 来进行研究；
对于各种二叉树太复杂，对于我自己将它们分为：普通二叉树，BST树(二叉查找树，二叉排序树，二叉搜索树),按照平衡来区分：AVL平衡二叉树和非平衡二叉树。注意avl树是高度平衡的二叉树，不利于工程使用。
本博客主要介绍二叉排序树的定义，性质，以及使用。
二叉排序树定义
递归定义：
1 要么是空树
2 要么当前树的左右子树也都是二叉排序树
性质
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
实现
二叉排序树工程上应用不多，根结点比左边大，比右边小；左右子树同样也是二叉排序树。
递归思想。
常见的算法实现：创建，插入，遍历，删除，更新
对于实现常见方式：递归和非递归(借助队列)
1.1 二叉排序树结构：
typedef int KEY_VALUE; //二叉树性质数据结构和业务分离 #if 0 struct bstree_node { //结点 KEY_VALUE data; struct bstree_node *left; struct bstree_node *right; }; //二叉树结构 struct bstree { struct bstree_node *root; }; #else #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 { struct bstree_node *root; struct bstree_node *nil; //不指向空，而是开辟一个叶子结点 }; #endif
1.2内部函数：
//创建一个结点 内部函数 struct bstree_node *_bstree_create_node(KEY_VALUE key) { //堆上创建 struct bstree_node *node = (struct bstree_node*)malloc(sizeof(struct bstree_node)); if (node == NULL){ //assert(0); return NULL; } node->data = key; node->bst.left = node->bst.right = NULL; return node; }
1.3对外api
插入
//插入 插入后就是在叶子结点 insert int bstree_insert(struct bstree *T, KEY_VALUE key){ //1 异常判断 if (T == NULL){ printf("bstree_insert T is NULL!!! \n"); return -1; //树为空 } //2 只是根结点 if (T->root == NULL) { printf("bstree_insert T->root is NULL!!! key:%d\n", key); T->root = _bstree_create_node(key); return 0; } //3 不只e根结点 二叉树无法回缩 struct bstree_node *node = T->root; struct bstree_node *tmp = T->root; while(node != NULL){ tmp = node; if (key <node->data){ node = node->bst.left; }else if (key > node->data){ node = node->bst.right; }else{ //相同的结点不插入 尽量不插入重复结点，不方便查找 return -2; } } if (key < tmp->data){ //分配空间 tmp->bst.left = _bstree_create_node(key); }else{ tmp->bst.right = _bstree_create_node(key); } return 0; }
遍历：
//遍历 traversal //前中后层次遍历 递归和非递归(需要接入一个队列实现) int bstree_traversal(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; }
查找
//查找 search //search() struct bstree_node * bstree_search(struct bstree *T, KEY_VALUE key){ //空树 if (T == NULL) return NULL; //根结点也是空的 if (T->root == NULL) return NULL; struct bstree_node *node = T->root; struct bstree_node *tmp = T->root; while(node != NULL){ tmp = node; if (key == node->data){ return node; } } return NULL; }
对于删除和更改暂未实现
测试代码：
int main() { //测试代码 int keyArray[ARRAY_LENGTH] = {24,25,13,35,23, 26,67,47,38,98, 20,13,17,49,12, 21,9,18,14,15}; struct bstree T = {0}; int i = 0; for (i = 0;i < ARRAY_LENGTH;i ++) { bstree_insert(&T, keyArray[i]); } bstree_traversal(T.root); printf("\n"); return 0; }
结果：
遍历
二叉排序树的遍历四种方式：前中后层次遍历
实现方式：递归和非递归(借助队列来实现）
完整代码：
https://github.com/hengfengyaoren/Data-Structure-Algorithm/blob/main/bstree.c
