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

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