두 갈래 트리 코드 연습

3571 단어
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define STACK_SIZE 100

typedef struct TREE
{
	char data;
	struct TREE *left;
	struct TREE *right;
}*Tree,Node;

typedef struct STACK
{
	Node node[STACK_SIZE];
	int top;
}Stack;

void init_stack(Stack * stack)
{
	stack->top = 0;
}

int is_empty(Stack *stack)
{
	return stack->top == 0;
}

int push(Stack *stack,Node * node)
{
	if(stack->top == STACK_SIZE)
		return 0;

	stack->node[stack->top++] = *node;
	return 1;
}

int top(Stack *stack,Node *node)
{
	if(stack->top == 0)
		return 0;

	*node = stack->node[stack->top-1];
	return 1;
}

int pop(Stack *stack,Node *node)
{
	if(stack->top == 0)
		return 0;

	*node = stack->node[--stack->top];
	return 1;
}

void creat_tree(Tree * tree)
{
	char data[1];
	scanf("%s",data);

//	char data;
//	scanf("%c",data); // !why?

	if(data[0] == 'a')
	{
		*tree = NULL;
	}
	else
	{
		*tree = malloc(sizeof(Node));
		if(*tree == NULL)
		{
			exit(0);
		}
			
		(*tree)->data = data[0];
		creat_tree(&((*tree)->left));
		creat_tree(&((*tree)->right));
	}
	return ;
}

void pre_order(Tree tree)
{
	if(tree == NULL)
		return ;
	
	printf("%c",tree->data);
	pre_order(tree->left);
	pre_order(tree->right);
}

void in_order(Tree tree)
{
	if(tree == NULL)
		return ;
	
	in_order(tree->left);
	printf("%c",tree->data);
	in_order(tree->right);
}

void post_order(Tree tree)
{
	if(tree == NULL)
		return ;
	
	post_order(tree->left);
	post_order(tree->right);
	printf("%c",tree->data);
}

void in_order_stack(Tree tree)
{
	if(tree == NULL)
		return ;

	Stack stack;
	init_stack(&stack);

	Node * node = malloc(sizeof(Node));

	while(!is_empty(&stack) || tree)
	{
		if(tree != NULL)
		{
			push(&stack,tree);
			tree = tree->left;
		}
		else
		{
			pop(&stack,node);
			printf("%c ",node->data);
			if(node->right != NULL)
				tree = node->right;
		}
	}
	printf("
"); } int tree_heigh(Tree tree) { if(tree == NULL) return 0; else { int left = tree_heigh(tree->left); int right = tree_heigh(tree->right); return left > right ? left+1 : right+1; } } // 1 2 3 a 4 a a a a // 1 // 2 3 // a 4 a a // a a int main() { Tree tree = NULL; creat_tree(&tree); printf("pre:
"); pre_order(tree); printf("
in:
"); in_order(tree); printf("
post:
"); post_order(tree); printf("
"); printf("Tree heigh is %d
",tree_heigh(tree)); in_order_stack(tree); return 0; }

좋은 웹페이지 즐겨찾기