大话数据结构-6.8 遍历二叉树 - 高飞网

6.8 遍历二叉树

2016-12-24 17:12:36.0

6.8 遍历二叉树

6.8.1 二叉树遍历原理

二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

6.8.2 二叉树的遍历方法

    1. 前序遍历

    规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。

    2. 中序遍历

    规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树。

    3. 后序遍历

    规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点。

    4. 层序遍历

    规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从右到右的顺序对结点逐个访问。

    为什么研究这么多遍历的方法?

    用图形的方式来表现树的结构,应该说非常直观和容易理解,但对于计算机来说,它只有循环、判断等方式来处理,也就是说,它只会处理线性序列,而刚才提到的四种遍历方法,其实都是把树中的结点变成某种意义的线性序列,这就给程序的实现带来了好处。

6.8.3 前序遍历算法

    二叉树的定义是用递归的方式,所以实现遍历算法也可以采用递归,而且极其简洁明了。

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
	if(T==NULL)
	{
		return ;
	}
	printf("%c",T->data);/* 显示结点数据 */
	PreOrderTraverse(T->lchild);/* 再先序遍历左子树 */
	PreOrderTraverse(T->rchild);/* 最后先序遍历右子树 */
}

6.8.4 中序遍历算法

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
	if(T==NULL)
	{
		return ;
	}
	InOrderTraverse(T->lchild);/* 中序遍历左子树 */
	printf("%c",T->data);/*显示结点数据 */
	InOrderTraverse(T->rchild);/* 最后中序遍历右子树 */
}

6.8.5 后序遍历算法

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
    {
        return ;
    }
    PostOrderTraverse(T->lchild);/* 后序遍历左子树 */
    PostOrderTraverse(T->rchild);/* 最后后序遍历右子树 */
    printf("%c",T->data);/*显示结点数据 */
}

6.8.6 推导遍历结果

    有一种题目是为了考查对二叉树遍历的掌握程度。已知一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF,求后序遍历结果是多少?

    三种遍历都是从根结点开始,前序遍历是先打印再递归左和右。所以前序遍历序列ABCDEF,第一个字母A为根结点。再由中序遍历序列是CBAEDF,可知C和B是A的左子树结点,E、D、F是A的右子树的结点。

    然后看前序中的C和B,ABCDEF,先B后C,所以B是A的左孩子,而C就只能是B的孩子,至于是左还是右不确定。看中序CBAEDF,打C后B,说明C是B的左孩子。

    再看前序的EDF,其顺序为ABCDEF,则D为A的右孩子,E和F是D的子孙。再看中序CBAEDF,E在D的左侧,而F在右侧,所以E为D的左孩子,F为D的右孩子。

    复原了二叉树后,就可以轻松地得到后序结果了:CBEFDA。

    如果足够熟练,不用画这棵二叉树,也可以得到后序的结果,因为刚才判断了A结点是根结点,那么它在后序序列中,一定是最后一个。同时C为B的左孩子,而B是A的孩子,意味着后序序列的前两位一定是CB,后样也可以得到EFD这样的后序顺序,最终就可以得到CBEFDA这样的序列。

    反过来,如果题目是:二叉树的中序序列是ABCDEFG,后序序列是BDCAFGE,求前序序列。

    由后序的BDCAFGE,得出E为根结点。根据中序后为两棵子树ABCD和FG。

    由后序序列的BDCAFGE得到,A为E的左孩子,前序序列目前分析为EA。由中序序列的ABCDEFG得到,BCD为A的右子孙。


    由后序序列BDCAFGE得到C为A的右孩子,前序序列目前分析为EAC。由中序ABCDEFG知,B为C的左孩子,D为C的右孩子。

    目前分析前序为EACBD。由后序BDCAFGE知道G为E的右孩子,由中序ABCDEFG得到F为G的左孩子。

    最终分析前序为:EACBDGF。

    这里可以得到两个二叉树遍历的性质:

  1. 已知前序和中序,可唯一确定一棵二叉树。
  2. 已知后序和中序,可唯一确定一棵二叉树。

    但是已知前序和后序,是不能确定一棵二叉树的。只能得到根结点。 

6.9 二叉树的建立

    为了让每个结点确认是否有左右孩子,需要对原树进行扩展,使每个结点的空指针引申出一个虚结点来,比如“#”。称这种处理后的二叉树为原二叉树的扩展二叉树。

二叉树的建立:

void CreateBiTree(BiTree *T)
{
	TElemType ch = str[i++];
	if(i>len)
	{
		return;
	}
	if(ch=='#')
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}