バイナリ検索ツリー印刷の問題

Question

私は、グラフィカルなSFML BSTメニューシステムで作業しています。私はテストファイルを持っています。それらのうちのいくつかは期待される出力を与えるが、他の出力は期待しない。私は数日後には何かを理解しようとしていましたが、私は理由を見ることができません。数字は正確にツリーに挿入されているようですが、重複した数字を持つ入力は、すべてのノードが出力されるわけではないので、ツリーのトラバーサルの構造を破壊するようです。下記の私のコードと例を見てください。

私は自分の.hファイルにストラットを持っています。これはかなりうまく動作します。

誰かがなぜこれらのいくつかがすべてのノードを通過していない理由を教えてもらえますか？

入力：1,3,5,6,7,8,9,10 出力：期待通りにグラフが見え、トラバーサルが期待通りです。

入力：（期待されていない）3,4,99,3,10,11,10 出力3,3,10,10

入力：10,3,10,24,3,20 出力：実際には3,3,10,10,24

//Binary Search Tree Program 
#include "BinarySearchTree.h" 

using namespace std; 

sf::CircleShape shape(50); 

BinarySearchTree::BinarySearchTree() 
{ 
    root = NULL; 

    if (!font.loadFromFile("font.ttf")) 
     cout << "Error loading font!"; 
} 


void BinarySearchTree::loadFile(int num) { 
    data.clear(); 
    string s = to_string(num); 
    string text; 
    string temp; // Added this line 
    ifstream file; 
    file.open("files/file" + s + ".txt"); 

    while (!file.eof()) 
    { 
     getline(file, temp); 
     text.append(temp); // Added this line 
    } 

    std::istringstream ss(text); 
    std::string token; 
    while (std::getline(ss, token, ',')) { 
     std::cout << token << ','; 
     std::string myString = token; 
     int value = atoi(myString.c_str()); //value = 45 
     data.push_back(value); 
    } 
} 

void BinarySearchTree::passToinsert() 
{ 
    for (std::vector<int>::iterator it = data.begin(); it != data.end(); ++it) { 
     insert(*it); 
     //cout << *it; 
    } 
} 


void BinarySearchTree::insert(int d) 
{ 
    tree_node* t = new tree_node; 
    tree_node* parent; 
    t->data = d; 
    t->left = NULL; 
    t->right = NULL; 
    parent = NULL; 

    // is this a new tree? 
    if (isEmpty()) root = t; 
    else 
    { 
     //Note: ALL insertions are as leaf nodes 
     tree_node* curr; 
     curr = root; 
     // Find the Node's parent 
     while (curr) 
     { 
      parent = curr; 
      if (t->data > curr->data) curr = curr->right; 
      else curr = curr->left; 
     } 

     if (t->data < parent->data) { 
      parent->left = t; 
      cout << "L-" << t->data<<endl; 
     } 
     else { 
      parent->right = t; 
      cout << "R-" << t->data << endl; 

     } 
    } 
} 


void BinarySearchTree::print_inorder() 
{ 
    inorder(root); 
} 

void BinarySearchTree::inorder(tree_node* p) 
{ 
    if (p != NULL) 
    { 
     if (p->left) inorder(p->left); 
     cout << " " << p->data << " "; 
     if (p->right) inorder(p->right); 
    } 
    else return; 
} 

void BinarySearchTree::print_postorder() 
{ 
    postorder(root, 100,0,0,0,0); 
} 


void BinarySearchTree::postorder(tree_node* p, int indent, int leftNodeCount, int rightNodeCount, int left, int right) 
{ 

    if (p != NULL) { 

     if (left = 1) { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (leftNodeCount * 80))); 
      nodeCount++; 
      leftNodeCount++; 
     } 
     else if (right = 1) { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (rightNodeCount * 80))); 
      nodeCount++; 
      rightNodeCount++; 
     } 
     else { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (nodeCount * 80))); 
      nodeCount++; 
     } 


     if (p->right) { 
      postorder(p->right, indent + 80, leftNodeCount, rightNodeCount,left=0,right=1); 
     } 
     if (p->left) { 
      postorder(p->left, indent - 80, leftNodeCount, rightNodeCount, left = 1, right = 0); 
     } 
    } 
} 

//Draw sub menu heading text and options to screen 
void BinarySearchTree::drawNodes(sf::RenderWindow &window) 
{ 
    window.clear(); 

    for (int i = 0; i < 10; i++) 
    { 
     window.draw(nodes[i]); 
    } 

    window.display(); 
} 

Answer 1

、番号が正しくツリーに挿入されていません。主な問題はclass BinarySearchTreeのinsert()機能にあります。

whileループwhile (curr)では、左と右の切り替えはif-condition if (t->data > curr->data)によって管理されます。この場合は、t->data == curr->dataが左側に接続されているものとします。

whileループの後で、左右のスイッチは、if-condition if (t->data < parent->data)によって管理されます。ケースはt->data == parent->dataが右側に接続されているものとします。 そして左側にはない！

解決策 - 次のようにwhileループ内のスイッチ条件を入れ替えてください。代わりの

if (t->data < curr->data) { 
    curr = curr->left; 
} 
else { 
    curr = curr->right; 
} 

：（） `関数`後順で

if (t->data > curr->data) curr = curr->right; 
else curr = curr->left;