后序遍历递归算法

① 二叉树遍历的递归算法（C程序，先序中序或后序）

那个 答案我用了不行 啊,报错后改了运行没结果

② 后序遍历（ 用递归和非递归的方法一起都要）

我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
另外,团IDC网上有许多产品团购,便宜有口碑

③ 二叉树的遍历

遍历概念

所谓遍历(Traversal)是指沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 访问结点所做的操作依赖于具体的应用问题 遍历是二叉树上最重要的运算之一 是二叉树上进行其它运算之基础

遍历方案

．遍历方案 从二叉树的递归定义可知 一棵非空的二叉树由根结点及左 右子树这三个基本部分组成 因此 在任一给定结点上 可以按某种次序执行三个操作 （ ）访问结点本身(N) （ ）遍历该结点的左子树(L) （ ）遍历该结点的右子树(R) 以上三种操作有六种执行次序 NLR LNR LRN NRL RNL RLN 注意 前三种次序与后三种次序对称 故只讨论先左后右的前三种次序

．三种遍历的命名 根据访问结点操作发生位置命名 ① NLR 前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前 ② LNR 中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间) ③ LRN 后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后 注意 由于被访问的结点必是某子树的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解释为根 根的左子树和根的右子树 NLR LNR和LRN分别又称为先根遍历 中根遍历和后根遍历

遍历算法

．中序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )访问根结点 ( )遍历右子树

．先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( ) 访问根结点 ( ) 遍历左子树 ( ) 遍历右子树

．后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )遍历右子树 ( )访问根结点

．中序遍历的算法实现 用二叉链表做为存储结构 中序遍历算法可描述为 void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T >lchild) ③ printf( ％c T >data) // 访问结点 ④ InOrder(T >rchild); ⑤ } ⑥ } // InOrder

遍历序列

．遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同（如下图虚线所示） 具体线路为 从根结点出发 逆时针沿着二叉树外缘移动 对每个结点均途径三次 最后回到根结点 ．遍历序列 （ ） 中序序列 中序遍历二叉树时 对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时 得到的中序序列为 D B A E C F （ ） 先序序列 先序遍历二叉树时 对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时 得到的先序序列为 蔽拿衡 A B D C E F （ ） 后序序列 后宏做序遍历二叉树时 对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时 得到的后序序列为 D B E F C A 注意 （ ） 在搜索路线中 若访问结点均是第一次经过结点时进行的 则是前序遍历 若访问结点均是在第二次(或第三次)经过结点时进行敏羡的 则是中序遍历(或后序遍历) 只要将搜索路线上所有在第一次 第二次和第三次经过的结点分别列表 即可分别得到该二叉树的前序序列 中序序列和后序序列 （ ） 上述三种序列都是线性序列 有且仅有一个开始结点和一个终端结点 其余结点都有且仅有一个前趋结点和一个后继结点 为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念 对上述三种线性序列 要在某结点的前趋和后继之前冠以其遍历次序名称 【例】上图所示的二叉树中结点C 其前序前趋结点是D 前序后继结点是E 中序前趋结点是E 中序后继结点是F 后序前趋结点是F 后序后继结点是A 但是就该树的逻辑结构而言 C的前趋结点是A 后继结点是E和F

二叉链表的构造

． 基本思想 基于先序遍历的构造 即以二叉树的先序序列为输入构造 注意 先序序列中必须加入虚结点以示空指针的位置 【例】建立上图所示二叉树 其输入的先序序列是 ABD∮∮CE∮∮F∮∮

④ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}

⑤ 后序遍历是什么

对于题图为后序遍历为：DECBA。

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递核塌陆归算法两种。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、衫弊右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：

若二叉树为空则结束返回，

否则：

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点

如右图所示二改顷叉树

后序遍历结果：DEBFCA

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

⑥ 用递归算法先序中序后序遍历二叉树

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);

}

}

(6)后序遍历递归算法扩展阅读：

注意事项

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的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。