二叉树（BST树）的插入

要进行插入，首先要在BST中进行查找，若key值已经存在，则应返回ERROR；不存在时，由于第一步的search操作已经返回了查找路径上的最后一个结点，只需要把key值与最后一个节点的值进行比较，比它小则为左子树，反之为右子树，代码如下:

/* 二叉树（BST树）的插入 */
#include <stdio.h>
#include <stdlib.h>
struct tree                     //树结构的声明
{    
    int data;                   //结点数据    
    struct tree *left;          //指向左子树的指针      
    struct tree *right;         //指向右子树的指针
};
typedef struct tree treenode;      //树的结构新类型
typedef treenode *btree;           //声明树结点指针类型

/* 二叉树的插入 */
btree insertnode(btree root, int value)
{    
    btree newnode;                 //新结点指针    
    btree temp = root;             //临时指针    
    btree back;                    //记录父节点指针   

    //创建新结点，将值存入结点    
    newnode = (btree)malloc(sizeof(treenode));    
    newnode->data = value;    
    newnode->left = NULL;    
    newnode->right = NULL;    

    //如果根结点为空，当前新结点当做根结点    
    if (root == NULL)    
    {
        return newnode;    
    }    
    else    
    {        
        while (temp != NULL)
        {    
            back = temp;            //保留父节点指针      
            if (temp->data > value) //比价结点值   
            {
                temp = temp->left;  //左子树    
            }    
            else    
            {
                temp = temp->right; //右子树    
            }
        }     
        //将新结点插入
        if (back->data > value)
        {    
            back->left = newnode;
        }
        else
        {   
            back->right = newnode;
        }    
    }    
    return root;                    //返回根结点
}
/* 创建二叉树 */
btree createbtree(int *data, int len)
{ 
    btree root = NULL;    
    int i;    
    for (i = 0; i < len; i++)    
    {
        root = insertnode(root, data[i]);    
    }    
    return root;
}

/* 
 二叉树的输出--先序遍历
 */
void preolder(btree ptr)
{
    if (ptr)
    {
        printf("%2d", ptr->data);
    preolder(ptr->left);
    preolder(ptr->right);
    }
}

/* 
 二叉树的输出--中序遍历
 */
void inolder(btree ptr)
{
    if (ptr)
    {
    inolder(ptr->left);
        printf("%2d", ptr->data);
    inolder(ptr->right);
    }
}

/* 
 二叉树的输出--后序遍历
 */
void postolder(btree ptr)
{
    if (ptr)
    {
    postolder(ptr->left);
    postolder(ptr->right);
        printf("%2d", ptr->data);
    }
}

/* 主函数 */
int main()
{    
    btree root = NULL;    
    int data[10] = {5, 6, 4, 8, 2, 3, 7, 1, 9};    
    root = createbtree(data, 9);     
    printf("\n---------先序遍历--------\n");
    preolder(root);    
    printf("\n---------中序遍历--------\n");
    inolder(root);    
    printf("\n---------后序遍历--------\n");
    postolder(root);    
    return 0;
}