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

本文目录

• 用递归算法先序中序后序遍历二叉树
• 二叉树遍历该怎样写（计算机二级考试）
• 二叉树中序遍历递归算法
• 有一二叉树，中序遍历为DBAECF,前序遍历为ABDCEF，求后续遍历
• 二叉树的遍历算法
• 先序遍历二叉树的递归算法怎样理解（严蔚敏主编）
• 建立二叉树，并实现先序中序后序，用递归算法
• 二叉树先序遍历递归算法和非递归算法本质区别
• c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

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

1、先序

void PreOrderTraversal(BinTree BT)

{

    if( BT ) 

    {

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

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

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

    }

}

2、中序

void InOrderTraversal(BinTree BT)

{

    if(BT)

    {

        InOrderTraversal(BT-》Left);

        printf("%d\n", BT-》Data);

        InOrderTraversal(BT-》Right);

    }

}

3、后序

void PostOrderTraversal(BinTree BT)

{

    if (BT)

    {

        PostOrderTraversal(BT-》Left);

        PostOrderTraversal(BT-》Right);

        printf("%d\n", BT-》Data);

    }

}

扩展资料：

注意事项

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

二叉树遍历该怎样写（计算机二级考试）

前序遍历 是 根左右
中序 是 左根右
后序 是 左右根
都是递归遍历：
1．中序遍历的递归算法定义： 　　
若二叉树非空，则依次执行如下操作： 　　
(1)中序遍历左子树； 　　
(2)访问根结点； 　　
(3)中序遍历右子树。 　　
2．先序（前序）遍历的递归算法定义： 　　
若二叉树非空，则依次执行如下操作： 　　
(1) 访问根结点； 　　
(2) 先序遍历左子树； 　　
(3) 先序遍历右子树。 　　
3．后序遍历得递归算法定义： 　　
若二叉树非空，则依次执行如下操作： 　　
(1)后序遍历左子树； 　　
(2)后序遍历右子树； 　　
(3)访问根结点

二叉树中序遍历递归算法

