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

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

これを解決するには、次の手順に従います-

• 空のスタックを作成する

• 最初の値をルートとして作成し、スタックにプッシュします。

• スタックが空でなく、次の値がスタックの最上位要素よりも大きい間、うんちを続けます。これを最後にポップされたノードの右の子にします。次に、新しいノードをスタックにプッシュします。

• 次の値がtop要素よりも小さい場合は、スタックtop要素の左の子として作成します。次に、新しいノードをスタックにプッシュします。

• すべてのプレオーダーリスト要素を確認するまで、手順2と3を繰り返します。

例

#include <iostream>
#include <stack>
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* constructTree ( int pre[], int size ) {
   stack<node*> stk;
   node* root = getNode( pre[0] );
   stk.push(root);
   int i;
   node* temp;
   for ( i = 1; i < size; ++i ) {
      temp = NULL;
      while ( !stk.empty() && pre[i] > stk.top()->data ) {
         temp = stk.top();
         stk.pop();
      }
      if ( temp != NULL) {
         temp->right = getNode( pre[i] );
         stk.push(temp->right);
      } else {
         node* peek_node = stk.top();
         peek_node->left = getNode( pre[i] );
         stk.push(stk.top()->left);
      }
   }
   return root;
}
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 = constructTree(pre, size);
   cout << "Inorder traversal: ";
   inord(root);
}

出力

Inorder traversal: 1 5 7 10 40 50