c++ - 在二叉搜索树中显示节点的路径

Question

我正在尝试显示从 BST 的根节点到目标节点的路径。我的功能在前两层工作得很好，但在那之后就搞砸了。例如，测试编号为 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);
}

score 5 · Accepted Answer

您的代码证实了我的怀疑。您的方法很好 - 这是您6, 9, 4, 11, 10按以下顺序插入构建的树：

第一（6）：

第二 (9)

 6
  \
   9

第三（4）

  6
 / \
4   9

第四（11）：

第五（10）：

因此，搜索 10，将为您提供路径 (6,9,11,10)。

请注意，从根到 BST 中的元素的路径不能保证被排序 - 如果这是您所期望的。实际上，只有当节点位于树中最右叶的路径上时，才会对其进行排序。

代码中的另一个问题：搜索 7（或树中不存在的任何元素）会给你一些虚假的路径。

score 0 · Accepted Answer

该代码仅在输入值在树中时才有效。当您搜索一个不存在的值时，您正在寻找一个不在树中的节点

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);
    }
}

c++ - 在二叉搜索树中显示节点的路径

2 回答 2

Related

Reference