在二元搜尋樹中插入新元素

函式insert()用於在二元搜尋樹中的適當位置新增新元素。 insert()函式的設計方式是，它必須在每個值上違反二元搜尋樹的屬性。

• 為樹分配記憶體。
• 將資料部分設定為值並設定樹的左右指標指向NULL。
• 如果要插入的資料項將是樹的第一個元素，則此節點的左和右節點將指向NULL。
• 否則，檢查資料項是否小於樹的根元素，如果為真，則以根的左子樹遞回執行此操作。
• 如果為false，則使用根的右子樹遞回執行此操作。

insert (TREE, ITEM)

第1步 : IF TREE = NULL
    為TREE分配記憶體 
      SET TREE -> DATA = ITEM 
     SET TREE -> LEFT = TREE -> RIGHT = NULL
     ELSE
      IF ITEM < TREE -> DATA
       Insert(TREE -> LEFT, ITEM)
     ELSE
      Insert(TREE -> RIGHT, ITEM)
     [IF結束]
     [IF結束]
第2步 : 結束

參考以下示意圖 -

使用C語言實現插入功能：

#include<stdio.h>  
#include<stdlib.h>  
void insert(int);  
struct node  
{  
    int data;  
    struct node *left;   
    struct node *right;   
};  
struct node *root;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\nEnter the item which you want to insert?\n");  
        scanf("%d",&item);  
        insert(item);  
        printf("\nPress 0 to insert more ?\n");  
        scanf("%d",&choice);  
    }while(choice == 0);  
}  
void insert(int item)  
{  
    struct node *ptr, *parentptr , *nodeptr;  
    ptr = (struct node *) malloc(sizeof (struct node));  
    if(ptr == NULL)  
    {  
        printf("can't insert");  
    }  
    else   
    {  
    ptr -> data = item;  
    ptr -> left = NULL;  
    ptr -> right = NULL;   
    if(root == NULL)  
    {  
        root = ptr;  
        root -> left = NULL;  
        root -> right = NULL;  
    }  
    else   
    {  
        parentptr = NULL;  
        nodeptr = root;   
        while(nodeptr != NULL)  
        {  
            parentptr = nodeptr;   
            if(item < nodeptr->data)  
            {  
                nodeptr = nodeptr -> left;   
            }   
            else   
            {  
                nodeptr = nodeptr -> right;  
            }  
        }  
        if(item < parentptr -> data)  
        {  
            parentptr -> left = ptr;   
        }  
        else   
        {  
            parentptr -> right = ptr;   
        }  
    }  
    printf("Node Inserted");  
    }  
}

執行上面範例程式碼，得到以下結果 -

Enter the item which you want to insert?
12
Node Inserted
Press 0 to insert more ?
0

Enter the item which you want to insert?
23
Node Inserted
Press 0 to insert more ?
1