He implementado BST en C. Inserte la búsqueda y funciona bien. Pero eliminar tiene problemas al eliminar el nodo raíz. Yo no soy capaz de liberar el puntero al nodo raíz. Yo podría, si se lo paso como un doble puntero, pero quería mantener el código simple sin necesidad de utilizar el doble de los punteros. Aquí NO tengo una cabeza de puntero que apunta al nodo raíz. Debo usar una cabeza puntero al nodo raíz?

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return(node);
}
static int lookup(struct node* node,int target)
{
if(node==NULL)
{
return(0);
}
else
{
if(target == node->data)
{
return(1);
}
else
{
if(target < node->data)
{
return(lookup(node->left,target));
}
else
{
return(lookup(node->right,target));
}
}
}
}
struct node* insert(struct node* node, int data)
{
if(node==NULL)
{
return(newNode(data));
}   
else
{
if(data < node->data)
{
node->left =insert(node->left,data);
}
else
{
node->right=insert(node->right,data);
}
return(node);
}
}
struct node* delete(struct node* node, struct node* pnode, int target)
{
struct node* rchild;
struct node* rchildparent;
if(node==NULL)
{
return(pnode);
}
else
{
if(target == node->data)
{
if(node->left == NULL && node->right == NULL) //leaf node
{
if(pnode == NULL) //special case deleting the root node
{
free(node);
return(NULL);
}
if(pnode->left == node)
{
pnode->left = NULL;
}
else
{
pnode->right = NULL;
}
free(node);
return(pnode);
}
if(node->left ==NULL ) //one child
{
if(pnode == NULL) //deleting root having no left child
{
struct node* temp = node;
node = node->right;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->right;
}
else
{
pnode->right = node->right;
}   
free(node);
return(pnode);
}
if(node->right ==NULL ) //one child
{
if(pnode == NULL) //deleting root having no right child
{
struct node* temp = node;
node = node->left;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->left;
}
else
{
pnode->right = node->left;
}   
free(node);
return(pnode);
}
//two children case
rchild = node->right;
rchildparent=node;
while(rchild->left != NULL)
{
rchildparent=rchild;
rchild = rchild->left;
}
node->data=rchild->data;
if(rchildparent == node)
{
//rchildparent->right=rchild->right;
node->right=rchild->right;
}
else
{
//rchildparent->left=NULL;
rchildparent->left=rchild->right;
}
free(rchild);
if(pnode ==NULL) //root node
{
return(node);
}           
return(pnode);
}
else
{
if(target < node->data)
{
delete(node->left,node,target);
return(node);
}
else
{
delete(node->right,node,target);
return(node);
}
}
}
}
void printinorder(struct node* node)
{
if(node == NULL)
{
return;
}   
printinorder(node->left);
printf("%d\t",node->data);
printinorder(node->right);
}
int main()
{
clock_t start,end;
struct node* root = newNode(3);
insert(root,7);
insert(root,7);
insert(root,7);
printinorder(root);
printf("\n");
root = delete(root,NULL,6);
printinorder(root);
printf("\n");
}

EDITAR:
Fija el código como por @modifiable lvalue sugerencia. Ahora hay una manera que puedo mejorar la eliminación de la lógica?

  • Supongo que no hay ningún problema con el malloc en función de newNode. El problema está en la delete función de donde estoy liberando una copia local de el puntero al nodo raíz
  • Usted necesitará una RAÍZ especial de puntero que se deba pasar a la delete función. Otra solución podría ser escribir un no-recursiva delete función y causa para que devuelva un node* que sería la nueva raíz.
  • ¿De qué estás hablando? Dejando de lado el potencial NULO eliminar cuando malloc falla, newNode está bien.
  • Si te refieres a un headPtr sería un miembro en cada nodo, entonces probablemente no. Un padre ptr sería aconsejable-y uno puede comprobar para nodoraíz cuando los padres==este
InformationsquelleAutor arunmoezhi | 2013-03-07

