LV020-二叉树遍历

一、二叉树结构创建

1. 树的结构体

由前边的分析,存储结点需要两个指针域和一个数据域，如下图：

typedef char bitree_data; /* 定义二叉树中数据元素的数据类型 */

typedef struct bitree_node 
{
	bitree_data data;/* 数据域 */
	struct bitree_node *left; /* 指向左孩 */
	struct bitree_node *right;/* 指向右孩 */
}binarytree;/* binary tree node */

2. 树的创建

2.1 存储结构

要进行树的遍历，首先要有棵树吧，可是怎么去创建树，就直接一个一个结点在程序实现吗？如果结点比较多的话，那样得来的程序有点难以想象，并且也无法修改了。

前边学习树的基本概念的时候，可以知道，树可以理解为是由根结点和若干子树构成的，也就是说，树中还是树，其实这便形成了一种递归的数据结构，于是我们可以考虑使用递归函数来创建树。

递归函数需要有结束的条件，我们可以规定输入#代表空，同时也是递归结束的条件。这个时候我们需要将待输入的二叉树补充成满二叉树，并且若有叶子结点，则也需要为叶子结点补充两个#孩结点以表示结束。如下图所示：

创建的链式存储结构如下图所示：

于是，得到我们在输入的时候需要输入的序列为：

AB#CD###E#FGH##K###<Enter>

【注意】在递归函数的结束条件中尽量不要打印提示信息，不然每一次达到递归结束条件时都会打印相关提示，看起来还是比较乱的。

2.2 函数实现

/**
 * @Function: binarytree_create
 * @Description: 二叉树创建
 * @param   : none
 * @return  : 返回一个地址
 *            NULL,创建失败;
 *            other,创建成功
 */
binarytree * binarytree_create()
{
	/* 定义一个接收输入的变量和一颗树的结构体指针变量 */
	bitree_data ch;
	binarytree * T;
	
	/* 1. 输入结点数据 */
	/* 不要在这里打印提示信息，否则每次递归到最后一层的时候都会打印一遍 */
	// printf("Please enter a data(# means enpty):");
	scanf("%c", &ch);
	if(ch == '#') /* 递归的返回条件 */
		return NULL;
	/* 2. 申请内存空间 */
	T = (binarytree *)malloc(sizeof(binarytree));
	/* 3. 判断是否申请成功 */
	if(T == NULL)
	{
		printf("binary tree malloc failed!\n");
		return NULL;
	}
	/* 4. 递归创建左右子树 */
	T->data = ch;
	T->left = binarytree_create();
	T->right = binarytree_create();
	
	return T;
}

二、遍历实现

1. 先序遍历

【算法简述】：若二叉树为空树，则空操作；否则访问根结点，然后先序遍历左子树，最后先序遍历右子树。

/**
 * @Function: preorder_traverse_recursive
 * @Description: 递归法先序遍历二叉树
 * @param T : 要遍历的二叉树树的地址
 * @return  : none
 */
void preorder_traverse_recursive(binarytree * T)
{
	/* 1. 判断树是否存在 */
	if(T == NULL)
	{
		/* 不要在这里打印提示信息，否则每次递归到最后一层的时候都会打印一遍 */
		// printf("\nbinary tree is not existed!\n");
		return;
	}
	/* 2. 访问结点数据 */
	printf("%c ", T->data);
	/* 3. 递归访问左右子树 */
	preorder_traverse_recursive(T->left);
	preorder_traverse_recursive(T->right);

}

2. 中序遍历

【算法简述】：若二叉树为空树，则空操作；否则先中序遍历左子树，再访问根结点，最后中序遍历右子树。

/**
 * @Function: inorder_traverse_recursive
 * @Description: 递归法中序遍历二叉树
 * @param T : 要遍历的二叉树树的地址
 * @return  : none
 */
void inorder_traverse_recursive(binarytree * T)
{
	/* 1. 判断树是否存在 */
	if(T == NULL)
	{
		/* 不要在这里打印提示信息，否则每次递归到最后一层的时候都会打印一遍 */
		// printf("\nbinary tree is not existed!\n");
		return;
	}
	/* 2. 递归访问左右子树 */
	inorder_traverse_recursive(T->left);
	printf("%c ", T->data);
	inorder_traverse_recursive(T->right);

}

3. 后序遍历

【算法简述】：若二叉树为空树，则空操作；否则先后序遍历左子树，然后后序遍历右子树，最后访问根结点。

/**
 * @Function: postorder_traverse_recursive
 * @Description: 递归法后序遍历二叉树
 * @param T : 要遍历的二叉树树的地址
 * @return  : none
 */
void postorder_traverse_recursive(binarytree * T)
{
	/* 1. 判断树是否存在 */
	if(T == NULL)
	{
		/* 不要在这里打印提示信息，否则每次递归到最后一层的时候都会打印一遍 */
		// printf("\nbinary tree is not existed!\n");
		return;
	}

	/* 2. 递归访问左子树 */
	postorder_traverse_recursive(T->left);
	/* 3. 递归访问右子树 */
	postorder_traverse_recursive(T->right);
	/* 4. 打印子树的根节点数据 */
	printf("%c ", T->data);

}

4. 层次遍历

层次遍历借助链式队列实现，这里直接使用之前的链式队列实现文件，但是需要修改链式队列中存放的数据类型，以及一些相关函数中printf打印语句。

/**
 * @Function: layertorder_traverse_slinkedqueue
 * @Description: 链式队列实现层次遍历二叉树
 * @param T : 要遍历的二叉树树的地址
 * @return  : none
 */
void layertorder_traverse_slinkedqueue(binarytree * T)
{
	/* 定义一个链式队列结构体指针变量 */
	slqueue_lq * lq;
	/* 1. 创建链式队列 */
	if ((lq = slqueue_create()) == NULL) 
		return;
	/* 2. 判断树是否存在 */
	if(T == NULL)
	{
		printf("binary tree is not existed!\n");
		return;
	}
	/* 3. 打印根结点数据同时根结点入队 */
	printf("%c ", T->data);
	slqueue_enqueue(lq, T);
	while(!slqueue_empty(lq))
	{
		T = slqueue_dequeue(lq);
		if(T->left != NULL)
		{
			printf("%c ", T->left->data);
			slqueue_enqueue(lq, T->left);
		}
		if(T->right != NULL)
		{
			printf("%c ", T->right->data);
			slqueue_enqueue(lq, T->right);
		}
	}
	puts("");
	slqueue_free(lq);
}