реализация BST
-
20-09-2019 - |
Вопрос
Что не так со следующей реализацией двоичное дерево поиска (BST)?Мне сказали, что лучше использовать указатель на указатель на struct
узел в качестве аргумента в функции вставки.
struct node
{
int key_value;
struct node* left;
struct node* right;
};
insert(int key, struct node *leaf)
{
if( leaf == 0 )
{
leaf = (struct node*) malloc( sizeof( struct node ) );
leaf->key_value = key;
/* initialize the children to null */
leaf->left = 0;
leaf->right = 0;
}
else if(key < leaf->key_value)
{
insert( key, leaf->left );
}
else if(key > leaf->key_value)
{
insert( key, leaf->right );
}
}
Решение
Эта строка:
leaf = (struct node*) malloc( sizeof( struct node ) );
придает новое значение leaf
, указывая на недавно выделенную память.Однако новое значение не покидает функцию.Когда функция вернется, вызывающий объект все равно будет ссылаться на старую версию. leaf
, и произойдет утечка памяти.
Есть два подхода, которые вы можете использовать, чтобы исправить это:
1. Используйте указатель на указатель, например.
void insert(int key, struct node **leaf)
{
if(*leaf == 0 )
{
*leaf = (struct node*) malloc( sizeof( struct node ) );
...
}
/* In caller -- & is prepended to current_leaf. */
insert(37, ¤t_leaf);
2. Верните новый лист (или старый лист, если изменений нет).
struct node *insert(int key, struct node *leaf)
{
if(leaf == 0 )
{
leaf = (struct node*) malloc( sizeof( struct node ) );
...
}
return leaf;
}
/* In caller -- & is prepended to current_leaf. */
current_leaf = insert(37, current_leaf);
Указатели на указатели близки к тому, что их трудно понять.Я бы, наверное, выбрал второй вариант, если бы insert
в настоящее время больше ничего не возвращает.
Другие советы
Когда узел вставлен (лист == 0), вы не изменили его родителя, поэтому новый узел станет сиротой.
Другими словами, ваше дерево по-прежнему будет выглядеть как один узел, независимо от того, сколько узлов было вызвано с помощью вставки.
#include<stdio.h>
typedef struct tnode{
int data;
struct tnode *left,*right;
}TNODE;
TNODE * createTNode(int key){
TNODE *nnode;
nnode=(TNODE *)malloc(sizeof(TNODE));
nnode->data=key;
nnode->left=NULL;
nnode->right=NULL;
return nnode;
}
TNODE * insertBST(TNODE *root,int key){
TNODE *nnode,*parent,*temp;
temp=root;
while(temp){
parent=temp;
if(temp->data > key)
temp=temp->left;
else
temp=temp->right;
}
nnode=createTNode(key);
if(root==NULL)
root=nnode;
else if(parent->data>key)
parent->left=nnode;
else
parent->right=nnode;
return root;
}
void preorder(TNODE *root){
if(root){
printf("%5d",root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(TNODE *root){
if(root){
inorder(root->left);
printf("%5d",root->data);
inorder(root->right);
}
}
void postorder(TNODE *root){
if(root){
postorder(root->left);
postorder(root->right);
printf("%5d",root->data);
}
}
main(){
TNODE *root=NULL;
int ch,key;
do{
printf("\n\n1-Insert\t2-Preorder\n3-Inorder\t4-Postorder\n5-Exit\n");
printf("Enter Your Choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("Enter Element: ");
scanf("%d",&key);
root=insertBST(root,key);
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
default:
printf("\nWrong Choice!!");
}
}while(ch!=5);
getch();
return 0;
}