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

广告位

函数insert()用于在二叉搜索树中的适当位置添加新元素。 insert()函数的设计方式是,它必须在每个值…

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

  

說着敷衍話

关于作者: 說着敷衍話

为您推荐