红黑树在工程中的使用，红黑树是平衡树的一种。
1. 红黑树顺序的功能
2. 快速查找的功能
1.二叉树插入
1. 如果比当前根节点大，就插到右子树
2. 如果比当前根节点小，就插到左子树
3. 再与根节点的子树去比较，决定插入到左子树，还是右子树。
一直到左右子树为空的情况。注意：二叉树的插入，只能作为叶子节点。
代码中的tmp指向的是node的父节点。下图的根节点是tmp指向的，node是指向根节点的子节点。
//二叉树创建节点，一般是不对外开放
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 node;
}
//二叉树插入
int bstree_insert(struct bstree *T,KEY_VALUE key)
{
if(T == null)
return -1;
//如果根节点为空，就创建一个树
if(T->root == NULL)
{
T->root = bstree_create_node(key);
return 0;
}
//接替根节点
//指向父节点的子节点
struct bstree_node *node = T->root;
//指向父节点
struct bstree_node *tmp = T->root;
//把一个值插入到相应的位置
//这个while循环就相当于，一个查找的过程
while(node != NULL)
{
//第一次，父节点和子节点指向的同一个位置
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.rignt = 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("M",node->data);
bstree_traversal(node->bst.right);
}
//二叉树的测试和遍历的代码
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");
}
tmp指针，node指针，一直在往下移动。为什么这样呢？因为二叉树没有回溯，没有办法返回上一层，找不到父节点。所以这里必须用两个指针。
当代码中的循环走完的时候,node指向空。
