时间戳

首页 > 解决方案 > 树，无法正确删除节点

c++ - 树，无法正确删除节点

问题描述

我从这段代码中删除节点时遇到问题，如果我插入数字 12 并尝试删除它，它不会删除它，我尝试调试，似乎当它尝试删除时，它出错了树的。但是，如果我尝试删除它已经插入主节点的节点，它将删除它，或者我插入数字 21 它可以删除它，对不起，如果它是西班牙语，如果你要求它，我可以将它翻译成英文。问题在于 struct nodo* borrar_nodo(struct nodo* raiz, int llave，它只是返回并且没有找到我放入树中的 12 或其他数字。我尝试了其他线程中的代码有类似问题，所以我不知道在哪里我错了。

#include <bits/stdc++.h> 
using namespace std; 

struct nodo { 
    int llave; 
    struct nodo *izquierda, *derecha; 
}; 
  
{ 
    struct nodo* temp = new nodo; 
    temp->llave = llave; 
    temp->izquierda = temp->derecha = NULL; 
    return temp;
}; 

void Inorden(struct nodo* temp)
{ 
    if (!temp) 
        return; 
    Inorden(temp->izquierda); 
    cout << temp->llave << " "; 
    Inorden(temp->derecha); 
} 

void preorden(struct nodo* temp)
{ 
    if (!temp) 
        return; 
    cout << temp->llave << " "; 
    Inorden(temp->izquierda); 
    Inorden(temp->derecha); 
} 

void postorden(struct nodo* temp)
{ 
    if (!temp) 
        return; 
    Inorden(temp->izquierda);  
    Inorden(temp->derecha); 
    cout << temp->llave << " ";
} 


void insertar(nodo* temp, int llave) 
{ 
    queue<nodo*> fila; 
    fila.push(temp); 
  

    while (!fila.empty()) { 
        nodo* temp = fila.front(); 
        fila.pop(); 
  
        if (!temp->izquierda) { 
        temp->izquierda = NodoNuevo(llave); 
            break; 
        } else
            fila.push(temp->izquierda); 
  
        if (!temp->derecha) { 
        temp->derecha = NodoNuevo(llave); 
            break; 
        } else
            fila.push(temp->derecha); 
    } 
}  
    



struct nodo * valorMinimo(struct nodo* nodo) 
{ 
    struct nodo* actual = nodo; 
  

    while (actual && actual->izquierda != NULL) 
        actual = actual->izquierda; 
  
    return actual; 
} 
  

struct nodo* borrar_nodo(struct nodo* raiz, int llave) 
{ 
 
    if (raiz == NULL) return raiz; 
  
    else if (llave < raiz->llave) 
        raiz->izquierda = borrar_nodo(raiz->izquierda, llave); 
  
    else if (llave > raiz->llave) 
        raiz->derecha = borrar_nodo(raiz->derecha, llave); 

    else
    { 
        if (raiz->izquierda == NULL) 
        { 
            struct nodo *temp = raiz->derecha; 
            free(raiz); 
            return temp; 
        } 
        else if (raiz->derecha == NULL) 
        { 
            struct nodo *temp = raiz->izquierda; 
            free(raiz); 
            return temp; 
        } 
  
        struct nodo* temp = valorMinimo(raiz->derecha); 
  
        
        raiz->llave = temp->llave; 
  
        raiz->derecha = borrar_nodo
        (raiz->derecha, temp->llave); 
    } 
    return raiz; 
} 
  

int main() 
{ 
int opcion;
int ins, borrar; 
    struct nodo* raiz = NodoNuevo(14); 
    raiz->izquierda = NodoNuevo(4); 
    raiz->izquierda->izquierda = NodoNuevo(3); 
    raiz->izquierda->derecha = NodoNuevo(9); 
    raiz->izquierda->derecha->izquierda = NodoNuevo(7);
    raiz->derecha = NodoNuevo(15); 
do
    {
        cout << "\nMenu de Opciones" << endl;
        cout << "1. Crear tu nodo" << endl;
        cout << "2. Eliminar nodo" << endl;
        cout << "3. Mostrar nodos en: PREORDEN, INORDEN, POSTORDEN" << endl;
        cout << "4. SALIR" << endl;
        cin >> opcion;
switch (opcion) {
    case 1:
    cout << "\nQue nodo (edad) desea introducir al arbol: \n"; 
    cin >> ins;
    insertar(raiz, ins);
    cout <<"\nNodo: " << ins << " insertado en el arbol";
    break;
    case 2: cout << "\nQue nodo (edad) desea eliminar de la siguiente lista: \n"; 
    Inorden(raiz);
    cout << "\n"; 
    cin >> borrar;
    borrar_nodo(raiz, borrar);
    break;
    case 3:     cout << "Recorrido en inorden : \n"; 
    Inorden(raiz);
    cout << "\nRecorrido en preorden: \n"; 
    preorden(raiz);
    cout << "\nRecorrido en postorden : \n"; 
    postorden(raiz);
    break;
 } 
}while (opcion != 5); 
}

标签： c++structtreebinary-search-tree

解决方案

谢谢你们的推荐，不知道 bits/stdc 和使用命名空间是不好的做法，我会改进我的识别。

我解决了我的问题，我使用了一种简单的方法来插入节点和数据，它服务于它的目的，它是用于关于数据结构的大学作业。如果有一个学生会说西班牙语以备将来参考，我使用了 Luis Joyanes Aguilar 第 548-589 页的“Programación en Java 2: Algoritmos, Estructura de datos y programación orientada a objetos”一书，它完美地解释了如何在一颗树。

 struct nodo* insert(struct nodo* nodo, int llave) 
{ 
    if (nodo == NULL) return NodoNuevo(llave);

    if (llave < nodo->llave)
        nodo->izquierda = insert(nodo->izquierda, llave); 
    else if (llave > nodo->llave)
        nodo->derecha = insert(nodo->derecha, llave); 

    return nodo; 
}

推荐阅读