二叉樹（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;
}