建立一颗完全二叉树
作者:
林夕丶
,
2022-03-28 22:40:23
,
所有人可见
,
阅读 243
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Node{
Node(int v) : val(v), left(nullptr), right(nullptr){}
int val;
Node *left;
Node *right;
};
Node* input() {
int pos = 0;
vector<int> data{1,2,3,4,5,6,7,8,9};
auto root = new Node{data[pos++]};
vector<Node*> q{root};
while(1) {
vector<Node*> next;
for(const auto qi : q) {
qi->left = new Node(data[pos++]);
if(pos >= data.size()) return root;
qi->right = new Node(data[pos++]);
if(pos >= data.size()) return root;
next.push_back(qi->left);
next.push_back(qi->right);
}
q = move(next);
}
return root;
}
int main()
{
auto root = input();
if(root == nullptr) {return 0;}
vector<Node*> q{root};
while(!q.empty()) {
vector<Node*> next;
for(const auto qi : q) {
cout << qi->val << ' ';
if(qi->left != nullptr) next.push_back(qi->left);
if(qi->right != nullptr) next.push_back(qi->right);
}
cout << '\n';
q = move(next);
}
cout << '\n';
}
// ---------------- 结果 -------------------------
// 1
// 2 3
// 4 5 6 7
// 8 9