リニア二叉ツリーを作成


/*
	                ,         
	     ,               ,                    
	             ,       
*/ 
/* 
#include   
  //       
  int flag = 1;
void binary_tree(int *btree, int *list, int len)  
{  
    int i;  
    int level;  
    btree[1] = list[1];  //                
  	 
    for (i = 2; i <= len; i++)  
    {
    	if(1 == flag){
    		btree[0] = list[0];
		}
        level = 1;
        while (btree[level] != 0)
        {
            if (list[i] > btree[level])
                level = 2 * level + 1; //1->3  0->1 
            else
                level = 2 * level;  //->2     0->0     0             
        }  
        btree[level] = list[i];  
    }  
}  
  
void mid_travel(int *btree, int pos)  
{  
	if(1 == flag){
		flag = 0;
		printf("%d ",btree[0]);
	}
		
    if (btree[pos] != 0)  
    {  
        mid_travel(btree, 2 * pos);  //1->2 0->0
        if (btree[pos] != 0)  
            printf("%d ", btree[pos]);  
        mid_travel(btree, 2 * pos + 1);  //1->3 0->1       pos 0              
    }  
}
int main(int argc, char* argv[])
{
    int btree[2048] = {0};
    int list[] = {-1,1,3,89,3,5,67,25,88,55,43,7,9,10};  //-1     
    int len = sizeof(list)/sizeof(list[0]);
    len -= 1;
    binary_tree(btree, list, len);
    mid_travel(btree, 1);
    return 0;
}  
 */ /*             */ 
#include
#include

 
typedef struct BiTree {
    int data;
    BiTree *lchild;
    BiTree *rchild;
}BTree;
 
//              key
BiTree* InsertBST(BiTree *t,int key)
{
    if (t == NULL)
    {
        t = new BiTree();
        t->lchild = t->rchild = NULL;
        t->data = key;
        return t;
    }
 
    if (key < t->data) 
        t->lchild = InsertBST(t->lchild, key);
    else
        t->rchild = InsertBST(t->rchild, key);
 
    return t;
}
 
//n      d ,tree       
BiTree* CreateBiTree(BiTree *tree, int d[], int n)
{
    for (int i = 0; i < n; i++)
        tree = InsertBST(tree, d[i]);
}
void midTravel(BiTree *tree){
	if(NULL != tree){
		midTravel(tree->lchild);
		printf("%d ",tree->data);
		midTravel(tree->rchild);
	} 
}
int main(){
	int data[8] = {95, 45, 15, 78, 84, 51, 24, 12};
	BTree root;
	CreateBiTree(&root,data,8);
	midTravel(&root);
	
	return 0;
}