Pourquoi mon code ne fera-t-il pas le formulaire de précommande correctement dans l'arbre de recherche binaire?

Question

J'ai édité un code pour un arbre de recherche binaire, pour des chaînes. Mais il y a un petit problème. Lorsque j'entre une entrée simple comme A B C D E F, mon programme dit que le formulaire de pré-commande est A B C D E F ... ce qui devrait être A B D E C F.

Depuis, il faut imprimer le mot à la racine puis imprimez le mot à la sous-arborescence à gauche en pré-commande, puis imprimer le mot à le sous-arbre droit en pré-commande.

Publier devrait également imprimer D E B F C A mais il imprime A B C D E F et en ordre devrait avoir imprimé D B E A F C ... mais il m'a donné F E D C B A.

Toute aide est appréciée, je ne sais pas ce qui s'est mal passé.

Voici le code source complet de travail:

#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

Dans votre exemple de test A B C D E F votre arbre est essentiellement une liste chaînée. Tout d'abord, vous insérez A, il devient ainsi votre nouvelle racine. B est plus grand que A, donc quand vous l'insérez, il va comme un enfant droit. La même chose se produit pour toutes les chaînes suivantes:

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

Ainsi, lorsque vous traversez votre arbre à partir de la gauche, vous imprimez simplement votre liste telle qu'elle est car il n'y a aucun enfant à gauche dans l'un des nœuds de l'arbre. Lorsque vous le traversez depuis la droite, il vous suffit de l'imprimer en arrière.

Étant donné que votre arbre est déséquilibré, il s'agit d'un comportement attendu. Il n'y a pas de bugs dans votre code à partir de ce que je peux voir. Essayez d'ajouter un équilibre ou faites une autre racine.