algorithm - 我们是否可以简单地通过将前序遍历中的元素按顺序插入到空树中来从前序遍历构造BST？

Question

给定 BST 的先序遍历。我必须构建 BST。我是否可以通过先创建一个空 BST 然后将先序遍历中的元素从第一个元素开始到最后一个元素一个一个地插入到空 BST 中来从前序遍历构造 BST？

例如，考虑以下 BST:-

    10
   /   \
  5     40
 /  \      \
1    7      50

它的前序遍历是:

10 5 1 7 40 50

通过创建一个空的 BST，然后从第一个元素开始一个一个地插入前序遍历中的元素，得到确切的 BST，解释如下:

(empty tree)

插入前序遍历第一个元素:10

   10

插入前序遍历的第二个元素:5

   10
   /
  5

同样，

     10       
   / 
  5  
 /  
1   

     10
   /   
  5    
 /  \  
1    7 

     10
   /   \
  5     40
 /  \ 
1    7

     10
   /   \
  5     40
 /  \      \
1    7      50

在这里，我只是通过将前序遍历中的元素一个一个地插入到一个空树中来构建精确的 BST。该算法是否适用于所有情况？是否存在该算法不起作用的情况？

void insertIntoTree(struct* Node,int val)
{
   if(Node == NULL)
   {
       Node = createNewNode(val);
       return;
   }
   if(val < Node->val)
      insertIntoTree(Node->left,val);
   else
      insertIntoTree(Node->right,val);

}
int main()
{
  int preorderlist[] = { 10,5,1,7,40,50};

  for(int i=0;i <= preorderlist.size();i++)
  {
     insertIntoTree(TreeRoot,preorderlist[i]);
  }

}

Answer 1

您的代码可以运行，但效率不高。您没有使用数组的预购属性。事实上，您的代码是从一般数组构建 BST。为了改进您的算法，您可以递归地构建树，在每个节点中保留 minRange 和 maxRange。如果下一个元素超出了当前节点的范围，则返回父节点。

编辑:您将得到相同的树，但如果原始树是平衡的，复杂度将为 O(N*logN)，否则为 O(N^2)。

我不想为您编写代码，但我会尝试更好地解释我的算法:保留指向您插入的最后一个节点的指针。同样对于每个节点保持子树的范围。插入元素时，从您保留的指针开始。如果新节点在范围内，则将其作为子节点插入并更新指针。如果它不在范围内，则将指针向上移动到其父级并尝试插入到那里。要更新范围:如果您将新节点作为左子节点插入，请将其 maxRange 设置为其父值。并分别为右 child 设置 minRange。对于所有情况，复杂度都是 O(N)。