按照数组顺序插入到二叉树中

参考文章

数组与二叉树的对应关系：一个结点在数组中的序号为 i，则其左孩子结点序号为 2 * i，右孩子结点序号为 2 * i + 1；

根据这条关系，我们可以建立个按照数组顺序的二叉树；

代码说明： 按数组 arr 顺序建立二叉树，i 为当前插入元素在数组中的位置，n 为数组元素个数，root 为本次插入的结点地址；这个函数的作用是将数组中 arr[i] 元素插入到地址为 root 的位置上，那么结点 root 的左孩子结点插入元素为 arr[2 * i]，右孩子结点插入元素为 arr[2 * i + 1]；每次创建一个结点，创建的结点就是上一个结点对应的左右结点；

node* insertLeverOrder(Type arr[], node* &root, int i, int n) {	 
	 if(i < n) {
	 	node* temp = create(arr[i]);	//创建一个新的结点
	 	root = temp;
	 	root->lchild = insertLeverOrder(arr, root->lchild, 2 * i, n);
	 	root->rchild = insertLeverOrder(arr, root->rchild, 2 * i + 1, n);
	 }
	 return root;
}

现在插入顺序为 'A', 'B', 'C', 'D', 'E', 'F', ‘G’ 插入后的二叉树如下：

完整代码如下：

#include<iostream>
using namespace std;
typedef char Type;
struct node {
	Type data;
	node* lchild;
	node* rchild;
}; 

node* create(Type x) {	//创建一个结点
	node* n = new node;
	n->data = x;
	n->lchild = n->rchild = NULL;
	return n;
}


//通过 arr[i] 元素创建 root 结点，注意是 root 地址的引用
node* insertLeverOrder(Type arr[], node* &root, int i, int n) {	 
	 if(i < n) {
	 	node* temp = create(arr[i]);
	 	root = temp;
	 	root->lchild = insertLeverOrder(arr, root->lchild, 2 * i, n);
	 	root->rchild = insertLeverOrder(arr, root->rchild, 2 * i + 1, n);
	 }
	 return root;
}
//中序遍历 
void inorder(node* root) {
	if(root == NULL) {
		return;
	}
	
	inorder(root->lchild);
	printf("%c\n", root->data);
	inorder(root->rchild); 
}

int main() {
    //第一个位置不放元素，因为下标为 0 则不能访问其左孩子结点(2 * i = 0)
	Type data[8] = {'0', 'A', 'B', 'C', 'D', 'E', 'F', 'G'};
	node* root = insertLeverOrder(data, root, 1, 8);
	inorder(root);
	return 0;
}

当然使用静态存储方式实现更加简单，即使用数组存储二叉树，若某结点在数组中位置为 i，其左孩子结点和右孩子结点分别为 2 * i 和 2 * i + 1；就不需要使用指针了；