/*=========================Programme Description==========================*/
/*程序名稱:Tree_Link.c                                                    */
/*程序目的:以鏈接的方式建立二叉樹                                         */
/*Written By:Wang Qiang.                                                  */
/*========================================================================*/
#include<stdio.h>
#include<stdlib.h>

struct tree //聲明樹的結構
{
	struct tree *left;
	int data;
	struct tree *right;
};

typedef struct tree treenode; //新類型樹結構
typedef treenode * b_tree;
b_tree btree;

/*-------------------------------------------*/
/*插入二叉樹的節點                           */
/*-------------------------------------------*/

b_tree insert_node(b_tree root,int node)
{
	b_tree newnode;
	b_tree currentnode;
	b_tree parentnode;

	/*建立新節點的內存空間*/
	newnode=(b_tree) malloc (sizeof(treenode));

	newnode->data=node;
	newnode->right=NULL;
	newnode->left=NULL;

	if( root == NULL)
		return newnode;
	else
	{
		currentnode=root;
		while(currentnode!=NULL) //直到currentnode=NULL
		{
			parentnode=currentnode; //在currentnode改變之前先將他賦予parentnode
			if ( currentnode->data > node)
				currentnode=currentnode->left; //左子樹
			else
				currentnode=currentnode->right;//右子樹
		}//while

		if (parentnode->data>node)
			parentnode->left=newnode;
		else
		    parentnode->right=newnode;
	}//else
	return root;
}//insert_node

/*---------------------------------------------------*/
/*建立二叉樹                                         */
/*---------------------------------------------------*/

b_tree create_btree(int *data,int len)
{
	b_tree root=NULL;
	int i;

	for ( i=0; i<len; i++)
		root=insert_node(root,data[i]);
	return root;
}


/*---------------------------------------------------*/
/*打印二叉樹                                         */
/*---------------------------------------------------*/
void print_btree(b_tree root)
{
	b_tree pointer;

	pointer=root->left;
	printf(" Print left_subtree node of root:\n");
	while(pointer !=NULL)
	{
		printf("[%2d]\n",pointer->data);
		pointer=pointer->left;
	}

	pointer=root->right;
	printf("Print right_subtree  of root:\n");
	while(pointer!=NULL)
	{
		printf("[%2d]\n",pointer->data);
		pointer=pointer->right;
	}
}

/*---------------------------------------------------*/
/*主程序:輸入元素,建立鏈表二叉樹,并輸出二叉樹的內容  */
/*---------------------------------------------------*/
void main()
{
	b_tree root=NULL;
	int i,index;
	int data;
	int nodelist[20];

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

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

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

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

	/*------------------打印二叉樹的內容-------------------*/
    print_btree(root);
}