在 C++ 中根据给定的层序遍历构造 BST
c++server side programmingprogramming
假设我们有一个层序遍历。从这个遍历中，我们必须生成树，因此，如果遍历类似于 [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 << "中序遍历:";
inord(root);
}
输出
中序遍历:1 3 4 5 6 7 8 10 12
