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

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

Answer 1

你的代码证实了我的怀疑.你的方法很好 - 这是你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(或树中不存在的任何元素)将给你一些虚假的路径.