什么是二叉查找树？
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点（no duplicate nodes）。
好的，我们来定义一个结构体，
struct bnode_info {
struct bnode_info *parent;
struct bnode_info *lchild;
struct bnode_info *rchild;
};
怎么没有数据域呢？模仿内核链表，我们把这个节点嵌入到大的结构体里。
static inline void bnode_init(struct bnode_info *bnode)
{
bnode->parent = NULL;
bnode->lchild = NULL;
bnode->rchild = NULL;
}
节点的初始化函数，为下文做准备。
struct data_info {
int data;
struct bnode_info bnode;
};
这个是测试用的，可以看到，把节点嵌入了进去。
static int bnode_cmp(struct bnode_info *a, struct bnode_info *b)
{
struct data_info *pa = list_entry(a, struct data_info, bnode);
struct data_info *pb = list_entry(b, struct data_info, bnode);
return pa->data - pb->data;
}
这是比较函数，关于list_entry宏，前面的博文已经说了，这里不赘述。
struct btree_info {
struct bnode_info *root; //指向树根
int (*key_cmp)(struct bnode_info *a,
struct bnode_info *b);
void (*push)(struct bnode_info *bnode,
struct btree_info *info);
int (*del)(struct bnode_info *bnode, struct btree_info *info);
struct bnode_info *(*find)(struct bnode_info *bnode,
struct btree_info *info);
void (*pre_order)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
void (*in_order)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
void (*post_order)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
//非递归遍历
void (*pre_order_norecur)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
void (*in_order_norecur)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
void (*post_order_norecur)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
void (*level_order)(struct btree_info *info,
void (*todo)(struct bnode_info *bnode));
size_t (*get_depth)(const struct btree_info *info);
int (*is_empty)(const struct btree_info *info);
};
这里定义了很多方法，我们先不管，只要知道里面有个指针，指向树根就可以了。
static int btree_is_empty(const struct btree_info *btree)
{
return btree->root == NULL;
}
如果树为空，那就是连树根都没有了。
下面进入正题，说把一个元素插入一棵树。
分析：1.这棵树是空的。那问题就简单了，这个节点就是树根。
2.这棵树不空。那就需要从树根查找。把新元素和树根比一比，小了就继续和树根的左孩子比，大了就继续和树根的右孩子比（假设不存在相等的情况），......,如果左孩子或者右孩子为空，那就是找到位置了，让这个新元素成为孩子就可以了。注意，这里我们不用递归，用迭代。
static void btree_push2(struct bnode_info *bnode,
struct btree_info *info)
{
assert(bnode != NULL && info != NULL); bnode_init(bnode); //[1].空树
if (btree_is_empty(info))
{
info->root = bnode;
return;
} //[2].非空树
struct bnode_info *cur = info->root;
struct bnode_info *parent = NULL;
int flag = 0; while (cur != NULL)
{
parent = cur;
if (info->key_cmp(bnode, cur) >= 0)
{
//右
cur = cur->rchild;
flag = 1;
}
else
{
//左
cur = cur->lchild;
flag = 0;
}
} if(flag==0)
parent->lchild=bnode;
else
parent->rchild=bnode; bnode->parent = parent; }
为了验证对错，我们要写个遍历树的方法。看看先序遍历-递归版本，（先树根，然后左子树，最后右子树）
static void __pre_order(struct bnode_info *bnode,
void (*todo)(struct bnode_info *bnode))
{
if (bnode != NULL) {
todo(bnode);
__pre_order(bnode->lchild, todo);
__pre_order(bnode->rchild, todo);
}
} static void btree_pre_order(struct btree_info *info,
void (*todo)(struct bnode_info *bnode))
{
__pre_order(info->root, todo);
}
void print_node(struct bnode_info *node)
{
struct data_info *pa = list_entry(node, struct data_info, bnode); printf("%d ", pa->data);
}
这个是打印用的，到时候传给todo。
测试函数：
int main()
{ struct data_info s[]={
{50},{24},{80},{16},{26},{5}
};
struct btree_info *btree = (struct btree_info *)
malloc(sizeof(struct btree_info));
assert(btree != NULL); btree_init(btree, bnode_cmp); int i;
for (i = 0; i < sizeof s/ sizeof *s; ++i) {
btree->push(&s[i].bnode, btree);
} //遍历
printf("--pre_order--\n");
btree->pre_order(btree, print_node);
printf("\n");
我们先看看运行结果：
--pre_order--
50 24 16 5 26 80
接着说插入，前面是非递归方法。这次我们用递归。思路很简单，把要插入的节点，和树根比，如果树根为空，那么这个节点就成为树根；如果比树根小，就和树根的左孩子比（左孩子可以看成是新的树根）；如果比树根大，就和树根的右孩子比。这里需要注意的是，假设比树根小，那么就和树根的左孩子比，假设传进来的参数是新节点和左孩子，我们发现左孩子为NULL，怎么办呢？当然应该把新节点的地址写入这里，为了改写NULL，我们就应该知道这个域的地址，这里就引入了二级指针。也就是说，我们的函数设计的时候，参数是新节点的地址，和树根的二级指针。
static void __push(struct bnode_info *bnode, struct bnode_info **pnode,
int (*cmp)(struct bnode_info *a, struct bnode_info *b))
{
if (*pnode == NULL)
{
bnode_init(bnode);
*pnode = bnode;
}
else
{
if (cmp(bnode, *pnode) > 0)
__push(bnode, &(*pnode)->rchild,cmp); else
__push(bnode, &(*pnode)->lchild,cmp);
}
} void btree_push_recursion(struct bnode_info *bnode, struct btree_info *info)
{
assert(bnode != NULL && info != NULL);
__push(bnode, &info->root,info->key_cmp);//第二个参数是二级指针
}
总结一下，这篇文章我们说了什么？1.节点的插入（递归和非递归）2.先序遍历（递归版本）
下次我们接着说。