資料結構
網路
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 檢視
廣告