树的后跟序遍历迭代算法

‘壹’ 二叉树的遍历算法

这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

‘贰’ 请教一下数据结构 二叉树的先序遍历 中序遍历 后序遍历 是怎么弄的

所谓先序、中序和后序的区别在于访问根的时机，分别是BLR、LBR和LRB，其中B、L、R分别表示根结点、根结点的左子树和根结点的右子树。
以后序遍历为例进行讲解。

后序遍历算法：
(1) 后序遍历根结点的左子树；
(2) 后序遍历根结点的右子树。
(3) 访问二叉树的根结点；

你的方法是将树分解为根、左子树、右子树，再将子树继续按前述方法分解，直至每一部分只剩一个结点或空为止。

对该图，分解为
根(a)，根的左子树(bde，不分先后)，根的右子树(cf，不分先后)
故后序的基本顺序是(bde)、(cf)、(a)

同样的道理，对(bde)和(cf)也进行分解：
根(b)、左子树(d)、右子树(e) 后序的基本顺序是deb
根(c)、左子树(空)、右子树(f) 后序的基本顺序是fc

整合起来就是：d e b f c a

‘叁’ 树的前序遍历、中序遍历、后序遍历详解

对于当前节点，先输出该节点，然后输出他的左孩子，最后输出他的右孩子。以上图为例，递归的过程如下：
（1）：输出 1，接着左孩子；
（2）：输出 2，接着左孩子；
（3）：输出 4，左孩子为空，再接着右孩子；
（4）：输出 6，左孩子为空，再接着右孩子；
（5）：输出 7，左右孩子都为空，此时 2 的左子树全部输出，2 的右子树为空，此时 1 的左子树全部输出，接着 1 的右子树；
（6）：输出 3，接着左孩子；
（7）：输出 5，左右孩子为空，此时 3 的左子树全部输出，3 的右子树为空，至此 1 的右子树全部输出，结束。

对于当前结点，先输出它的左孩子，然后输出该结点，最后输出它的右孩子。以上图为例：
（1）：1-->2-->4，4 的左孩子为空，输出 4，接着右孩子；
（2）：6 的左孩子为空，输出 6，接着右孩子；
（3）：7 的左孩子为空，输出 7，右孩子也为空，此时 2 的左子树全部输出，输出 2，2 的右孩子为空，此时 1 的左子树全部输出，输出 1，接着 1 的右孩子；
（4）：3-->5，5 左孩子为空，输出 5，右孩子也为空，此时 3 的左子树全部输出，而 3 的右孩子为空，至此 1 的右子树全部输出，结束。

对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点。依旧以上图为例：
（1）：1->2->4->6->7，7 无左孩子，也无右孩子，输出 7，此时 6 无左孩子，而 6 的右子树也全部输出，输出 6，此时 4 无左子树，而 4 的右子树全部输出，输出 4，此时 2 的左子树全部输出，且 2 无右子树，输出 2，此时 1 的左子树全部输出，接着转向右子树；
（2）：3->5，5 无左孩子，也无右孩子，输出 5，此时 3 的左子树全部输出，且 3 无右孩子，输出 3，此时 1 的右子树全部输出，输出 1，结束。

已知：
前序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
求后序遍历
首先，要先画出这棵二叉树，怎么画呢？根据上面说的我们一步一步来……
1.先看前序遍历，前序遍历第一个一定是根节点，那么我们可以知道，这棵树的根节点是G，接着，我们看中序遍历中，根节点一定是在中间访问的，那么既然知道了G是根节点，则在中序遍历中找到G的位置，G的左边一定就是这棵树的左子树，G的右边就是这棵树的右子树了。
2.我们根据第一步的分析，大致应该知道左子树节点有：ADEF，右子树的节点有：HMZ。同时，这个也分别是左子树和右子树的中序遍历的序列。
3.在前序遍历遍历完根节点后，接着执行前序遍历左子树，注意，是前序遍历，什么意思？就是把左子树当成一棵独立的树，执行前序遍历，同样先访问左子树的根，由此可以得到，左子树的根是D，第2步我们已经知道左子树是ADEF了，那么在这一步得到左子树的根是D，请看第4步。
4.从第2步得到的中序遍历的节点序列中，找到D，发现D左边只有一个A，说明D的左子树只有一个叶子节点，D的右边呢？我们可以得到D的右子树有EF，再看前序遍历的序列，发现F在前，也就是说，F是先前序遍历访问的，则得到E是F的左子树，只有一个叶子节点。
5.到这里，我们可以得到这棵树的根节点和左子树的结构了。如下图：

