boolean関数は、C++ではない場合にtrueを返します

Question

私は、各タイプのトラバーサルで幅優先検索を使用してバイナリ検索ツリーを検索するプログラムを持っています。すべての関数が動作して実行されますが、最後のトラバーサル、ポストオーダートラバーサルは、ツリーにない数値を検索するときにtrueを返します。私はプログラムをデバッグして、それがポストオーダートラバーサル関数でツリー全体を走っているのを見ましたが、実際には一度も真を返すことはありませんが、依然として真の出力をプリントアウトしています。なぜ誰かが私に言うことができますか？

#include <queue> 
#include <iostream> 
using namespace std; 

struct Node 
{ 
    int data; 
    Node *left, *right; 
}*root; 

Node *createNode(int data) 
{ 
    Node *Tnode = new Node; 

    Tnode->left = NULL; 

    Tnode->right = NULL; 

    Tnode->data = data; 

    return Tnode; 
} 

vbool breadthFirstSearch(Node *node, int item) 
{ 
    queue<Node*> q; 

    if(root) 
    { 
     q.push(root); 
     while(!q.empty()) 
     { 
      Node *d = q.front(); 
      q.pop(); 
      if(d->data == item) 
       return true; 
      if(d->left) 
       q.push(d->left); 
      if(d->right) 
       q.push(d->right); 

     } 
    } 
    return false; 
} 

bool inorderTraversal(Node *node, int item) 
{ 
    if(node == NULL) 
     return false; 
    inorderTraversal(node->left, item); 
    if(node->data == item) 
     return true; 
    inorderTraversal(node->right, item); 
} 

bool preorderTraversal(Node *node, int item) 
{ 
    if(node == NULL) 
     return false; 
    if(node->data == item) 
     return true; 
    preorderTraversal(node->left, item); 
    preorderTraversal(node->right, item); 
} 

bool postorderTraversal(Node *node, int item) 
{ 
    if(node == NULL) 
     return false; 
    postorderTraversal(node->left, item); 
    postorderTraversal(node->right, item); 
    if(node->data == item) 
     return true; 
} 

int main() 
{ 
    root = createNode(20); 
    root->left = createNode(10); 
    root->left->left = createNode(5); 
    root->left->right = createNode(15); 
    root->right = createNode(30); 
    root->right->left = createNode(25); 
    root->right->right = createNode(35); 

    cout<<"\n-----Breadth First Search Traversal-----\n"; 

    if(breadthFirstSearch(root, 35) == true) 
    { 
     cout<< "The item 35 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 35 is not in the tree\n"; 
    } 
    if(breadthFirstSearch(root, 29) == true) 
    { 
     cout<< "The item 29 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 29 is not in the tree\n"; 
    } 

    cout<<"\n-----Inorder Search Traversal-----\n"; 

    if(inorderTraversal(root, 35) == true) 
    { 
     cout<< "The item 35 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 35 is not in the tree\n"; 
    } 
    if(inorderTraversal(root, 29) == true) 
    { 
     cout<< "The item 29 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 29 is not in the tree\n"; 
    } 
    cout<<"\n-----Preorder Search Traversal-----\n"; 

    if(preorderTraversal(root, 35) == true) 
    { 
     cout<< "The item 35 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 35 is not in the tree\n"; 
    } 
    if(preorderTraversal(root, 29) == true) 
    { 
     cout<< "The item 29 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 29 is not in the tree\n"; 
    } 
    cout<<"\n-----Postorder Search Traversal-----\n"; 

    if(postorderTraversal(root, 35) == true) 
    { 
     cout<< "The item 35 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 35 is not in the tree\n"; 
    } 
    if(postorderTraversal(root, 29) == true) 
    { 
     cout<< "The item 29 is in the tree\n"; 
    } 
    else 
    { 
     cout << "The item 29 is not in the tree\n"; 
    } 
    return 0; 
} 

他のトラバーサルはそれぞれ、35がツリーにあり、29がツリーにないことを正しく示しています。たとえ29がチェックされているときにtrueが返されなくても、ポストオーダーだけが29にツリーを表示します。私は何か小さくて愚かな行方不明だと確信していますが、私はそれを見つけることができないようです。

Answer 1

postorderTraversalノードがnullでなく、そのキーがitemでない場合、関数は何も返しません。これは未定義の動作です。

Answer 2

bool preorderTraversal(Node *node, int item) 
{ 
    if(node == NULL) 
     return false; 
    if(node->data == item) 
     return true; 
    preorderTraversal(node->left, item); 
    preorderTraversal(node->right, item); 
} 

bool preorderTraversal(Node *node, int item) 
{ 
    if(node == NULL) 
     return false; 
    if(node->data == item) 
     return true; 
    return preorderTraversal(node->left, item) || preorderTraversal(node->right, item); 
} 

も

他の機能に変更します。

Answer 3

値を返すが、未定義の動作を呼び出さない関数を記述する。

これを確認する最も簡単な方法は、これらの関数の最後にcout行を追加し、それらのいずれかが実行されるかどうかを確認することです。

bool inorderTraversal(Node *node, int item) 
{ 
    if (node == NULL) 
     return false; 
    inorderTraversal(node->left, item); 
    if (node->data == item) 
     return true; 
    inorderTraversal(node->right, item); 
    cout << "OOPS1" << "\n"; // error if this line is executed 
} 

bool preorderTraversal(Node *node, int item) 
{ 
    if (node == NULL) 
     return false; 
    if (node->data == item) 
     return true; 
    preorderTraversal(node->left, item); 
    preorderTraversal(node->right, item); 
    cout << "OOPS2" << "\n"; // error if this line is executed 
} 

bool postorderTraversal(Node *node, int item) 
{ 
    if (node == NULL) 
     return false; 
    postorderTraversal(node->left, item); 
    postorderTraversal(node->right, item); 
    if (node->data == item) 
     return true; 
    cout << "OOPS3" << "\n"; // error if this line is executed 
} 

Live Example of compiler warnings and running of the program

あなたは「OOPSことがわかります"行はすべて実行され、値を返さずに関数の終わりを告げたことを示します。

したがって、戻って機能のロジックを再考する必要があります。他の答えはあなたが何をすべきかを示しています。