在二叉搜索樹中插入新元素

函數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