バイナリ検索ツリーで、自分のコードがプリオーダフォームを正しくしないのはなぜですか？

Question

文字列のバイナリ検索ツリーのコードを編集しました。しかし、小さな問題があります。私が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; 
} 

Answer 1

A B C D E Fあなたのツリーは、基本的にリンクされたリストです。まず、Aを挿入すると、新しいルートになります。 BはAより大きく、挿入すると右の子になります。 >F - >B - - >C - >D - >E

A：同じことはすべて、次の文字列のために起こります。

左からツリーをトラバースすると、ツリー内のどのノードにも左の子がないので、リストをそのまま印刷します。あなたが右からそれを横断すると、あなたはそれを逆向きに印刷します。

ツリーがアンバランスなので、これは予想される動作です。私が見ることのできるコードにはバグはありません。バランシングを追加するか、別のルートを作成してください。