wo.c

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

#include<stdio.h>
#include<stdlib.h>
typedef struct bitree {
	char data;
	struct bitree *lchild, *rchild;
} BT;
void preordercreatBT(BT **p)
{
	int c;
	if( (c=getchar()) == '#')
		*p = NULL;
	else {
		*p = malloc(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 s {
	BT *root;
	struct s *next;
} S;
void push(S **sp, BT *bp)
{
	static size_t cnt = 0;
	S *t = (S *)malloc(sizeof(S));
	if(t == NULL) {
		fprintf(stderr, "Fatal: mem alloc failed !");
		exit(1);
	}
	t->root = bp;
	t->next = cnt++ ? *sp : NULL;
	*sp = t;
}
int stack_empty(S *sp)
{
	return sp != NULL ? 0 : 1;
}
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;
		}
	} 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("\npreordertraverse, using stack");
	preordertraverse_stack(p);
	freeBT(p);
	return 0;
}