3 Comentarios

  1. 1

    Me gustaría volver la cabeza nodo de eliminar y administrar la cabeza en su función principal como: root = delete(root, NULL, 10);, y yo haría lo mismo para insertar: root = insert(root,/*...*/);, ya que es una especie de la mitad parece que has hecho tú…

    • Gracias. Esto es simple y elegante. Hice el cambio y funciona bien para el caso de que me elimine la raíz.
    • Creo que lo que más me gusta de este es que es claro que a otras personas que head de hecho puede cambiar. Me gusta hacer esto para cualquiera de las funciones que pueden causar head a cambio (en otras situaciones, por ejemplo. las listas enlazadas, colas, etc, también). De esa manera, parece mucho menos probable que los problemas de los que cuelgan los punteros de la voluntad de los cultivos en grupo de proyectos y entornos comerciales. También podría ser una oportunidad para equilibrar el árbol, en este caso.
    • Uno piensa que todavía no estoy en mi delete es que cada vez que me echa para el caso especial de raíz de ser eliminados. Puedo evitar de alguna manera para mejorar el rendimiento?
    • En mi primera edición de su código, he quitado espacios en blanco innecesarios de la delete código: ideone.com/1yVNEP que he encontrado por la eliminación de la recursivo elementos, y de trabajo en términos de child, branch (un puntero, inicializado a &node, pero está establecida en el punto a de la rama tomadas durante la búsqueda) y parent en lugar de node y pnode podía quitar esa prueba y muchos otros para formar este (no probado) código: ideone.com/HpAOAP
    • Gracias por gastar su tiempo de depuración mi código. En realidad he hecho un poco de depuración así. Estaba teniendo problemas con el recursiva de retorno. Así que he modificado. Ahora funciona en casi todos los casos. Pero no estoy seguro de si me falta alguna..
    • permítanme también tratar de comprender el código y probarlo

  2. 0

    privado DataNode eliminar(nodo de datos de la raíz,int dValue){

    DataNode temp=null;
    if(root!=null){
    if(dValue<root.value){
    root.left=delete(root.left,dValue);
    }
    else if(dValue>root.value){
    root.right=delete(root.right,dValue);
    }
    else{
    if(root.left==null){
    temp=root.right;
    root.right=null;
    return temp;
    }
    else if(root.right==null){
    temp=root.left;
    root.left=null;
    return temp;
    }
    temp=MinBST(root.right);
    root.value=temp.value;
    //deleting inorder successor
    root.right=null;
    }
    }
    return root;

    }

    privado DataNode MinBST(DataNode raíz){

    if(root!=null){
    while(root.left!=null){
    root=root.left;
    }
    }
    return root;

    }

    Ir a través del enlace de eliminación de nodo de árbol binario

    https://www.youtube.com/watch?v=YK3tLMYk3nk

  3. 0
    //c tree
    #include<stdio.h>
    #include<conio.h>
    struct tree_node
    {
    struct tree_node*right,*left;
    int data;
    };
    struct tree_node*savetemp=NULL;
    struct tree_node* del(struct tree_node*,int);
    struct tree_node* insert(struct tree_node*,int);
    struct tree_node* travel(struct tree_node*,struct tree_node*);
    void inorder(struct tree_node *);
    int height(struct tree_node*);
    int noOfNode(struct tree_node *);
    void main()
    {
    struct tree_node* root=NULL;
    int item,cho;
    clrscr();
    do
    {
    printf("Enter your choice\n");
    printf("1.insert 2.delete 3.display 4.no of nodes 5.height 6.exit\n");
    scanf("%d",&cho);
    switch(cho)
    {
    case 1:{
    printf("Enter element to insert\n");
    scanf("%d",&item);
    root=insert(root,item);
    }
    break;
    case 2:{
    printf("Enter element to delete\n");
    scanf("%d",&item);
    root=del(root,item);
    if(savetemp!=NULL)//condition for any break link is present to insert or not
    travel(root,savetemp);//to insert break link during insertion
    }
    break;
    case 3:{
    printf("inorder travel\n");
    inorder(root);
    }
    break;
    case 4:{
    printf("No of nodes are: %d\n",noOfNode(root));
    }
    break;
    case 5:
    printf("height of tree %d",height(root));
    break;
    case 6:
    printf("Exiting");
    break;
    default : printf("wrong cho\n");
    }
    }while(cho!=6);
    getch();
    }
    void inorder(struct tree_node *root)
    {
    if (root != NULL)
    {
    inorder(root->left);
    printf("%d \n", root->data);
    inorder(root->right);
    }
    }
    struct tree_node* insert(struct tree_node*root,int item)
    {
    if(root==NULL)
    {
    struct tree_node* temp;
    temp=(struct tree_node*)malloc(sizeof(struct tree_node));
    temp->left=NULL;
    temp->right=NULL;
    temp->data=item;
    root=temp;
    }
    else
    {
    if(root->data<item)
    {
    root->right=insert(root->right,item);
    }
    else
    {
    root->left=insert(root->left,item);
    }
    }
    return(root);
    }
    struct tree_node* del(struct tree_node*root,int item)
    {
    if(item==root->data)
    {
    if(root->left==NULL&&root->right==NULL) //no child
    {
    root=NULL;
    }
    else if(root->left==NULL||root->right==NULL) //one child
    {
    if(root->left!=NULL) //left child
    {
    root=root->left;
    }
    else               //right child
    {
    root=root->right;
    }
    }
    else  if(root->left!=NULL&&root->right!=NULL) //both child
    {
    struct tree_node* temp;
    savetemp=root->right->left;
    temp=root;
    root=root->right;
    root->left=temp->left;
    }
    }
    else
    {
    if(root->data<item)
    {
    root->right=del(root->right,item);
    }
    else
    {
    root->left=del(root->left,item);
    }
    }
    return(root);
    }
    struct tree_node* travel(struct tree_node*root,struct tree_node*savetemp)
    {
    if (savetemp != NULL)
    {
    insert(root,savetemp->data);
    travel(root,savetemp->left);
    travel(root,savetemp->right);
    }
    return(root);
    }
    int height(struct tree_node*root)
    {
    int lheight,rheight;
    if(root==NULL)
    {
    return(-1);
    }
    else
    {
    lheight=height(root->left);
    rheight=height(root->right);
    }
    if(lheight>rheight)
    {
    return(lheight+1);
    }
    else
    {
    return(rheight+1);
    }
    }
    int noOfNode(struct tree_node *root)
    {
    static int count=0;
    if (root != NULL)
    {
    noOfNode(root->left);
    count=count+1;
    noOfNode(root->right);
    }
    return(count);
    }
    • Amablemente agregar más detalles
    • Por favor, añadir algunas explicaciones a este bloque de código.
    • echa un vistazo de nuevo he cambiado algo………

Dejar respuesta

Please enter your comment!
Please enter your name here