6.接着看右子树，在第2步的右子树中序遍历序列中，右子树是HMZ三个节点，那么先看前序遍历的序列，先出现的是M，那么M就是右子树的根节点，刚好，HZ在M的左右，分别是它的左子树和右子树，因此，右子树的结构就出来了：

7.到这里，我们可以得到整棵树的结构：

中序遍历：ADEFGHMZ
后序遍历：AEFDHZMG

1..根据后序遍历的特点（左右中），根节点在结尾，确定G是根节点。根据中序遍历的特点（左中右），确定ADEF组成左子树，HMZ组成右子树。

2.分析左子树。ADEF这四个元素在后序遍历（左右中）中的顺序是AEFD，在中序遍历（左中右）中的顺序是ADEF。根据后序遍历（左右中）的特点确定D是左子树的节点，根据中序遍历（左中右）的特点发现A在D前面，所以A是左子树的左叶子，EF则是左子树的右分枝。
EF在后序（左右中）和中序（左中右）的相对位置是一样的，所以EF关系是左右或者左中，排除左右关系（缺乏节点），所以EF关系是左中。
到此得出左子树的形状

3.分析右子树。HMZ这三个元素在中序遍历（左中右）的顺序是HMZ，在后序遍历（左右中）的顺序是HZM。根据后序遍历（左右中）的特点，M在尾部，即M是右子树的节点。再根据中序遍历（左中右）的特点，确定H（M的前面）是右子树的左叶子，Z（M的后面）是右子树的右叶子。

所以右子树的形状

‘肆’ 已知二叉树的中序遍历是DBEAFC.前序遍历是ABDECF.后序遍历怎么算

1、首先声明一个静态二叉树节点类，通过该类对象，可以构建一棵二叉树结构。

‘伍’ 树的后序遍历具体什么意思呢

树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。

⑴访问结点本身（N），

⑵遍历该结点的左子树（L），

⑶遍历该结点的右子树（R）。

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。

(5)树的后跟序遍历迭代算法扩展阅读：

二叉树前序访问如下：

从根结点出发，则第一次到达结点A，故输出A;

继续向左访问，第一次访问结点B，故输出B；

按照同样规则，输出D，输出H；

当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；

I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；

向E左子树，故输出J；

按照同样的访问规则，继续输出C、F、G。

二叉树中序访问如下：

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；

到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；

H右子树为空，则返回至D，此时第二次到达D，故输出D；

由D返回至B，第二次到达B，故输出B；

按照同样规则继续访问，输出J、E、A、F、C、G。

‘陆’ 先序遍历和后序遍历是什么

1、先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：ABDECF

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

如右图所示二叉树

后序遍历结果：DEBFCA

已知前序遍历和中序遍历，就能确定后序遍历。

(6)树的后跟序遍历迭代算法扩展阅读：

图的遍历算法主要有两种，

一种是按照深度优先的顺序展开遍历的算法，也就是深度优先遍历；

另一种是按照宽度优先的顺序展开遍历的算法，也就是宽度优先遍历。宽度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。

如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。

如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。

利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。宽度优先遍历又名广度优先遍历。通过沿着图的宽度遍历图的节点，如果所有节点均被访问，算法随即终止。宽度优先遍历的实现一般需要一个队列来辅助完成。

