bitree.cpp

二叉树的先序

# include<stdio.h>
# include<malloc.h>
typedef struct bitree {
	char data;
	struct bitree *lchild, *rchild;
}* bitnode;

void pre(struct bitree  *T) 
{
	printf("%c", T->data);
	if(T->lchild){
		pre(T->lchild);
		if(T->rchild) {
			pre(T->rchild);
		}
	}
	else if(T->rchild) {
		pre(T->rchild);
	}
}

void in(struct bitree *T)
{
	struct bitree *s[100], *p;
	int top = 0;
	s[top] = T;
	top ++;
	while( top != 0 && !(top == 1 && s[0] == NULL )) {
		p = s[top - 1];
		while( p) {
			s[top] = p->lchild;
			top ++;
			p = s[top - 1];
		}

		top = top - 2;
		p = s[top];
		if(p){
			printf("%c", p->data);
		}
		s[top] = p -> rchild;
		top ++;
	}//while;
}

void post(struct bitree *T)
{
    if(T->lchild) {
		post(T->lchild);
		if(T->rchild) {
			post(T->rchild);
		}
	}
	else if(T->rchild) {
		post(T->rchild);
	}
	printf("%c", T->data);
	
}

void ceng(struct bitree *T)
{
	struct bitree *Q[100], *p;
	int h = 0, t = 1;
	Q[h] = T;

	for(; ; ){
		if(h != t) {
			p = Q[h];
			printf("%c", p->data);
		    h = (h + 1) % 100;
			if(p->lchild) {
				Q[t] = p -> lchild;
				t = (t + 1 ) % 100;
			}
			if(p->rchild) {
				Q[t] = p -> rchild;
				t = (t + 1 ) % 100;
			}
		}
		else break;
	}
}

void creat(bitnode &T) 
{
	char ch;
	scanf("%c", &ch);
	if(ch == '#') {
		T = NULL;
	}
	else{
		T = (struct bitree *) malloc(sizeof(struct bitree));
		T -> data = ch;
		creat(T->lchild);
		creat(T->rchild);
	}
} 

int main()
{
	bitnode T;
	creat(T);
	printf("先序遍历：");
	pre(T);
	printf("\n中序遍历：");
	in(T);
	printf("\n后序遍历：");
	post(T);
	printf("\n按层遍历：");
	ceng(T);
	printf("\n");
	return 0;
}