二叉树的建立(非递归)

1. 问题描述:

先序非递归建立一颗以二叉链表为存储结构的二叉树。例如建立如下所示的一颗二叉树

A

/ \

B E

/ \ /

C D F

则输入应为: ABC_ _D_ _EF_ _ _ (其中_代表空格).

代码如下:

/*
 *  名 称: 建立二叉树(非递归)
 *  作 者: Brooke gao
 *  时 间: 2013/8/21
 *  
*/
	
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define STACKSIZE 50
#define bitree_size(tree)  ((tree)->size)   
#define bitree_root(tree)  ((tree)->root)
#define bitree_left(node)  ((node)->left)
#define bitree_right(node) ((node)->right)

/*
 *  定义二叉树结点以及二叉树的结构
 *
*/
typedef struct BiTreeNode_
{
	char data;
	struct BiTreeNode_ *left;
	struct BiTreeNode_ *right;
}BiTreeNode;

typedef struct BiTree_
{
	int size;
	BiTreeNode *root;
}BiTree;

/*
 *  定义栈的结构
 *
*/
typedef struct Stack_
{
	BiTreeNode * base[STACKSIZE];
	int top;
	int stacksize;
}Stack;

void stack_init(Stack *stack)
{
	stack->top = -1;
	stack->stacksize = 0;
}

void push(Stack *stack, BiTreeNode *node)
{
	if(stack->stacksize == STACKSIZE)
		exit(-1);

	stack->base[++stack->top] = node;
	stack->stacksize++;
}

int stack_empty(Stack *stack)
{
	if((-1 == stack->top) && (0 == stack->stacksize))
		return 1;
	else
		return 0;
}

BiTreeNode* pop(Stack *stack)
{
	if(stack->top < 0)
		exit(-1);
	else
	{
		stack->stacksize--;
		return stack->base[stack->top--];
	}
}

BiTreeNode* get_stack_top(Stack *stack)
{
	if(stack->top < 0)
		exit(-1);
	return stack->base[stack->top];
}

void bitree_init(BiTree *tree)
{
	tree->size = 0;
	tree->root = NULL;
}

//给树tree的某个结点node插入数据域为data的左子树
int bitree_ins_left(BiTree *tree, BiTreeNode *node, const char data)
{
	BiTreeNode *new_node, **position;

	if(NULL == node)
	{
		if(bitree_size(tree) > 0)
			return -1;
		position = &tree->root;
	}
	else
	{
		if(bitree_left(node) != NULL)
			return -1;
		position = &node->left;
	}

	if( NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) )
		return -1;
	new_node->data = data;
	new_node->left = NULL;
	new_node->right = NULL;
	*position = new_node;
	tree->size++;
		
	return 0;
}

//给树tree的某个结点node插入数据域为data的右子树
int bitree_ins_right(BiTree *tree, BiTreeNode *node, const char data)
{
	BiTreeNode *new_node, **position;

	if(NULL == node)
	{
		if(bitree_size(tree) > 0)
			return -1;

		position = &tree->root;
	}
	else
	{
		if(bitree_right(node) != NULL)
			return -1;

		position = &node->right;
	}

	if( NULL == (new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) )
		return -1;

	new_node->data = data;
	new_node->left = NULL;
	new_node->right = NULL;

	*position = new_node;

	tree->size++;
	return 0;
}

// 先序遍历函数
void pre_order(const BiTreeNode *node)
{
	if(node)
	{
		printf("%c",node->data);
		pre_order(node->left);
		pre_order(node->right);
	}
}

// 中序遍历函数
void in_order(const BiTreeNode *node)
{
	if(node)
	{
		in_order(node->left);
		printf("%c",node->data);
		in_order(node->right);
	}
}

// 后序遍历函数
void end_order(const BiTreeNode *node)
{
	if(node)
	{
		end_order(node->left);
		end_order(node->right);
		printf("%c",node->data);
	}
}

int main()
{
	char data;
	Stack stack;
	BiTree tree;
	BiTreeNode *node;
	
	stack_init(&stack);
	bitree_init(&tree);

	printf("请以先序顺序输入结点值: \n");

	data = getchar();
	
	if( 0 == bitree_size(&tree) )
	{
		if( ' ' == data )
			return -1;
		bitree_ins_left(&tree,NULL,data);
		push(&stack,tree.root);
	}
	while(!stack_empty(&stack))
	{
		data = getchar();

		if( ' ' == data )
		{
			node = pop(&stack);
			
			if(NULL == node->left)
			{
				data = getchar();
				if( ' ' != data )
				{
					bitree_ins_right(&tree,node,data);
					push(&stack,node->right);
				}
			}
		}
		else
		{
			node = get_stack_top(&stack);
			if( NULL == node->left )
			{
				bitree_ins_left(&tree,node,data);
				push(&stack,node->left);
			}
			else
			{
				node = pop(&stack);
				bitree_ins_right(&tree,node,data);
				push(&stack,node->right);
			}
		}
	}
	printf("-----先序遍历二叉树-----\n");
	pre_order(tree.root);
	putchar('\n');
	
	printf("-----中序遍历二叉树-----\n");
	in_order(tree.root);
	putchar('\n');

	printf("-----后序遍历二叉树-----\n");
	end_order(tree.root);
	putchar('\n');

	return 0;
}

运行结果:

注:

最近复习到树一章，发现严蔚敏的《数据结构》一书关于二叉树的建立只有递归算法，而没有非递归算法。

但想着只要是递归能实现的非递归一定能实现，所以昨天开始试着自己看能不能写出来，但折腾了老半天

还是错误百出，最后干脆没头绪了。后来在网上找了一下，用非递归建立二叉树的很少，仅有的几个思路不

是很清晰且有些运行起来有些问题。今天经@zhao4zhong1老师的推荐，看了《算法精解--C语言描述》一

书有关二叉树的一章，总算是找到了非递归建立的方法，故有如上的实现方法。