宽度优先遍历和深度优先遍历一样也是一种盲目的遍历方法。也就是说，宽度遍历算法并不使用经验法则算法， 并不考虑结果的可能地址，只是彻底地遍历整张图，直到找到结果为止。图的遍历问题分为四类：

1、遍历完所有的边而不能有重复，即所谓“欧拉路径问题”（又名一笔画问题）；

2、遍历完所有的顶点而没有重复，即所谓“哈密顿路径问题”。

3、遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；

4、遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。

对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。

‘柒’ 用递归算法先序中序后序遍历二叉树

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(“%d ”, BT->Data); //对节点做些访问比如打印

PreOrderTraversal(BT->Left); //访问左儿子

PreOrderTraversal(BT->Right); //访问右儿子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、后序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(7)树的后跟序遍历迭代算法扩展阅读：

注意事项

1、前序遍历

从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。

2、中序遍历

从整棵二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。

3、后序遍历

将整棵二叉树的根结点入栈，取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。

‘捌’ 知道一棵树的中序遍历和后序遍历，如何推算出这颗树的前序遍历

树中已知先序和中序求后序。
如先序为：abdc,中序为：bdac .
则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。
算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例
中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含
元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的
进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右
子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。
关于“已知先序和后序求中序”的思考：该问题不可解，因为对于先序和后序不能唯一的确定
中序，比如先序为 ab，后序为ba，我只能知道根节点为a，而并不能知道b是左子树还是右子树
，由此可见该问题不可解。当然也可以构造符合中序要求的所有序列。

2004.12.5
*/
#include <stdio.h>
int find(char c,char A[],int s,int e) /**//* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/**//* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/**//* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/**//* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /**//* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /**//* 子树子仅为一个节点时直接输出并完成。 */<br/> return ;<br/> }
c=pre[pre_s]; /**//* c储存根节点。 */
k=find(c,in,in_s,in_e); /**//* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /**//* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /**//* 递归求解分割的右子树。 */
printf("%c",c); /**//* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}

//..

已知二叉树的先序和中序求后序－转贴自CSDN

二叉树的根结点（根据三种遍历）只可能在左右（子树）之间，或这左子树的左边，或右子树的右边。
如果已知先序和中序（如果是中序和后序已知也可以，注意：如果是前序和后序的求中序是不可能实现的），先确定这棵二叉树。
步骤：1，初始化两个数组，存放先序合中序。
2，对比先序和中序，在中序忠查找先序的第一个元素，则在中序遍历中将这个元素的左右各元素分成两部分。即的左边的部分都在这个元素的左子树中，右边的部分都在右子树中。
3，然后从从先序的第二个元素开始继续上面的步骤。

如 先序：1 2 3 4 5 6 7 8 9 10 11
后序：3 2 5 4 1 7 9 8 11 10 6

level 1: 1
2: 2 3
3: 3 4 7
4: 5 8
5: 9 10
6: 11

这

‘玖’ 已知一颗二叉树的后序遍历序列和中序遍历序列确定二叉树算法

1. 依据后序遍历序列的最后一个元素确定根结点T
2. 在中序序列中找到1中确定的根节点，其左边的序列L为根结点的左子树结点集合，其右边的序列R为根结点右子树结点集合。
3. 将L看做一棵树的序列集合重复1,得到左子树的根结点，将R看做一棵树的序列集合重复1得到右子树的根结点。这两个结点即为T的左结点和右结点。
4. 将L看做一棵树的序列集合重复2得到L子树的左子树和右子树，将R看做一棵树的序列集合重复2得到R子树的左子树和右子树
5. 对得到的子树序列重复3，4直到产生的子树序列都为空为止

‘拾’ 什么是先、中、后根遍历什么是左子树、右子树和二叉树

1、先根遍历一般是先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的先根遍历结果是：ABDECF

6、二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。