1

BST のルート ノードからターゲット ノードへのパスを表示しようとしています。私が持っている関数は、最初の 2 つのレイヤーでは正常に機能しますが、その後はうまくいきません。たとえば、テスト番号は 6、9、4、11、10 の順に挿入されます。6、9、または 4 を検索すると機能します (例: "6 9")。しかし、11 または 10 を試してみると、両方が表示され、順不同で表示されます。なぜだろうとちょっと困っています。どんなアイデアも素晴らしいでしょう！

template <class T>
void BST<T>::displayPath(T searchKey, BST<T> *node)
{
    if (searchKey == node->mData)
    {
        cout << node->mData << " ";
    }

    else if (searchKey < node->mData )
    {
        cout << node->mData << " ";
        displayPath(searchKey, node->mLeft);
    }
    else// (searchKey > node->mData)
    {
        cout << node->mData << " ";
        displayPath(searchKey, node->mRight);
    }
}

これが挿入機能です。番号は上記の順序で挿入されます。

template <class T>
void BST<T>::insert(BST<T> *&node, T data)
{
   // If the tree is empty, make a new node and make it 
   // the root of the tree.
   if (node == NULL)
   { 
      node = new BST<T>(data, NULL, NULL);
      return;
   }

   // If num is already in tree: return.
   if (node->mData == data)
      return;

   // The tree is not empty: insert the new node into the
   // left or right subtree.
   if (data < node->mData)
          insert(node->mLeft, data);
   else
      insert(node->mRight, data);
}
4

2 に答える 2

5

あなたのコードは私の疑いを裏付けています。あなたの方法は問題ありません-これは、6, 9, 4, 11, 10この順序で挿入して構築したツリーです:

最初 (6):

 6

秒 (9)

 6
  \
   9

3位 (4)

  6
 / \
4   9

4番目 (11):

   6
  / \
 /   \
4     9
       \
        \
         11

5番目 (10):

   6
  / \
 /   \
4     9
       \
        \
         11
         /
        /
       10

したがって、10 を検索すると、パス (6,9,11,10) が得られます。

ルートから BST 内の要素へのパスがソートされるとは限らないことに注意してください。実際、ノードがツリーの右端の葉へのパス上にある場合にのみソートされます。

コードの別の問題: 7 (またはツリーに存在しない要素) を検索すると、偽のパスが表示されます。

于 2012-10-24T07:16:18.623 に答える
0

コードは、入力値がツリーにある場合にのみ機能します。そこにない値を検索するときは、ツリーにないノードを探していることになります

template <class T>
void BST<T>::displayPath(T searchKey, BST<T> *node)
{
    if (searchKey == node->mData)
    {
    cout << node->mData << " ";
    }

    else if (searchKey < node->mData )
    {
        cout << node->mData << " ";
        if (node->mLeft == NULL) // When trying to access a node that isn't there
            cout << "Not Found\n";
        else
        displayPath(searchKey, node->mLeft);
    }
    else // (searchKey > node->mData)
    {
        cout << node->mData << " ";
        if (node->mRight == NULL)
            cout << "Not Found\n";
        else
            displayPath(searchKey, node->mRight);
    }
}
于 2018-03-23T00:45:51.883 に答える