Detailed introduction to the hierarchical method of binary tree creation

一、引言
Two methods of creating a binary tree by the preorder method have been given above,Non-recursive and recursive methods, respectively,This article will giveCThe language version of the Hierarchical Method algorithm for creating binary trees.The so-called hierarchical method is actually based on where the nodes in the binary tree are“层”进行遍历,The rule for traversing each layer is from left to right.Therefore, the hierarchical traversal is actually traversed according to the numbering order of the nodes in the complete binary tree,But binary trees are not necessarily complete binary trees,Hence it involves the addition of virtual into a complete binary tree,Then do the hierarchy traversal.
The example binary tree used is shown in the figure below.

二、二叉树的创建-层次法
1、结点编号规则
Hierarchical method to create binary tree,It is still necessary to extend the binary tree.But here is different from the extension of the preorder method,The nodes need to be expanded according to the pattern of a complete binary tree.The purpose of filling these nodes is to record the node number of the complete binary tree,So in fact there is no need to actually fill in the missing nodes,Just remember the number of all nodes on the binary tree on the complete binary tree.
此时,图（1）The numbering of the mid-nodes is as follows（从1开始）：

2、算法的基本思路：
首先创建一个数组S,Used to store all the nodes on the binary tree.
After that, start to read the node data in sequence,The specific method is to read the number of a node at the same timei和数据data,Create a node with this,and put the node into the arrayS的下标为i的位置.接着根据i/2to confirm the presence of his parentsS中的下标,且根据i是否被2Divide to determine the nodei是j的左子树还是右子树.

3、算法的具体实现：

#include"stdio.h"
#include"malloc.h"

#define CHAR 
#define MAX_NODE 100

#ifdef CHAR
typedef char datatype;
#else
typedef int datatype;
#endif

typedef struct node
{
    
	datatype data;
	struct node *Lchild;
	struct node *Rchild;
}BiTree;

BiTree *CreateBiTreeLevel( void )  
{
    
	BiTree *T,  *p, *s[MAX_NODE];
	datatype data;       
	int i,  j;
	T = NULL; 
	while ( 1 )
	{
    
		printf( " Enter the node number( 0 则终止输入 ): " );
		scanf( "%d", &i ); 
		if( i == 0 )
			break;
		else
		{
    
#ifdef CHAR
			getchar();//Filter newlines after the input node number
			printf( " 请输入结点数据(字符):" );
			scanf( "%c",&data );
			getchar();//Newline character after filtering node data 
#else
			printf( " 请输入结点数据(整数):" );
			scanf( "%d",&data );
#endif
			//创建结点,并把data存入该结点,At the same time, the left and right subtrees of the node are empty
			p = ( BiTree * )malloc( sizeof(BiTree) ) ;
			p->data = data ;        
			p->Lchild = NULL;
			p->Rchild = NULL;                        
			s[i] = p ;
			if( i == 1 ) //编号为1The node is the root of the tree 
				T = p ; 
			else//Find the parents of the newly added node
			{
    
				j = i / 2;    // j是iThe parent node number of 
				if( i % 2 == 0 ) 
				{
    
					s[j]->Lchild = p;//左子树
					//The output below is to verify that the position of the node is as expected. 
#ifdef CHAR 
					printf( " %c 是 %c 的左子树\n", p->data, s[j]->data );
#else
					printf( " %d 是 %d 的左子树\n", p->data, s[j]->data );
#endif
				}    
				else 
				{
    
					s[j]->Rchild = p;//右子树
#ifdef CHAR 
					printf( " %c 是 %c 的右子树\n", p->data, s[j]->data );
#else
					printf( " %d 是 %d 的右子树\n", p->data, s[j]->data );
#endif
				} 
					
			} 		 
		}
	}
	return( T ); 
}

int main()
{
    
	BiTree *T = CreateBiTreeLevel( );
	return 0;
}

4、运行结果