用递归算法先序中序后序遍历二叉树
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的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。
求一个用C语言写的建立二叉树并且先序中序后序遍历这个二叉树
其实这个程序很简单的。 代码如下：
#include《stdio.h》
#include《malloc.h》
#define MAX_TREE_SIZE 100
typedef struct {
int i;
}TElemType;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &T)
{
char ch;
scanf(“%c“,&ch);
getchar();
if(ch==’ ’||ch==’\n’)
{
T=NULL;
}
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
T-》data=ch;
CreateBiTree(T-》lchild);
CreateBiTree(T-》rchild);
}
return 1;
}//CreateBiTree()
int Visit(char ch)
{
printf(“%c“,ch);
return 1;
}
int PreOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
if(Visit(T-》data))
if(PreOrderTraverse(T-》lchild,Visit))
if(PreOrderTraverse(T-》rchild,Visit)) return 1;
}else return 1;
}
int InOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
if(InOrderTraverse(T-》lchild,Visit))
if(Visit(T-》data))
if(InOrderTraverse(T-》rchild,Visit)) return 1;
}else return 1;
}
int PostOrderTraverse(BiTree T,int(* Visit)(char ch))
{
if(T)
{
if(PostOrderTraverse(T-》lchild,Visit))
if(PostOrderTraverse(T-》rchild,Visit))
if(Visit(T-》data)) return 1;
}else return 1;
}
void main()
{
BiTree T;
printf(“从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：\n“);
CreateBiTree(T);
printf(“先序遍历为：“);
PreOrderTraverse(T,Visit);
printf(“\n“);
printf(“中序遍历为：“);
InOrderTraverse(T,Visit);
printf(“\n“);
printf(“后序遍历为：“);
PostOrderTraverse(T,Visit);
}
已知某二叉树的前序序列及中序序列要求输出其后序序列，试写出程序
输入树的节点，输入0结束
1
2
3
4
5
6
7
8
9
0
中序打印
1-》2-》3-》4-》5-》6-》7-》8-》9-》
后序打印
9-》8-》7-》6-》5-》4-》3-》2-》1-》
前序打印
1-》2-》3-》4-》5-》6-》7-》8-》9-》
//////////////////////////////////////////////////////////////////////////////////////////
#include《stdlib.h》
#include《stdio.h》
typedef
struct
tree
{
struct
tree
*left;
int
date;
struct
tree
*right;
}treenode,*b_tree;
///////按顺序插入节点/////////////////////
b_tree
insert(b_tree
root,int
node)
{
b_tree
newnode;
b_tree
currentnode;
b_tree
parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode-》date=node;
newnode-》right=NULL;
newnode-》left=NULL;
if(root==NULL)
return
newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode-》date》node)
currentnode=currentnode-》left;
else
currentnode=currentnode-》right;
}
if(parentnode-》date》node)
parentnode-》left=newnode;
else
parentnode-》right=newnode;
}
return
root;
}
//////建立树///////////////////
b_tree
creat(int
*date,int
len)
{
b_tree
root=NULL;
int
i;
for(i=0;i《len;i++)
root=insert(root,date);
return
root;
}
//////中序打印////////////////
void
print1(b_tree
root)
{if(root!=NULL){
print1(root-》left);
printf(“%d-》“,root-》date);
print1(root-》right);}
}
//////后序打印////////////////
void
print2(b_tree
root)
{if(root!=NULL){
print2(root-》left);
print2(root-》right);
printf(“%d-》“,root-》date);}
}
//////前序打印////////////////
void
print3(b_tree
root)
{if(root!=NULL){
printf(“%d-》“,root-》date);
print3(root-》left);
print3(root-》right);}
}
///////测试函数//////////////////
void
main()
{
b_tree
root=NULL;
int
i,index;
int
value;
int
nodelist;
printf(“输入树的节点，输入0结束\n“);
index=0;
scanf(“%d“,value);
while(value!=0)
{
nodelist=value;
index=index+1;
scanf(“%d“,value);
}
root=creat(nodelist,index);
printf(“\n中序打印\n“);
print1(root);
printf(“\n后序打印\n“);
print2(root);
printf(“\n前序打印\n“);
print3(root);}
二叉树的先序,中序,后序遍历是
前序遍历就是先遍历根节点，然后遍历左节点，最后是右节点；
中序遍历就是先遍历左节点，然后遍历中间的根节点，最后是右节点；
后序遍历就是先遍历左节点，然后遍历是右节点，最后是中间的根节点。
二叉树的这三种遍历方法，是按照每颗子树的根节点顺序遍历的。
扩展资料：
例子：已知二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）
(1)中序遍历：debac
后序遍历：dabec
后序遍历序列的最后一个结点是根结点，所以可知c为根结点。
中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点c只有左子树，没有右子树。
(2)中序遍历：deba
后序遍历：dabe
后序遍历序列的最后一个结点是根结点，所以可知e为c的左子树的根结点。
中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点e的左子结点是d，右子树是ba。
(3)中序遍历：ba
后序遍历：ab
由后序遍历序列可知b为e的右子树的根结点。由中序遍历序列中可看出，a为根结点b的右子结点。
怎样建立一个二叉树实现二叉树的先序中序后序和遍历
其实这个程序很简单的。 代码如下：
#include《stdio.h》
#include《malloc.h》
#define MAX_TREE_SIZE 100
typedef struct {
int i;
}TElemType;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &T)
{
char ch;
scanf(“%c“,&ch);
getchar();
if(ch==’ ’||ch==’\n’)
{
T=NULL;
}
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
T-》data=ch;
CreateBiTree(T-》lchild);
CreateBiTree(T-》rchild);
}
return 1;
}//CreateBiTree()
int Visit(char ch)
{
printf(“%c“,ch);
return 1;
}
int PreOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
if(Visit(T-》data))
if(PreOrderTraverse(T-》lchild,Visit))
if(PreOrderTraverse(T-》rchild,Visit)) return 1;
}else return 1;
}
int InOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
if(InOrderTraverse(T-》lchild,Visit))
if(Visit(T-》data))
if(InOrderTraverse(T-》rchild,Visit)) return 1;
}else return 1;
}
int PostOrderTraverse(BiTree T,int(* Visit)(char ch))
{
if(T)
{
if(PostOrderTraverse(T-》lchild,Visit))
if(PostOrderTraverse(T-》rchild,Visit))
if(Visit(T-》data)) return 1;
}else return 1;
}
void main()
{
BiTree T;
printf(“从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：\n“);
CreateBiTree(T);
printf(“先序遍历为：“);
PreOrderTraverse(T,Visit);
printf(“\n“);
printf(“中序遍历为：“);
InOrderTraverse(T,Visit);
printf(“\n“);
printf(“后序遍历为：“);
PostOrderTraverse(T,Visit);
}
编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法
文件 main.cpp 代码如下： #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 }这样可以么？
求c#前中后序遍历二叉树的算法及思想
下面简单介绍一下几种算法和思路：
先序遍历：
1. 访问根结点
2. 按先序遍历左子树;
3. 按先序遍历右子树;
4. 例如：遍历已知二叉树结果为：A-》B-》D-》G-》H-》C-》E-》F
中序遍历：
1. 按中序遍历左子树;
2. 访问根结点;
3. 按中序遍历右子树;
4. 例如遍历已知二叉树的结果：B-》G-》D-》H-》A-》E-》C-》F
后序遍历：
1. 按后序遍历左子树;
2. 按后序遍历右子树;
3. 访问根结点;
4. 例如遍历已知二叉树的结果：G-》H-》D-》B-》E-》F-》C-》A
层次遍历：
1.从上到下,从左到右遍历二叉树的各个结点(实现时需要借辅助容器);
2.例如遍历已知二叉树的结果：A-》B-》C-》D-》E-》F-》G-》H
附加代码：
二叉遍历算法解决方案
using System;
using System.Collections.Generic;
using System.Text;
namespace structure
{
class Program
{
二叉树结点数据结构的定义#region 二叉树结点数据结构的定义
//二叉树结点数据结构包括数据域,左右结点以及父结点成员;
class nodes《T》
{
T data;
nodes《T》 Lnode, Rnode, Pnode;
public T Data
{
set { data = value; }
get { return data; }
}
public nodes《T》 LNode
{
set { Lnode = value; }
get { return Lnode; }
}
public nodes《T》 RNode
{
set { Rnode = value; }
get { return Rnode; }
}
public nodes《T》 PNode
{
set { Pnode = value; }
get { return Pnode; }
}
public nodes()
{ }
public nodes(T data)
{
this.data = data;
}
}
#endregion
#region 先序编历二叉树
static void PreOrder《T》(nodes《T》 rootNode)
{
if (rootNode != null)
{
Console.WriteLine(rootNode.Data);
PreOrder《T》(rootNode.LNode);
PreOrder《T》(rootNode.RNode);
}
}
#endregion
计算机二级二叉树前序中序后序
二叉树遍历方式是数据结构的基础知识，作为计算机专业的大学生，我的理解如下：
1、 前序遍历
它的遍历顺序是：先访问根结点，再进入这个根结点的左子树；以上述方式遍历完所有左子树后，再进入它的右子树，以同样的方式遍历右子树中的结点，即根结点→左子树→右子树。下图中1为主根结点，245为左子树，367为右子树；在左子树中，2为根结点，4为左子树，5为右子树；在右子树中，3为根结点，6为左子树，7为右子树。依次将每个树中的根结点、左子树以及右子树分清，只到子树中只剩一个元素为止。综上可知，结果为1→2→4→5→3→6→7。
例子
2、 中序遍历
它的遍历顺序是：先进入根结点的左子树，以同样方式遍历左子树结点，在访问当前的根结点，最后进入根结点的右子树，以同样方式遍历右子树结点，即左子树→根结点→右子树。由前序遍历中分析可知结果为4→2→5→1→6→3→7。
3、 后序遍历
它的遍历顺序是：先进入根结点的左子树，以同样方式遍历左子树结点，再进入根结点的右子树，以同样方式遍历右子树结点，左右子树都遍历完后，才能访问当前根结点，即左子树→右子树→根结点。由前序遍历中分析可知结果为4→5→2→6→7→3→1。
试一试，二叉树例题与解答：
例题
前序遍历：A→B→D→F→G→H→I→E→C
中序遍历：F→D→H→G→I→B→E→A→C
后序遍历：F→H→I→G→D→E→B→C→A
C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历下面有我的建树函数，有注释的
#include“cstdio“
#include“vector“
#include“cstring“
#include“algorithm“
using namespace std;
const int maxn =30;
struct node{
int data;
node* lchild;
node* rchild;
};
int n;
int in;
bool vis={false};
vector《int》 lev;
node* create(vector《int》 lev,int inl,int inr){
if(lev.size()==0) return NULL;
if(inl》inr) return NULL;
//printf(“00\n“);
node* root= new node;
root-》data =lev;
int k;
for(k=inl;k《=inr;k++){
if(lev)
break;
}
for(int j=inl;j《=k-1;j++)
vis=true;
vector《int》 tempLeft,tempRight;//要函数体内新建
for(int i=1;i《lev.size();i++){
if(vis==true)
tempLeft.push_back(lev);
else
tempRight.push_back(lev);
}
root-》lchild =create(tempLeft,inl,k-1);
root-》rchild =create(tempRight,k+1,inr);
return root;
}
void preorder(node* root){
if(root==NULL)
return;
printf(“%d “,root-》data);
preorder(root-》lchild);
preorder(root-》rchild);
}
int main(){
scanf(“%d“,&n);
int x;
for(int i=0;i《n;i++){
scanf(“%d“,&x);
lev.push_back(x);
}
for(int j=0;j《n;j++)
scanf(“%d“,∈);
node *root =create(lev,0,n-1);
preorder(root);
return 0;
}
二叉树遍历问题（前序，中序，后序)
前序遍历（DLR）
前序遍历也叫做先根遍历，可记做根左右。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
中序遍历（LDR）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
后序遍历（LRD）
后序遍历也叫做后根遍历，可记做左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。
如上图所示二叉树
前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树
遍历结果：a,b,e,f,c,g
中序遍历，也叫中根遍历，顺序是
左子树，根，右子树
遍历结果：e,b,f,a,g,c
后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根
遍历结果：e,f,b,g,c,a