/*   BITREE.C   二叉排序樹的中序遍歷   */
/*  將該程序中的學號、姓名以及????(10處)補充完整  */
/*  20031500林定移  將前面的學號和姓名更改為你的學號和姓名!!!  */

#include "stdio.h"

struct TreeNode {
	struct TreeNode *lchild;
	int data;
	struct TreeNode *rchild;
};  /*以上語句定義樹結點的數據結構*/
typedef struct TreeNode NODE;

NODE *T;  /*T為二叉樹根結點的存儲地址*/
int n=30;
int k[30]={15,9,27,20,7,11,19,29,30,1,8,3,16,21,22,
	14,12,5,2,25,6,18,23,28,10,4,13,17,24,26};

void InsertTree(int item) {  /*將一個數據插入到二叉排序樹中*/
	NODE *p,*q;
	p=(NODE *)malloc(sizeof(NODE));  /*申請一個新結點p*/
	p->data=item;  /*以下三個語句給p賦初值*/
	p->lchild=NULL;
	p->rchild=NULL;
	if (T==NULL)  ???? ;  /*如果為空樹*/
	else {  /*如果不是空樹*/
		q=T;
		do {
			if (item < q->data) {  /*插入到左子樹中*/
				if (q->lchild!=NULL)  ???? ;
				else { ???? ; break;}
			}
			else {  /*插入到右子樹中*/
				if (q->rchild!=NULL)  ???? ;
				else { ???? ; break;}
			}
		} while (1);
	}
}

void SortTree() {  /*調用插入數據函數，將所有數據插入到二叉樹中，形成二叉排序樹*/
	int i;
	T=NULL;
	for (i=0;i<n;i++)  ???? ;
}

void InOrder() {  /*二叉排序樹的中序遍歷*/
	int top=0;
	NODE *p;
	NODE *stack[100];
	p=T;
	do {
		while (p!=NULL) {
			top++;  /*進棧*/
			stack[top]=p;
			???? ;
		}
		p=stack[top];
		???? ;  /*出棧*/
		printf("%d ",p->data);  /*輸出一個結點的數據域*/
		???? ;  /*指向右子樹*/
	} while ( ???? ) ;  /*條件式*/
}

main() {
	SortTree();
	InOrder();
	printf("\n");
}