[数据结构与算法]如何通过数组创建二叉树ACM模式

我们其实可以想象一下二叉树这种数据结构，然后通过数组下标关系进行访问，可以有两种实现方式递归和非递归方式

首先我们来一下递归方式创建普通二叉树

#include<iostream>
using namespace std;
#include<vector>
struct Node {//我们先自己定义一个数据结构模拟数
	int val;
	Node* left;
	Node* right;
	Node(int val) {
		this->val = val;
		left = nullptr;
		right = nullptr;
	}
};
class Bree {
	Node* root;
	
};
Node* creatBree(vector<int>&nums, int index) {//返回值就是返回根节点，参数就是下标和构建数组
	/*
	* 写递归函数可以三步走
	* 1.明确递归函数返回值以及参数定义
	* 2.明确递归结束条件
	* 3.确定单层操作
	*/
	if (index >= nums.size());//递归结束条件
	{
		return nullptr;
	}
	int left = index * 2 + 1;//左右子树关系可以自己画个数组下标（用下标进行模拟）进行标记
	int right = index * 2 + 2;
	Node* root = new Node(nums[index]);//创建根节点
	root->left = creatBree(nums, left);
	root->right = creatBree(nums, right);
	return root;
}
int main() {
	vector<int>nums{ 1, 7, 5, 4, 9, 8, 10 };
	Node* root = creatBree(nums, 0);
}

这样一课可以操作的二叉树就建造好了

2.我们可以通过迭代方式创建一个普通二叉树，可以在数组中存入数数据结构

Node* constructBree(const vector<int>& vec) {
	vector<Node*>vecBree(vec.size(), NULL);
	Node* root = NULL;
	for (int i = 0; i < vec.size(); i++) {
		Node* node = NULL;
		if (vec[i] != -1) node = new Node(vec[i]);
		vecBree[i] = node;
		if (i == 0) {
			root = node;
		}
	}
	for (int i = 0; i * i + 2 < vec.size(); i++) {
		if (vecBree[i] != NULL) {
			vecBree[i]->left = vecBree[2 * i + 1];
			vecBree[i]->right = vecBree[2 * i + 2];
		}
	}
	return root;
}