if(T){
if(InOrderTraverse(T-》l,Visit))
if(Visit(T-》data))
if(InOrderTraverse(T-》r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍历二叉树
这段程序我全有，具体如下：
#include 《alloc.h》
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)《 (b))
#define LQ(a,b) ((a)《=(b))
typedef struct BinaryTree //定义二叉树
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//
BiNode * new()//为新结点开辟空间
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)//创建新有子树
{
if ((all==0)||i》16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)-》data=all;
CreateSubTree(&((*T)-》l),all,2*i);
CreateSubTree(&((*T)-》r),all,2*i+1);
}
CreateBiTree(BiTree *T)//创建新结点
{
ElemType all={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)//输出
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍历
{
if(T){
if(Visit(T-》data))
if(PreOrderTraverse(T-》l,Visit))
if(PreOrderTraverse(T-》r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍历
{
if(T){
if(InOrderTraverse(T-》l,Visit))
if(Visit(T-》data))
if(InOrderTraverse(T-》r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T-》data){ *p=T;return TRUE;}
else if LT(key,T-》data) SearchBST(T-》l,key,T,p);
else SearchBST(T-》r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s-》data=e;s-》l=s-》r=NULL;
if(!p) *T=s;
else if (LT(e,p-》data)) p-》l=s;
else p-》r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)-》r){
q=(*p);
(*p)=(*p)-》l;
****(q);
}
else if(!(*p)-》l){
q=(*p);
(*p)=(*p)-》r;
****(q);
}
else {
/* q=(*p);
s=(*p)-》l;
while(s-》r) {q=s; s=s-》r;}
(*p)-》data=s-》data;
if(q!=(*p) ) q-》r=s-》l;
else q-》l=s-》l;
****(s);
*/
q=s=(*p)-》l;
while(s-》r) s=s-》r;
s-》r=(*p)-》r;
****(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)-》data)) Delete(T);
else if ( LT(key,(*T)-》data)) DeleteBST( &((*T)-》l), key);
else DeleteBST( &((*T)-》r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i《10;i++)
InsertBST(&sroot,a);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i《3;i++)
DeleteBST(&sroot,a);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}

有一二叉树，中序遍历为DBAECF,前序遍历为ABDCEF，求后续遍历

先给出结果吧，后序遍历为DBAEFC。解释有些麻烦，尽量能说得清楚一些吧。

前序遍历先访问根节点，然后前序遍历左子树，最后前序遍历右子树，这是一种递归的算法，由于第二步是前序遍历左子树，这样可以设想根节点的左子树还有一左子树，就会再先访问左子树的根节点，再前序遍历。中序遍历先中序遍历左子树，然后访问根节点，最后中序遍历右子树。

我们看到前序遍历的结果为ABDCEF，可以知道根节点是A，再看中序遍历的结果为DBAECF，可以看到根节点A在中间，两个节点DB肯定在根节点的左子树，节点ECF肯定在根节点的右子树。再看前序遍历的结果，根节点A后访问B（所以B肯定是D的根节点），最后是D，所以再看中序遍历（先中序遍历左子树），所以D是B的左子树。右子树部分也类推。很容易看到C是右子树的根节点（前序遍历先访问根节点），然后可推出E是左子树，F是右子树。

画了一幅图片，可能看图好理解一些

二叉树的遍历算法

void
preorder(BiTree
root)
/*先序遍历输出二叉树结点，root为指向二叉树根节点的指针*/
{
if（root!=NULL）
{
printf(root-》data);
preorder(root-》Lchild);
preorder(root-》Rchild);
}
}
你看好这个程序,你首先定义了一个preorder函数,然后在函数体中又调用了本函数,这是函数的自调用.执行printf(root-》data);语句的时候输出当前遍历的数据,preorder(root-》Lchild);在执行到4的时候,root-》Lchild=NULL,但是执行preorder(root-》Rchild);语句,由此转向下一个结点,即5

先序遍历二叉树的递归算法怎样理解（严蔚敏主编）

先序调用的时候，递归函数，先序函数会一直递归，直到t-》next为空，即t为叶节点，需要注意的是当t-》next 为空时，函数的实参没有传过去，所以t指向叶结点的父节点，更要注意的是，先序调用的递归函数还没执行完，在先序调用的最里层，要执行这个函数的最后一个语句，即先序访问右子树。
在了解递归函数时，要注意函数是一层一层执行的，把没有调用的函数看作哦是第一层，第一次调用的时候，，势必会第二次遇到调用函数，变成第二层，，，，

建立二叉树，并实现先序中序后序，用递归算法

#include
《stdio.h》
#include《conio.h》
#include
《malloc.h》
typedef
char
TElemType;
typedef
struct
BiTNode{
TElemType
data;
/*二叉树数据域*/
struct
BiTNode
*lchild,
*rchild;/*
左右孩子指针*/
}BiTNode,
*BiTree;/*二叉树的二叉链表存储表示*/
BiTree
CreateBiTree(void)/*按先序次序输入二叉树中结点的值，’#’代表空树*/
{
TElemType
e;
BiTree
tmp
=
NULL;
if(
(e=getchar())!=’#’
){
//getchar();
/*接收回车符*/
tmp=(BiTree)malloc(sizeof(BiTNode));
if(!tmp)
return
NULL;
tmp-》data=e;
printf("input
%c:left
child:",e);
/*请输入左孩子：*/
tmp-》lchild=CreateBiTree();
printf("input
%c:right
child:",e);
/*请输入右孩子：*/
tmp-》rchild=CreateBiTree();
}
else
getchar();/*接收回车符*/
return
tmp;
}
void
PreOrderTraverse(BiTree
bt)
/*先序遍历二叉树*/
{
if(bt){
printf("%c
",
bt-》data);
/*输出根结点数据域的值*/
PreOrderTraverse(bt-》lchild);
/*先序遍历左子树*/
PreOrderTraverse(bt-》rchild);
/*先序遍历右子树*/
}
}
void
InOrderTraverse(BiTree
bt)
/*中序遍历二叉树*/
{
if(bt){
InOrderTraverse(bt-》lchild);
/*中序遍历左子树*/
printf("%c
",
bt-》data);
/*输出根结点数据域的值*/
InOrderTraverse(bt-》rchild);
/*中序遍历右子树*/
}
}
void
PostOrderTraverse(BiTree
bt)
/*后序遍历二叉树*/
{
if(bt){
PostOrderTraverse(bt-》lchild);
/*后序遍历左子树*/
PostOrderTraverse(bt-》rchild);
/*后序遍历右子树*/
printf("%c
",
bt-》data);
/*输出根结点数据域的值*/
}
}
void
main()
{
BiTree
bt;
printf("input
Root:");
/*请输入根结点：*/
bt
=
CreateBiTree();/*按先序次序创建二叉树*/
printf("PreOrderTraverse:");
PreOrderTraverse(bt);
/*递归先序遍历二叉树*/
printf("InOrderTraverse:");
InOrderTraverse(bt);
/*递归中序遍历二叉树*/
printf("PostOrderTraverse:");
PostOrderTraverse(bt);
/*递归后序遍历二叉树*/
printf("\n");
getch();
}

二叉树先序遍历递归算法和非递归算法本质区别

1. 先序遍历
　　在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT-》Data); //对节点做些访问比如打印
PreOrderTraversal(BT-》Left); //访问左儿子
PreOrderTraversal(BT-》Right); //访问右儿子
}
}
　　由递归代码可以看出，该递归为尾递归（尾递归即递归形式在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈
　　a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
　　b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
　　c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
　　实现代码如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问（打印）后压入堆栈
{
printf("%d\n", T-》Data);
Push(S, T);
T = T-》Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T-》Right; //转向右子树
}
}
}
由以上例子可以看出，递归与非递归的本质区别就是递归是不断循环调用同一过程，非递归是循环执行同一个动作，并且非递归有入栈与出栈的过程，因此更节省存储空间。个人浅见，欢迎指正。

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); // 递归销毁右子树，如无右子树，则不执行任何操作
****(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
}