Встановлення бінарного дерева C ++ - c ++, функція, дерево, вставка, бінарне дерево

Я намагався реалізувати двійкове дерево пошуку в C ++ для розваги Проблема полягає в тому, що у мене виникають проблеми з моєю функцією вставки. Нижче наведено те, що у мене є:

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){

??????

}

}

Відповіді:

Не слід вставляти сліпо, дотримуйтесь логікинижче. Якщо значення x.value менше кореневого значення, спробуйте вставити зліва. Якщо x.value>> = root.value, перейдіть праворуч. Повторюйте цю логіку, поки не досягнете значення NULL. Це буде правильне місце для вставки вашого елемента.

Ви можете перевернути логіку, я просто вибрав ліворуч на <, тому що менше, ніж вид робить стрілку ліворуч. <-: С

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;

Якщо ви не турбуєтесь про замовлення, спочатку виконайте глибокий пошук у черзі.

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();
}

Якщо ви хочете вставити як ліворуч, так і праворучдитина НЕ є нульовим, то ви можете вставити елемент шляхом рекурсивного переміщення до самого лівого вузла дерева. А оскільки ви просто вставляєте значення в не конкретному порядку, це буде важко відстежувати. Замість цього застосуйте Двійкове пошукове дерево у такому випадку.

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

І найголовніше, вставте БАЗОВИЙ випадок, щоб вийти з рекурсії.