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.