Geek asks and answers

BST using pre-order bypass

Is it possible to build a binary search tree? Only to circumvent it?

I know that a binary tree can only be built if a traversal and an order of assumptions are specified. But my question is about the binary search tree.

For example: Subject to: 5,3,1,4,7,8

  Construct : 

       5
    3    7 
  1   4    8
+5
source share
4 answers

Yes, you can build a binary search tree from a pre-order bypass. Given the preliminary tour a_1, ..., a_n, we divide it into three segments a_1, (a_2, ..., a_k) and (a_ {k + 1}, .., a_n), with the property that a_ {k + 1} - the first element in the pre-order, which is greater than a_1.

BST T1 (a_2,..., a_k) BST T2 (a_ {k + 1},.., a_n) BST a_1.

+11

inorder .

  • .
  • inorder, .
  • , , .

:

     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/

+1
source

Based on the above algorithm .. my implementation in 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;
 }
0
source

More articles:


All Articles