struct BSTreeNode
{
struct BSTreeNode *leftchild;
AnsiString data;
struct BSTreeNode *rightchild;
};
struct BSTreeNode * root;
String tree = "";
struct BSTreeNode * newNode(AnsiString x)
{
struct BSTreeNode * node = new struct BSTreeNode;
node->data = x;
node->leftchild = NULL;
node->rightchild = NULL;
return node;
}
struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x)
{ if (node == NULL) return newNode(x);
if (x < node->data)
node->leftchild = insertBSTree(node->leftchild, x);
else
node->rightchild = insertBSTree(node->rightchild, x);
return node;
}
void printBSTree(struct BSTreeNode * node)
{ if (node != NULL)
{ printBSTree(node->leftchild);
tree += node->data+"_";
printBSTree(node->rightchild);
}
}
//--- insert button ---
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString data;
data = Edit1->Text;
root = insertBSTree(root, data);
tree = "";
printBSTree(root);
Memo1->Lines->Add(tree);
}
Предположим, что я вставляю A、B、C、D、E、F、G в двоичное дерево (Button1Click — это кнопка для вставки данных в двоичное дерево) двоичное дерево должно быть таким
A
/ \
B C
/ \ / \
H J D E
/ \
F G
но оказалось, что это похоже на
A
\
B
\
C
\
D
\
E
\
F
\
G
struct BSTreeNode ---> узел дерева
struct BSTreeNode * newNode(AnsiString x) ---> создание нового узла
button1Нажмите ---> вставьте данные из Edit->text; к бинарному дереву.
InsertBSTree ---> если узел имеет значение NULL, создайте новый узел. Вставка данных в leftchild/rightchild
@prapin: можно также предложить использовать ссылки или сделать эти функции функциями-членами.
Пожалуйста, опубликуйте минимальный пример проблемы (похоже, достаточно только A и B) и то, что вы сделали, чтобы попытаться диагностировать проблему (т. е. использовать отладчик, чтобы увидеть, где он сначала не сделал то, что вы ожидали).
Каковы значения data
в вашем примере?
Код выглядит нормально, неясно, почему вы ожидаете ожидаемого результата. Это недопустимое двоичное дерево поиска для показанных данных.
Я отладил и ошибок нет. «данные» хранят значение двоичного дерева. Например, если я вставлю «A» в двоичное дерево (Button1Click), значение «A» будет сохранено в «данных». Ассистент моего учителя рассказал мне, что мое бинарное дерево оказалось таким, как второе в посте.
Вы создали двоичное дерево поиска, используя <
, чтобы определить, в какую ветвь вставить:
struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x) { if (node == NULL) return newNode(x); if (x < node->data) node->leftchild = insertBSTree(node->leftchild, x); else node->rightchild = insertBSTree(node->rightchild, x); return node; }
Ваш второй пример — двоичное дерево поиска, но не сбалансированное.
Ожидаемый результат не может быть создан с помощью показанных функций, поскольку они поддерживают строгий инвариант, при котором левая ветвь должна содержать только значения, меньшие корня. Эффективность двоичного дерева поиска применима только к сбалансированным.
Сбалансированное двоичное дерево поиска, содержащее эти данные, будет выглядеть следующим образом, поскольку все задействованные деревья (включая поддеревья) сбалансированы.
D
/ \
/ \
/ \
B F
/ \ / \
A C E G
Вы можете добиться этого, добавив механизм проверки сбалансированности вашего дерева и внося коррективы, «поворачивая» деревья влево или вправо.
A
\
B
\
C
Становится сбалансированным путем поворота влево вокруг наименьшего значения в правой части дерева.
B
/ \
A C
Чтобы сбалансировать исходное дерево:
A
\
B
\
C
\
D
\
E
\
F
\
G
Вы проверите каждое поддерево, чтобы убедиться, что оно сбалансировано. Первое несбалансированное поддерево — это E, F, G.
A
\
B
\
C
\
D
\
F
/ \
E G
Тогда мы увидим, что D, E, F, G несбалансированы вправо.
A
\
B
\
C
\
E
/ \
D F
\
G
И так далее...
A
\
B
\
D
/ \
C E
\
F
\
G
A
\
B
\
D
/ \
C F
/ \
E G
A
\
C
/ \
B D
\
F
/ \
E G
A
\
C
/ \
B E
/ \
D F
\
G
A
\
D
/ \
C E
/ \
B F
\
G
A
\
D
/ \
C F
/ / \
B E G
B
/ \
A C
\
D
\
F
/ \
E G
B
/ \
A C
\
E
/ \
D F
\
G
B
/ \
A D
/ \
C E
\
F
\
G
B
/ \
A D
/ \
C F
/ \
E G
C
/ \
B D
/ \
A F
/ \
E G
C
/ \
B E
/ / \
A D F
\
G
Если пойти еще на несколько шагов дальше:
D
/ \
C E
/ \
B F
/ \
A G
D
/ \
B E
/ \ \
A C F
\
G
D
/ \
/ \
/ \
B F
/ \ / \
A C E G
В C++ бесполезно использовать ключевое слово
struct
при указании типа.BSTreeNode
это уже типаж, не пишитеstruct BSTreeNode
везде.