苗火 Nicholas

[Data structures]Traversing binary tree

2019-7-31 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

typedef struct _BiTree{
	char data;
	struct _BiTree *left;
	struct _BiTree *right;
}BiTree;

int PreOrderTraverseCreate(BiTree **T)
{
	char c;
	scanf(" %c",&c); 
	printf(" %c", c);
	if(c == '$'){
		*T = NULL;
	}else{
		*T = (BiTree *)malloc(sizeof(BiTree));
		(*T)->data = c;
		(*T)->left = (*T)->right = NULL;

		PreOrderTraverseCreate(&(*T)->left);
		PreOrderTraverseCreate(&(*T)->right);
	}
}

int PreOrderTraverse(BiTree *T)
{
	if(T != NULL){
		printf(" %c", T->data);
		PreOrderTraverse(T->left);
		PreOrderTraverse(T->right);
	}
}

void InOrderTraverse(BiTree *T)
{
	BiTree *stack[MAX];
	int top = -1;

	BiTree *p;

	stack[++top] = T;
	while(top>=0){
		while(p = stack[top]){
			stack[++top] = p->left;	
		};
		top--;

		if(top>=0){
			p = stack[top--];
			printf(" %c", p->data); 
			stack[++top] = p->right;
		}
	}
}

void InOrderTraverse2(BiTree *T)
{
	BiTree *stack[MAX];
	int top = -1;

	BiTree *p;	
	p = T;
	while(p || top>=0){
		if(p){
			stack[++top] = p;
			p = p->left;
		}else{
			p = stack[top--];
			printf(" %c", p->data);
			p = p->right;
		}
	}
}

void main()
{
	BiTree *T;	

	printf("log.anycle.com\n\n");
	printf("Pre order traverse create binary tree:\n");
	PreOrderTraverseCreate(&T);
	printf("\n");

	printf("Pre order traverse:\n");
	PreOrderTraverse(T);
	printf("\n");

	printf("In order traverse:\n");
	InOrderTraverse(T);
	printf("\n");

	printf("In order traverse:\n");
	InOrderTraverse2(T);
	printf("\n");

}

标签: Data Structures data_structures