Warum wird mein Code im Binary Search Tree das Vorbestellformular nicht korrekt ausfüllen?

Question

Ich habe einen Code für einen binären Suchbaum für Strings bearbeitet. Aber da ist ein kleines Problem. Wenn ich eine einfache Eingabe wie A B C D E F gebe, sagt mein Programm, dass das Vorbestellformular A B C D E F ... ist, was eigentlich A B D E C F sein sollte.

Da, sollte es das Wort an der Wurzel drucken dann das Wort an der linken Unterbaum in vorbestellbarer drucken und dann das Wort an rechten Teilbaum in vorbestellbarer drucken.

Beitrag Auftrag sollte auch D E B F C A drucken, aber er druckt A B C D E F und in Ordnung D B E A F C haben sollte gedruckt ... aber es gab mir nur F E D C B A.

Jede Hilfe wird geschätzt, ich weiß nicht, was schief gelaufen ist.

Hier ist die Arbeits vollständigen Quellcode:

#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; 
} 

Answer 1

In Ihrem Testbeispiel A B C D E F Ihr Baum ist im Grunde eine verknüpfte Liste. Zuerst fügen Sie A ein, so dass es zu Ihrem neuen root wird. B ist größer als A, also wenn Sie es einfügen, geht es wie ein richtiges Kind. Das gleiche geschieht für alle nächsten Strings:

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

Wenn Sie also Ihren Baum von links durchqueren, drucken Sie Ihre Liste einfach so, wie sie ist, da sich in keinem der Knoten in der Struktur ein linkes Kind befindet. Wenn Sie es von rechts durchqueren, drucken Sie es einfach rückwärts.

Da Ihr Baum unausgeglichen ist, ist dies ein erwartetes Verhalten. Es gibt keine Fehler in Ihrem Code von dem, was ich sehen kann. Versuchen Sie, einen Ausgleich hinzuzufügen oder einen anderen Stamm zu erstellen.