bintree.c

自己做的常用库和实现的数据结构。public domain.

/* Demo of simple binary tree operations.
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */
#include<my.h> 
typedef struct bitree {
	char data;
	struct bitree *lchild, *rchild;
} BT;
void preordercreatBT(BT **p)
{
	int c;
	if( (c=getchar()) == '#')
		*p = NULL;
	else {
		*p = mem('m', sizeof(BT));
		(*p)->data = (char)c;
		preordercreatBT( &((*p)->lchild));
		preordercreatBT( &((*p)->rchild));
	}
}
void inordertraverseBT(BT *p)
{
	if(p) {
		inordertraverseBT(p->lchild);
		putchar(p->data);
		inordertraverseBT(p->rchild);
	}
}
void freeBT(BT *p)
{
	if(p) {
		freeBT(p->lchild);
		freeBT(p->rchild);
		free(p);
	}
}


typedef struct q {
	struct bitree bt;
	struct q *next;
}q, *qq;
typedef struct {
	qq front;
	qq rear;
} Q;

void init_queue(Q *qu)
{
	qu->front = qu->rear = (qq)mem('m', sizeof(q));
	qu->front->next = NULL;
}
void levelordervisit(BT *p)
{
	putchar(p->data);
}
void en_queue(Q *qu, BT *p)
{
	qq t = (qq)mem('m', sizeof(q));
	t->bt = *p;
	t->next = NULL;
	qu->rear->next = t;
	qu->rear = t;
}
bool queue_empty(Q *qu)
{
	return (qu->front == qu->rear) ? true : false;
}
void de_queue(Q *qu, BT *t)
{
	qq t2;
	if(queue_empty(qu))
		return;
	t2 = qu->front->next;
	qu->front->next = t2->next;
	if(t2 == qu->rear)
		qu->rear = qu->front;
	*t = t2->bt;
	free(t2);
}
void destroy_queue(Q *qu)
{
	while(qu->front != NULL) {
		qu->rear = qu->front->next;
	        free(qu->front);
		qu->front = qu->rear;	
	}
}
void levelordertraverseBT(BT *p)
{
	Q queue;
	BT a;
	if(p) {
		init_queue(&queue);
		levelordervisit(p);
		if(p->lchild) en_queue(&queue, p->lchild);
		if(p->rchild) en_queue(&queue, p->rchild);
		while(! queue_empty(&queue)) {
			de_queue(&queue, &a);			
			levelordervisit(&a);
			p = &a;
			if(p->lchild) en_queue(&queue, p->lchild);
			if(p->rchild) en_queue(&queue, p->rchild);
		}
		destroy_queue(&queue);
	}
}

typedef struct s {
	BT *root;
	struct s *next;
} S;
void push(S **sp, BT *bp)
{
	static size_t cnt = 0;
	S *t = (S *)mem('m', sizeof(S));
	t->root = bp;
	t->next = cnt++ ? *sp : NULL;
	*sp = t;
}
bool stack_empty(S *sp)
{
	return sp != NULL ? false : true;
}
void pop(S **sp)
{
	S *t = *sp;
	if(! stack_empty(*sp)) {
		*sp = (*sp)->next;
		free(t);
	}
}
void gettop(S *sp)
{
	putchar(sp->root->data);
}
void preordertraverse_stack(BT *p)
{
	S *sp;
	if(p == NULL) 
		return;
	do {
		if(p) {
			push(&sp, p); gettop(sp); p = sp->root->lchild;
		} else {
			pop(&sp); p = sp->root->rchild;
		}
		/*
		if(p) {
			push(&sp, p); p = sp->root->lchild;
		} else {
			pop(&sp); gettop(sp); p = sp->root->rchild;
		}
		*/
	} while(p==NULL && stack_empty(sp));
}
int main()
{
	BT *p;
	puts("\npreordercreatBT, using '#' as NULL, like abd##e##cf##g##");
	preordercreatBT(&p);
	puts("\ninordertraverse");
	inordertraverseBT(p);
	puts("\nlevelordertraverse");
	levelordertraverseBT(p);
	puts("\npreordertraverse, using stack");
	preordertraverse_stack(p);
	freeBT(p);
	return 0;
}