数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 C++ 中根据给定的层序遍历构造 BST
假设我们有一个层序遍历。从这个遍历中，我们必须生成这棵树。因此，如果遍历类似于 [7, 4, 12, 3, 6, 8, 1, 5, 10]，那么这棵树将如下: -
为了解决这个问题，我们将使用递归方法。第一个元素将是根。第二个元素将是左子节点，第三个元素将是右子节点（如果 BST 的条件得到满足），此属性将满足于所有元素。因此，我们将遵循以下步骤
首先，我们必须获取数组的第一个元素，并将其作为根。
然后获取第二个元素。如果它小于根，则将其作为左子节点，否则作为右子节点。
然后递归调用步骤 2 以生成 BST。
示例
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node *lvlOrd(Node *root , int data) {
if(root==NULL){
root = getNode(data);
return root;
}
if(data <= root->data)
root->left = lvlOrd(root->left, data);
else
root->right = lvlOrd(root->right, data);
return root;
}
Node* makeTree(int arr[], int n) {
if(n==0)
return NULL;
Node *root= NULL;
for(int i=0;i<n;i++)
root = lvlOrd(root , arr[i]);
return root;
}
void inord(Node* root) {
if (!root)
return;
inord(root->left);
cout << root->data << " ";
inord(root->right);
}
int main() {
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = sizeof(arr) / sizeof(arr[0]);
Node *root = makeTree(arr, n);
cout << "Inorder Traversal: ";
inord(root);
}输出
Inorder Traversal: 1 3 4 5 6 7 8 10 12
更新于: 03-Jan-2020
300 查看
广告