Корневой узел в дереве бинарного поиска пуст
Я изучаю с ++ и структуры данных
Я реализовал бинарный поиск Tress
может ли кто-нибудь сказать, что проблема в этом коде
Я получаю корневой указатель как ноль.
В принципе не удалось создать дерево.
Моя конечная цель — найти ключ в дереве. я написал метод для этого. но, к сожалению, я не могу создать дерево. Я проверил это, написав код обхода.
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
// Node structure
struct TreeNode {
int value;
int key;
struct TreeNode *left;
struct TreeNode *right;
TreeNode()
{
left=NULL;
right=NULL;
}
};
void preOrder (TreeNode *);
void insertNode(TreeNode *, int, int);
TreeNode* findNode(TreeNode *aNode, int);
void main() {
TreeNode *root = NULL;
for(int i = 15; i<= 300; i+=15) {
insertNode(root, i, i);
if (root!=NULL) {
cout<<root ->value<<endl;
}
}
cout<<"The preorder traversal"<<endl;
preOrder(root);
getch();
}
void preOrder (TreeNode *p) {
if (p!=NULL) {
cout<<p ->value<<endl;
preOrder(p ->left);
preOrder(p ->right);
} else{
cout << "NULL"<<endl;
}
}
void createNewNode(TreeNode *newNode, int aValue, int aKey) {
newNode = new TreeNode; // create new node
newNode -> value = aValue; // set data
newNode -> key = aKey; // set key
cout<<newNode ->value<<endl;
// Set left,right
newNode -> left = newNode -> right = NULL;
}
void insertNode(TreeNode *aNode, int aValue, int aKey) {
if (aNode == NULL) {
TreeNode *newNode = new TreeNode; // create new node
newNode -> value = aValue; // set data
newNode -> key = aKey; // set key
//createNewNode(newNode, aValue, aKey);
if(newNode == NULL) {
cout<< "Null returned"<<endl;
} else {
cout<< newNode -> key <<endl;
}
aNode = newNode;
} else if (aKey == aNode->key) {
cout<<aKey<<endl;
return;
} else if (aKey < aNode->key) {
insertNode((aNode->left), aValue, aKey);
} else {
insertNode((aNode->right), aValue, aKey);
}
}
TreeNode* findNode(TreeNode *aNode, int aKey) {
if (aNode == NULL) {
return NULL;
} else if (aNode->key == aKey) {
return aNode;
} else if (aKey <= aNode->key) {
return findNode(aNode->left, aKey);
} else {
return findNode(aNode->right, aKey);
}
}
Решение
Основная проблема, по мне в вашем коде вставки узла, вы передаете aNode по вызову по значению вместо вызова по ссылке. Вместо того, чтобы просто использовать TreeNode *aNode в вашей функции вставки узла, попробуйте использовать TreeNode * &aNode,
Другие решения
Проблема в том, что ваш insertNode функция пытается создать новый TreeNode если вы передаете NULL, но это не влияет на указатель, который вы передали.
Например,
void foo(int * p) {
p = new int;
}
int main() {
int* test = NULL;
foo(test);
// test is still NULL, but foo created an int internally
}
Что вам нужно сделать, это передать указатель в качестве ссылки, так что foo изменит указатель, который вы даете (а не просто создаете). Как это:
void foo(int *& p) { // Notice I'm now using a reference to a pointer
p = new int;
}
int main() {
int* test = NULL;
foo(test);
// test will now point to whatever foo created
}
Я думаю, вы научитесь лучше, если сейчас попробуете применить это к своему примеру. Постарайтесь точно понять, почему это нужно сделать. Просто спросите, если вам нужно больше разъяснений.