根据给定的先序遍历构造 BST - C++ 中的集合 2
c++server side programmingprogramming
假设我们有一个先序遍历。从这个遍历开始。我们必须生成树，因此，如果遍历类似于 [10, 5, 1, 7, 40, 50]，则树将类似于 −
为了解决这个问题，我们将遵循以下步骤 −
创建空堆栈
将第一个值作为根，并将其推入堆栈。
现在，在堆栈不为空且下一个值大于堆栈顶部元素时继续大便，将其作为最后弹出节点的右子节点。现在将新节点推送到堆栈。
当下一个值小于顶部元素时，将其作为堆栈顶部元素的左子元素。现在将新节点推送到堆栈。
重复步骤 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 << "中序遍历: ";
inord(root);
}
输出
中序遍历: 1 5 7 10 40 50
