資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律用 C++ 以分層遍歷順序從給出陣列中構建一棵完全二叉樹
假設我們有一個數組 A[]，包含 n 個元素。我們必須以分層遍歷順序從陣列中構建二叉樹。因此陣列中的元素從左到右將按層填充到從 0 級開始的樹中。因此，如果陣列為 A = [1, 2, 3, 4, 5, 6]，則樹為如下所示
如果我們進一步觀察，我們可以發現當父元素位於索引 i 時，它的兩個子元素將位於索引 (2i + 1) 和 (2i + 2) 上。因此我們可以使用其父元素插入左和右元素。陣列的第一個元素將是樹的根元素。
示例
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left, * right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
Node* insertLevelWise(int arr[], Node* root, int i, int n) {
if (i < n) {
Node* temp = getNode(arr[i]);
root = temp;
root->left = insertLevelWise(arr, root->left, 2 * i + 1, n);
root->right = insertLevelWise(arr, root->right, 2 * i + 2, n);
}
return root;
}
void inorderTrav(Node* root) {
if (root != NULL){
inorderTrav(root->left);
cout << root->data <<" ";
inorderTrav(root->right);
}
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
Node* root = insertLevelWise(arr, root, 0, n);
cout << "Inorder traversal of created tree: ";
inorderTrav(root);
}輸出
Inorder traversal of created tree: 4 2 5 1 6 3
更新於：2019 年 12 月 30 日
1000+ 檢視
廣告