bitree.txt

二叉排序树的中序遍历

/*   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");
}