Я пытался реализовать двоичное дерево поиска в 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();
}
Если вы хотите вставить, когда левый и правый дочерние элементы НЕ равны NULL, вы можете вставить элемент, рекурсивно переместившись к самому левому узлу дерева. А поскольку вы просто вводите значения в произвольном порядке, будет сложно отслеживать. Скорее реализуйте бинарное дерево поиска в этом случае.
else if(x->left != NULL && x->right != NULL){
Insert(value,x->left);
x-> data = value;
x->left = x->right = NULL;
}
И самое главное, вставить BASE case для выхода из рекурсии.