Create a complete binary tree in array order

Insert into the binary tree in array order

Reference article

The correspondence between array and binary tree ： The sequence number of a node in the array i, Then the left child node serial number is 2 * i, The serial number of the right child node is 2 * i + 1;

According to this relationship , We can build a binary tree in array order ;

Code instructions ： By array arr Establish a binary tree in sequence ,i The position of the currently inserted element in the array ,n Is the number of array elements ,root Is the node address of this insertion ; This function is used to put arr[i] The element is inserted into the address root Location , So node root The inserted element of the left child node is arr[2 * i], The inserted element of the right child node is arr[2 * i + 1]; Create one node at a time , The created node is the left and right nodes corresponding to the previous node ;

node* insertLeverOrder(Type arr[], node* &root, int i, int n) {
    	 
	 if(i < n) {
    
	 	node* temp = create(arr[i]);	// Create a new node 
	 	root = temp;
	 	root->lchild = insertLeverOrder(arr, root->lchild, 2 * i, n);
	 	root->rchild = insertLeverOrder(arr, root->rchild, 2 * i + 1, n);
	 }
	 return root;
}

Now the insertion order is ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’ The inserted binary tree is as follows ：

The complete code is as follows ：

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

node* create(Type x) {
    	// Create a node 
	node* n = new node;
	n->data = x;
	n->lchild = n->rchild = NULL;
	return n;
}


// adopt  arr[i]  Element creation  root  node , Note that  root  Reference to address 
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;
}
// In the sequence traversal  
void inorder(node* root) {
    
	if(root == NULL) {
    
		return;
	}
	
	inorder(root->lchild);
	printf("%c\n", root->data);
	inorder(root->rchild); 
}

int main() {
    
    // Don't put the element in the first position , Because the index is zero  0  You cannot access its left child node (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;
}

Of course, using static storage is simpler , That is, use an array to store a binary tree , If the position of a node in the array is i, Its left child node and right child node are 2 * i and 2 * i + 1; You don't need to use a pointer ;