由二叉树的前序遍历和中序遍历打印出树的后序遍历（C语言）

时间：2021-05-17 17:29:39

      很久很久之前，我曾经转载过一个由前序遍历和中序遍历来构建二叉树的文章（http://www.cnblogs.com/ITEagle/archive/2010/01/17/1650138.html），但是我最近在准备保研的各种复试的时候，再去写这道题的时候，依然非常的痛苦，几次都不能一次性写对。于是我决定再自己写一篇文章，来分析这个简单的算法，我写的应该和上篇文章有很大不同的，因为那篇文章我完全看不进去。

      首先描述算法：

         1.在前序遍历中确定根节点，然后在中序遍历中确定左右子树。

         2.回到前序遍历，分别确定左右子树的根节点。

         3.如此递归，直到完成二叉树的构建。

         4.以后序遍历打印二叉树

      很明显，这个要用递归来实现。构建二叉树和打印二叉树是两个递归例程。算法很简单，根据算法写出C语言实现也不是什么难事，但是还是有很多需要注意的地方，如果这些地方记住如何写了，能一次写对这个程序，就比较容易了。

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

typedef struct node
{
	char data;
	struct node *lchild;
	struct node *rchild;
}NODE;

#define NUM 7
#define LEFT 0
#define RIGHT 1
#define EMPTY 101

char pred[]="ABDECFG";          //前序遍历
char inod[]="DBEACGF";          //中序遍历

int findInIno(char c);
int findInPre(char c);
NODE *createTree();
void create(NODE *root,int leftlen,int rightlen,int part);
void print(NODE *root);

int findInIno(char c)
{
	int i;
	for(i=0;i < NUM;i++)
	{
		if(c == inod[i])
			return i;
	}
	return -1;
}

int findInPre(char c)
{
	int i;
	for(i=0;i<NUM;i++)
	{
		if(c == pred[i])
			return i;
	}
	return -1;
}

NODE *createTree()
{
	NODE *root=(NODE*)malloc(sizeof(NODE));
	int rootIndex;
	
	root->data = pred[0];
	rootIndex = findInIno(root->data);
	create(root,rootIndex,NUM-rootIndex-1,LEFT);
	create(root,rootIndex,NUM-rootIndex-1,RIGHT);

	return root;
}

void main()
{
	NODE* root = createTree();
	print(root);
	getchar();
}

　　   以上是代码的主题部分，对应了算法的大体思路，先建树，然后打印树，难的在于建树和打印的两个递归函数。

void create(NODE *root,int leftlen,int rightlen,int part)
{
	int rootIndex;
	int preRootIndex = findInPre(root->data);
	NODE *p = (NODE*)malloc(sizeof(NODE));

	if(leftlen==0)
		root->lchild =(NODE*)EMPTY;
	if(rightlen==0)
		root->rchild=(NODE*)EMPTY;

	if(leftlen==0&&part==LEFT)
	{
		return;
	}

	if(rightlen==0&&part==RIGHT)
	{
		return;
	}

	if(part == LEFT)
	{
		p->data = pred[preRootIndex+1];
		root->lchild = p;
		preRootIndex = findInIno(root->data);
		rootIndex = findInIno(p->data);
		create(p,rootIndex-preRootIndex+leftlen,preRootIndex-rootIndex-1,LEFT);
		create(p,rootIndex-preRootIndex+leftlen,preRootIndex-rootIndex-1,RIGHT);
	}

	if(part == RIGHT)
	{
		p->data = pred[preRootIndex+leftlen+1];
		root->rchild = p;
		preRootIndex = findInIno(root->data);
		rootIndex = findInIno(p->data);
		create(p,rootIndex-preRootIndex-1,preRootIndex+rightlen-rootIndex,LEFT);
		create(p,rootIndex-preRootIndex-1,preRootIndex+rightlen-rootIndex,RIGHT);
	}
}

　　  这是建树的递归函数的代码。函数有四个参数，分别代表了当前的根节点（进入函数体之后，我们会先找到下一个根节点，并把这个根节点当作当前根，于是这个参数root代表的结点就成了前一个结点，这只一种表述方式）、左子树长度、右子树长度。part代表当前处理的是左子树还是右子树。选择使用这几个参数的理由是这样的：root传递当前根节点的数据，有part是因为左右子树的处理方式略有不同，左右字数的长度是用来计算下一次递归调用的参数的。

       这里非常关键的就是这个递归调用中，如何用当前根节点的坐标和左右字数的长度来计算，下一次调用中左右子树的长度。特别是处理左子树时候，递归调用时leftlen的计算和处理右子树时，rightlen的计算。在最一开始的时候，我利用了数组的开始坐标和结束坐标来计算，这是完全错误的。这里一定要用上一根节点坐标和当前根节点的坐标，以及传递进来的左右子树长度来计算。

       另外就是递归收敛的条件。只有当要处理左子树但是左子树长度为0或者处理右子树但右子树长度为0 的时候，才返回上一层调用。

void print(NODE *root)
{
	if(root->lchild == (NODE*)EMPTY &&root->rchild == (NODE*)EMPTY)
	{
		printf("%c",root->data);
	        return;
	}

	if(root->lchild != (NODE*)EMPTY)
            print(root->lchild);

	if(root->rchild != (NODE*)EMPTY)
	    print(root->rchild);

	printf("%c",root->data);
}

　　这是后序遍历结果打印的函数。也是递归调用。简单的理解为，在左右子树存在的情况下，先打印左子树，再打印右子树，最后打印根节点。若某子树不存在则跳过。递归调用。

     需要注意的依然是收敛的条件，打印到叶子结点的时候，不再继续调用，打印叶子结点数据，然后返回上层函数。

标签：

相关文章