내 코드가 바이너리 검색 트리에서 사전 주문 양식을 올바르게 수행하지 않는 이유는 무엇입니까?

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보다 커서 삽입 할 때 올바른 아이가됩니다. 동일은 다음의 모든 문자열을 발생합니다

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

왼쪽에서 트리를 탐색 할 때 트리의 노드에 왼쪽 자식이 없으므로 그대로 목록을 인쇄합니다. 오른쪽에서 그것을 가로 지르면 바로 뒤쪽으로 인쇄합니다.

트리가 불균형이므로 예상되는 동작입니다. 내가 볼 수있는 코드에는 버그가 없습니다. 균형 조정을 추가하거나 다른 루트를 만들어보십시오.