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