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
