recorrido - Implementación de árbol binario C++

podar arbol en c

Question

He estado intentando implementar un árbol de búsqueda binario en C ++ por diversión. Mi problema es que estoy teniendo problemas con mi función de inserción. Debajo está lo que tengo hasta ahora:

class TreeNode{

public: 
    int data;          
    TreeNode *left;    
    TreeNode *right;  
    void Insert(int value, TreeNode *x);
    void TreeNode::Print(TreeNode *x);
    TreeNode();
};


TreeNode::TreeNode(){

left = NULL;
right = NULL;

}

.

void TreeNode::Insert(int value, TreeNode *x){

    if(x->left == NULL && x->right == NULL){
           TreeNode *tree = new TreeNode();                        
           tree->datavalue;                               
           x->left = tree;                                  
    }

    else if(x->left == NULL && x->right != NULL){

           TreeNode *tree = new TreeNode();                
           tree->data = value;                          
           x->left = tree;                                 
    }

    else if(x->left != NULL && x->right == NULL){

           TreeNode *tree = new TreeNode();                      
           tree->data = value;                            
           x->right = tree;                          
    }

    else if(x->left != NULL && x->right != NULL){

        ??????

    }

}

Answer 1

No debe insertar a ciegas, siga la lógica a continuación. Si x.value es menor que el valor raíz, intente insertar a la izquierda. Si x.value es> = root.value, vaya a la derecha. Repite esta lógica hasta que toques un valor NULL. Ese será el lugar adecuado para insertar su elemento.

Podrías voltear la lógica, simplemente elegí "left" en <porque menos que un poco hace una flecha a la izquierda. <-: P

TreeNode *root = this;
TreeNode *parent = root;
//Traverse the tree, go left if x.val < , else go right(>=)
while(root) {
    parent = root;
    root = (root->value > x.value) ? root->left : root->right;
}
if(parent->value > x->value) 
    parent->left = x;
else
    parent->right = x;

Si no le importa ordenar, haga una primera búsqueda en profundidad con una cola.

queue<TreeNode*> nodes;
nodes.push(this);
while(1)
{
    if(!nodes.front()->left)
    {
        nodes.front()->left = x;
        return;
    } 
    else if (!nodes.front()->right)
    {
        nodes.front()->right = x;
        return;
    }
    nodes.push(nodes.front()->left);
    nodes.push(nodes.front()->right);
    nodes.pop();
}

Answer 2

Si desea insertar cuando tanto el hijo izquierdo como el derecho NO son nulos, entonces puede insertar el elemento moviéndolo recursivamente al nodo situado más a la izquierda del árbol. Y dado que solo está insertando valores sin un orden en particular, será difícil hacer un seguimiento. Más bien implemente un árbol de búsqueda binaria en ese caso.

else if(x->left != NULL && x->right != NULL){
         Insert(value,x->left);
         x-> data  = value;
         x->left = x->right = NULL;
}

Y lo más importante, inserte un caso BASE para salir de la recursión.