数据结构
网络
关系数据库管理系统
操作系统
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+ 查看
广告