/*=========================Programme Description==========================*/
/*程序名稱:Tree_Arrey.c                                                   */
/*程序目的:以數組的方式建立二叉樹                                         */
/*Written By:Wang Qiang.                                                  */
/*========================================================================*/

#include<stdio.h>
/*------------------------------------------------------*/
/*建立二叉樹                                            */
/*------------------------------------------------------*/
void create_btree(int *b_tree, int *nodelist, int len)
{
	int i;
	int level;    /*樹的階層數*/

	b_tree[1]=nodelist[1]; //以第一個元素為根節點
	
	for (i=2;i<len;i++) //依序建立其他節點
	{
		level=1;  //從階層一開始建立
		while( b_tree[level] !=0) //判斷是否有子樹存在
		{
			if(nodelist[i]<b_tree[level]) //判斷是左子樹還是右子樹
				level=level*2; //左子樹
		    else
				level=level*2+1;//右子樹
		}//while
		b_tree[level]=nodelist[i];
	}//for
}//create_btree

/*-------------------------------------------------------*/
/*主函數:輸入元素、建立二叉樹并輸出二叉樹的內容          */
/*-------------------------------------------------------*/

void main()
{
	int i,index;
	int data;  //讀入輸入值所使用的暫存變量
	int b_tree[100]; //二叉樹數組
	int nodelist[100];//存儲輸入數據的數組

	printf("Please input the elements of the binary tree(Exit for 0):\n");

	index=1;

    /*--------------------讀取數值到數組中------------------*/
    scanf("%d",&data);

    while(data !=0)
	{
		nodelist[index]=data;
	    index=index+1;
	    scanf("%d",&data);
	}


    /*-------------------清除二叉樹數組的內容---------------*/
    for(i=0;i<100;i++)
       b_tree[i]=0;

    /*-------------------建立二叉樹--------------------------*/
    create_btree(b_tree,nodelist,index);

    /*-------------------輸出二叉樹的內容---------------------*/
    printf("\nThe binary tree is:\n");
    for(i=1;i<100;i++)
       printf("%2d:[%d]    \n",i,b_tree[i]);
}

//二叉樹組的優點是:對于任一個結點都能容易地找到其父節點,子節點,及兄弟,而且每個節點地存儲空間不大
//只占用數組的一個內存空間,但當二叉樹的深度和節點數的比例偏高時(二叉樹分布不均勻,如歪斜樹),內存
//的利用率偏低,容易造成空間的浪費.