algorithm - 事前注文トラバーサルを使用した BST

Question

preorder traversal のみが与えられた二分探索木を構築することは可能ですか?

inorder と preorder traversal の両方が指定された場合にのみ、バイナリ ツリーを構築できることを私は知っています。しかし、私の質問は 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) の 3 つのセグメントに分割します。 {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

上記のアルゴリズムに基づいて.. 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;
 }