指定されたプレオーダートラバーサルからBSTを構築します-C++で1を設定します

事前注文トラバーサルが1つあるとします。このトラバーサルから。ツリーを生成する必要があるため、トラバーサルが[10、5、1、7、40、50]の場合、ツリーは-

これを解決するために、このトリックを使用します。秘訣は、各ノードに範囲{min…max}を設定することです。最初に、範囲を{INT_MIN…INT_MAX}として初期化します。最初のノードは確実に範囲内にあるため、その後ルートノードを作成します。左側のサブツリーを作成するには、範囲を{INT_MIN…root->data}として設定します。値が{INT_MIN…root->data}の範囲にある場合、その値は左側のサブツリーの一部です。適切なサブツリーを作成するには、範囲を{root->data…max…INT_MAX}として設定します。

例

#include <iostream>
using namespace std;
class node {
   public:
      int data;
      node *left;
      node *right;
};
node* getNode (int data) {
   node* temp = new node();
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
node* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) {
   if( *preord_index >= size )
   return NULL;
   node* root = NULL;
   if( key > min && key < max ){
      root = getNode( key );
      *preord_index += 1;
      if (*preord_index < size){
         root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size );
         root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size );
      }
   }
   return root;
}
node *makeTree (int pre[], int size) {
   int preord_index = 0;
   return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size );
}
void inord (node* node) {
   if (node == NULL)
      return;
   inord(node->left);
   cout << node->data << " ";
   inord(node->right);
}
int main () {
   int pre[] = {10, 5, 1, 7, 40, 50};
   int size = sizeof( pre ) / sizeof( pre[0] );
   node *root = makeTree(pre, size);
   cout << "Inorder traversal: ";
   inord(root);
}

出力

Inorder traversal: 1 5 7 10 40 50