数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究从给定的先序遍历中构造二叉搜索树-第 2 部分 in C++
假设我们有先序遍历。我们基于此遍历生成树。如果遍历类似于 [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 << "Inorder traversal: ";
inord(root);
}输出
Inorder traversal: 1 5 7 10 40 50
更新于： 2020 年 1 月 3 日
158 次浏览
广告