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

¥ 我要打赏    纠错/补充 收藏