Почему мой код не будет правильно формировать форму предварительного заказа в бинарном дереве поиска?

Я отредактировал код для двоичного дерева поиска, для строк. Но есть небольшая проблема. Когда я ввожу простой ввод, такой как A B C D E F, моя программа говорит, что форма предварительного заказа A B C D E F… что это должно быть на самом деле A B D E C F,

Так как он должен напечатать слово в корне, затем напечатать слово в левом поддереве в предварительном порядке, а затем напечатать слово в
правильное поддерево в предзаказе.

Почтовый заказ также должен печатать D E B F C A но это печатает A B C D E F и по порядку должен был распечатать D B E A F C… но это просто дало мне F E D C B A,

Любая помощь приветствуется, я не знаю, что пошло не так.

Вот рабочий полный исходный код:

#include <iostream>
#include <string>
#include <conio.h>
using namespace std;

class Node {
string word;
Node* left;
Node* right;
public:
Node() { word=-1; left=NULL; right=NULL; };
void setWord(string aWord) { word = aWord; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
string Word() { return word; };
Node* Left() { return left; };
Node* Right() { return right; };
};

class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(string word);
void inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
void addNode(string word, Node* leaf);
void freeNode(Node* leaf);
};

Tree::Tree() {
root = NULL;
}

Tree::~Tree() {
freeNode(root);
}

void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}

void Tree::addNode(string word) {
if ( root == NULL ) {
Node* n = new Node();
n->setWord(word);
root = n;
}
else {
addNode(word, root);
}
}

void Tree::addNode(string word, Node* leaf) {
if ( word <= leaf->Word() ) {
if ( leaf->Left() != NULL )
addNode(word, leaf->Left());
else {
Node* n = new Node();
n->setWord(word);
leaf->setLeft(n);
}
}
else {
if ( leaf->Right() != NULL )
addNode(word, leaf->Right());
else {
Node* n = new Node();
n->setWord(word);
leaf->setRight(n);
}
}
}

void Tree::inOrder(Node* n) {
if ( n ) {
inOrder(n->Left());
cout << n->Word() << " ";
inOrder(n->Right());
}
}

void Tree::preOrder(Node* n) {
if ( n ) {
cout << n->Word() << " ";
preOrder(n->Left());
preOrder(n->Right());
}
}void Tree::postOrder(Node* n) {
if ( n ) {
postOrder(n->Left());
postOrder(n->Right());
cout << n->Word() << " ";
}
}

int main() {
string word;
Tree* tree = new Tree();
while(word != "end"){
cin >> word;
if(word == "end"){
break;
}
tree->addNode(word);
}

cout << "In order traversal" << endl;
tree->inOrder(tree->Root());
cout << endl;

cout << "Pre order traversal" << endl;
tree->preOrder(tree->Root());
cout << endl;

cout << "Post order traversal" << endl;
tree->postOrder(tree->Root());
cout << endl;

delete tree;
_getch();
return 0;
}

1

Решение

В вашем тестовом примере A B C D E F Ваше дерево — это в основном связанный список. Сначала вы вставляете A, так что это становится вашим новым корнем. B больше чем A, поэтому, когда вы вставляете его, он идет как правильный ребенок. То же самое происходит для всех следующих строк:

A->B->C->D->E->F,

Поэтому, когда вы пересекаете свое дерево слева, вы просто распечатываете свой список таким, какой он есть, поскольку ни в одном из узлов дерева нет левого потомка. Когда вы пересекаете его справа, вы просто печатаете его задом наперед.

Поскольку ваше дерево не сбалансировано, это ожидаемое поведение. В вашем коде нет ошибок из того, что я вижу. Попробуйте добавить балансировку или сделать другой рут.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]