algorithm - 使用前序遍历的 BST

Question

仅给定其前序遍历，是否可以构造二叉搜索树？

我知道只有同时给出中序遍历和前序遍历才能构造二叉树。但我的问题是针对 Binary Search Tree 的。

例如：给定：5,3,1,4,7,8

  Construct : 

       5
    3    7 
  1   4    8

Answer 1

是的，您可以从前序遍历构造二叉搜索树。给定一个前序遍历 a_1, ..., a_n，将其分为三个段 a_1, (a_2,...,a_k) 和 (a_{k+1},..,a_n)，其性质为 a_ {k+1} 是预排序中第一个大于 a_1 的元素。

递归计算 (a_2,...,a_k) 的 BST T1 和 (a_{k+1},..,a_n) 的 BST T2，并将它们添加为以 a_1 为根的新 BST 的左右子树。

Answer 2

这里提供了一个更好的解释..

http://www.geeksforgeeks.org/archives/25203

Answer 3

在这里，您在构建树时使用数字的 inorder 属性。

1. 对于特定的中序和预序，树是固定的。
2. 如果只给出顺序，那么一棵树就有无限的可能性。
3. 同样，如果只给出预购，那么一棵树就有无限的可能性。

前任 ：

     a                             a
   /   \                            \
  b     e     and                    b
 / \   / \                            \
d  c  f   g                            d 
                                        \
                                         c
                                          \ 
                                           e
                                            \
                                             f
                                              \
                                               g

上述两棵树具有相同的前序，即a、b、d、c、e、f、g

这是因为我们没有考虑给定元素之间的任何顺序作为您给出的案例中的数字。

如果您在使用 BST 时需要订购，此链接提供了解决方案。

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

Answer 4

基于上述算法..我在 C++ 中的实现

node* buildtree(int[] preOrder,int start,int end) {

  if(start>end) return NULL;

  node *t = malloc(sizeof(node));

  // finds the index of the first element greater than preOrder[start]
  int index = find_index(preOrder, preOrder[start], start+1, end); 

  t->left = buildtree(preOrder,start+1,index-1);
  t->right = buildtree(preOrder,index,end);

  return t;

}

int find_index(int[] preOrder, int search_element, int start, int end) {

  for(int i=start;i<=end;i++) {
      if(preOrder[i]>search_element) return i;
  }
   return end+1;
 }