二叉树的遍历操作(二叉树的三种遍历例题)

本篇文章给大家谈谈二叉树的遍历操作，以及二叉树的三种遍历例题对应的知识点，文章可能有点长，但是希望大家可以阅读完，增长自己的知识，最重要的是希望对各位有所帮助，可以解决了您的问题，不要忘了收藏本站喔。

二叉树的层次遍历

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。

voidHierarchyBiTree(BiTreeRoot){

LinkQueue*Q;//保存当前节点的左右孩子的队列

InitQueue(Q);//初始化队列

if(Root==NULL)return;//树为空则返回

BiNode*p=Root;//临时保存树根Root到指针p中

Visit(p->data);//访问根节点

if(p->lchild)EnQueue(Q,p->lchild);//若存在左孩子，左孩子进队列

if(p->rchild)EnQueue(Q,p->rchild);//若存在右孩子，右孩子进队列

while(!QueueEmpty(Q))//若队列不空，则层序遍历{DeQueue(Q,p);//出队列

Visit(p->data);//访问当前节点

if(p->lchild)EnQueue(Q,p->lchild);//若存在左孩子，左孩子进队列

if(p->rchild)EnQueue(Q,p->rchild);//若存在右孩子，右孩子进队列

}

DestroyQueue(Q);//释放队列空间

return;

这个已经很详细了！你一定可以看懂的！加油啊！

二叉树前序遍历abdgcef中序遍历dgbaechf后序遍历怎么求

其实很简单跟着我的思路来。

。。画出来了这个树，就很简单了对吧前序遍历是先根。我们看abdgcef，第一个是a，说明整个树的根是a。中序遍历中根，我们看dgbaechf。既然a是整个树的根，那么a左边的dgb就是左子树，a右边echf就是右子树。再看前序遍历：a是根，那么接下来就应该是左子树了。我们把左子树分离出来看既然中序遍历已经知道是dgb了，那么前序遍历就是a后面的bdg。已知左子树的前序遍历是bdg，中序遍历是dgb，求左子树的形状。看，这不又变成刚才的问题了吗？只不过是规模减小了。显然，根是d，d的左儿子是b，d的右儿子是g。以此类推，就能画出整个Tree了。很简单吧！多用手模拟一下，多做两三题，很快就能掌握了。如果还不懂还可以Q我：328880142

c语言编程实现二叉树的三种遍历

二叉树有三种遍历方式，分别为先序遍历、中序遍历、后序遍历。

二叉树是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

顺序存储的二叉树是如何创建和遍历的

一、首先，简单介绍一下什么是“二叉树”

二叉树是n个结点的有限集合，它的定义具有递归性：

（1）当n=0时，为空树；

（2）当n=1时，只有一个结点，该节点称为根结点；

（3）当n>1时，除了根结点外的其他节点可分为互不相交的两个子集，称为左右子树，且左右子树本质上也都是二叉树。

图1二叉树

根据二叉树的结构和定义，可总结出二叉树的特点：

（1）非空二叉树的第i层最多有2∧（i-1）个结点；

（2）深度为k的二叉树最多有2∧k-1个结点

二叉树的存储结构

二叉树是非线性的结构，其每个结点最多有一个“前驱”，但可以有多个“后继”。它可以采用顺序存储结构和链式存储结构。

1、顺序存储结构

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的结点。必须把二叉树的所有结点安排成一个恰当的序列结点在这个序列中的相互位置能反映出结点之间的逻辑关系。

要介绍顺序存储结构，首先要了解一个概念——完全二叉树。如果深度为k，有n个结点的二叉树，当k与n满足2∧(k-1)≦n≦2∧k-1时，该二叉树称为完全二叉树。

对于一个二叉树，如果其不是一个完全二叉树，则首先增添一些并不存在的空结点，使之称为一个完全二叉树的形式，然后按照从上到下、从左到右的顺序将树中的结点存储在数组中。

以图1为例，其补成完全二叉树如图2所示。

图2补完后的二叉树

其顺序存储状态为：

ABCDE∧H∧∧FGI

显然，当一个非完全二叉树采用顺序存储结构时，由于需要增加许多空结点，因此会造成空间的大量浪费。

2、链式存储结构

二叉树的链式存储结构是指用链来表示二叉树结点之间的逻辑关系。

通常的方法是链表中的每个结点由3个域组成：

左指针域＋数据域＋右指针域即：Lchild+data+Rchild其中：data域存放结点的数据信息；Lchild和Rchild分别存放左、右支的指针，当某一支不存在时，相应的指针域为空(用符号∧国NULL表示)。

如图1中的c结点，因其左支不存在，因此其Lchild的值为NULL。

三、二叉树的遍历算法

二叉树常用的遍历方式有：前序遍历、中序遍历、后续遍历以及层序遍历。

1、前序遍历

先访问根结点，然后是左子树，最后是右子树。

图1的前序遍历结果为：

A->B->D->E->F->G->C->H->I

2、中序遍历

先访问左子树，然后是根结点，最后是右子树。

图1的中序遍历结果为：

D->B->F->E->G->A->C->I->H

3、后续遍历

先访问左子树，然后是右子树，最后是根结点。

图1的后续遍历结果为：

D->>F->G->E->I->H->B->C->A

4、层序遍历

从顶层的结点开始，从左向右依次遍历，之后转到第二层，继续从左向右遍历，……，直到所有的结点都遍历完成。

图1的层序遍历结果为：

A->B->C->D->E->H->F->G->I

知道中序和后序遍历，画二叉树和写出前序遍历

知道中序和后序遍历，以中序遍历是:HDMIBJNEAFKCG。后续遍历是HMIDNJEBKFGCA为例，画二叉树和写出前序遍历的方法和步骤如下1、从后序遍历知道，最后一个必然是根节点，因此A是根。再结合中序遍历可知HDMIBJNE是A的左子树部分，FKCG是右子树部分；

2、取A的右子树部分来看先，右子树部分的中序遍历：FKCE，后序遍历：KFGC。接着从后序遍历中看A的右子树部分KFGC，所以C是根，又从中序遍历知，FK是C的左子树部分，G是C右子树；

3、使用同样的方法，C的左子树部分，中序：FK，后序：KF。可以得出F是根，那么K只能是F的右子树了。此时如图所示，A的右子树部分都出来了；

4、再看，A的左子树部分HDMIBJE，中序：HDMIBJNE，后序：HMIDNJEB。后序遍历可知，B是根结点，那么再结合中序遍历可知道HDMI是B的左子树部分，JNE是B的右子树部分；

5、紧接着就是看B的左子树部分HDMI，中序：HDMI，后序：HMID，可知D是根，H是D的左子树，MI是D的右子树部分；

6、看到D的右子树部分，中序后序都是MI，根据后序中序的特性可知道，根只能是I，M是I的左子树；

7、再接着看看B的右子树部分JNE，中序：JNE，后序：NJE，后序看出E是根，中序看出E无右子树，只有JN是E的左子树部分；

8、最后看JN的中序：JN，后序：NJ，根据后序特性看出，J是根，中序看出N是J的右子树，那么整体的二叉树就出来了。

关于二叉树的遍历操作，二叉树的三种遍历例题的介绍到此结束，希望对大家有所帮助。