2024年9月二叉树前序中序后序代码（用递归算法先序中序后序遍历二叉树）

　　⑴二叉树前序中序后序代码（用递归算法先序中序后序遍历二叉树

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

　　⑶voidPreOrderTraversal(BinTreeBT)

　　⑷printf(“%d

　　⑸”,BT-》Data);????//对节点做些访问比如打印

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

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

　　⑻voidInOrderTraversal(BinTreeBT)

　　⑼InOrderTraversal(BT-》Left);

　　⑽printf(“%d

　　⑾“,BT-》Data);

　　⑿InOrderTraversal(BT-》Right);

　　⒀voidPostOrderTraversal(BinTreeBT)

　　⒁PostOrderTraversal(BT-》Left);

　　⒂PostOrderTraversal(BT-》Right);

　　⒃printf(“%d

　　⒄“,BT-》Data);

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

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

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

　　⒈求一个用C语言写的建立二叉树并且先序中序后序遍历这个二叉树

　　⒉其实这个程序很简单的。代码如下：#include《stdio.h》#include《malloc.h》#defineMAX_TREE_SIZEtypedefstruct{inti;}TElemType;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intCreateBiTree(BiTree&T){charch;scanf(“%c“,&ch);getchar();if(ch==’’||ch==’

　　⒊’){T=NULL;}else{T=(BiTNode*)malloc(sizeof(BiTNode));T-》data=ch;CreateBiTree(T-》lchild);CreateBiTree(T-》rchild);}return;}//CreateBiTree()intVisit(charch){printf(“%c“,ch);return;}intPreOrderTraverse(BiTreeT,int(*Visit)(charch)){if(T){if(Visit(T-》data))if(PreOrderTraverse(T-》lchild,Visit))if(PreOrderTraverse(T-》rchild,Visit))return;}elsereturn;}intInOrderTraverse(BiTreeT,int(*Visit)(charch)){if(T){if(InOrderTraverse(T-》lchild,Visit))if(Visit(T-》data))if(InOrderTraverse(T-》rchild,Visit))return;}elsereturn;}intPostOrderTraverse(BiTreeT,int(*Visit)(charch)){if(T){if(PostOrderTraverse(T-》lchild,Visit))if(PostOrderTraverse(T-》rchild,Visit))if(Visit(T-》data))return;}elsereturn;}voidmain(){BiTreeT;printf(“从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：

　　⒋“);CreateBiTree(T);printf(“先序遍历为：“);PreOrderTraverse(T,Visit);printf(“

　　⒌“);printf(“中序遍历为：“);InOrderTraverse(T,Visit);printf(“

　　⒍“);printf(“后序遍历为：“);PostOrderTraverse(T,Visit);}

　　⒎已知某二叉树的前序序列及中序序列要求输出其后序序列，试写出程序

　　⒏输入树的节点，输入结束中序打印-》-》-》-》-》-》-》-》-》后序打印-》-》-》-》-》-》-》-》-》前序打印-》-》-》-》-》-》-》-》-》//////////////////////////////////////////////////////////////////////////////////////////#include《stdlib.h》#include《stdio.h》typedefstructtree{structtree*left;intdate;structtree*right;}treenode,*b_tree;///////按顺序插入节点/////////////////////b_treeinsert(b_treeroot,intnode){b_treenewnode;b_treecurrentnode;b_treeparentnode;newnode=(b_tree)malloc(sizeof(treenode));newnode-》date=node;newnode-》right=NULL;newnode-》left=NULL;if(root==NULL)returnnewnode;else{currentnode=root;while(currentnode!=NULL){parentnode=currentnode;if(currentnode-》date》node)currentnode=currentnode-》left;elsecurrentnode=currentnode-》right;}if(parentnode-》date》node)parentnode-》left=newnode;elseparentnode-》right=newnode;}returnroot;}//////建立树///////////////////b_treecreat(int*date,intlen){b_treeroot=NULL;inti;for(i=;i《len;i++)root=insert(root,date);returnroot;}//////中序打印////////////////voidprint(b_treeroot){if(root!=NULL){print(root-》left);printf(“%d-》“,root-》date);print(root-》right);}}//////后序打印////////////////voidprint(b_treeroot){if(root!=NULL){print(root-》left);print(root-》right);printf(“%d-》“,root-》date);}}//////前序打印////////////////voidprint(b_treeroot){if(root!=NULL){printf(“%d-》“,root-》date);print(root-》left);print(root-》right);}}///////测试函数//////////////////voidmain(){b_treeroot=NULL;inti,index;intvalue;intnodelist;printf(“输入树的节点，输入结束

　　⒐“);index=;scanf(“%d“,value);while(value!=){nodelist=value;index=index+;scanf(“%d“,value);}root=creat(nodelist,index);printf(“

　　⒑“);print(root);printf(“

　　⒒“);print(root);printf(“

　　⒓“);print(root);}

　　⒔二叉树的先序,中序,后序遍历是

　　⒕前序遍历就是先遍历根节点，然后遍历左节点，最后是右节点；

　　⒖中序遍历就是先遍历左节点，然后遍历中间的根节点，最后是右节点；

　　⒗后序遍历就是先遍历左节点，然后遍历是右节点，最后是中间的根节点。

　　⒘二叉树的这三种遍历方法，是按照每颗子树的根节点顺序遍历的。

　　⒙例子：已知二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba

　　⒚中序遍历：debac

　　⒛后序遍历：dabec

　　后序遍历序列的最后一个结点是根结点，所以可知c为根结点。

　　中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点c只有左子树，没有右子树。

　　后序遍历序列的最后一个结点是根结点，所以可知e为c的左子树的根结点。

　　中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点e的左子结点是d，右子树是ba。

　　由后序遍历序列可知b为e的右子树的根结点。由中序遍历序列中可看出，a为根结点b的右子结点。

　　怎样建立一个二叉树实现二叉树的先序中序后序和遍历

　　其实这个程序很简单的。代码如下：

　　#include《stdio.h》#include《malloc.h》#define?MAX_TREE_SIZE??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==’

　　’){?T=NULL;}else{?T=(BiTNode?*)malloc(sizeof(BiTNode));?T-》data=ch;?CreateBiTree(T-》lchild);?CreateBiTree(T-》rchild);}return?;}//CreateBiTree()int?Visit(char?ch){printf(“%c“,ch);return?;}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?;}else?return?;}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?;}else?return?;}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?;}else?return?;}void??main(){BiTree??T;printf(“从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：

　　“);CreateBiTree(T);printf(“先序遍历为：“);PreOrderTraverse(T,Visit);printf(“

　　“);printf(“中序遍历为：“);InOrderTraverse(T,Visit);printf(“

　　“);printf(“后序遍历为：“);PostOrderTraverse(T,Visit);}

　　编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法

　　文件main.cpp代码如下：#include《malloc.h》//malloc()等#include《stdio.h》//标准输入输出头文件，包括EOF(=^Z或F)，NULL等#include《stdlib.h》//atoi()，exit()#include《math.h》//数学函数头文件，包括floor()，ceil()，abs()等#defineClearBiTreeDestroyBiTree//清空二叉树和销毁二叉树的操作一样typedefstructBiTNode{intdata;//结点的值BiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;intNil=;//设整型以为空voidvisit(inte){printf(“%d“,e);//以整型格式输出}voidInitBiTree(BiTree&T){//操作结果：构造空二叉树TT=NULL;}voidCreateBiTree(BiTree&T){//算法.：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，//构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改intnumber;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);//递归构造右子树}}voidDestroyBiTree(BiTree&T){//初始条件：二叉树T存在。操作结果：销毁二叉树Tif(T)//非空树{DestroyBiTree(T-》lchild);//递归销毁左子树，如无左子树，则不执行任何操作DestroyBiTree(T-》rchild);//递归销毁右子树，如无右子树，则不执行任何操作free(T);//释放根结点T=NULL;//空指针赋}}voidPreOrderTraverse(BiTreeT,void(*Visit)(int)){//初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法.//操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)//T不空{Visit(T-》data);//先访问根结点PreOrderTraverse(T-》lchild,Visit);//再先序遍历左子树PreOrderTraverse(T-》rchild,Visit);//最后先序遍历右子树}}voidInOrderTraverse(BiTreeT,void(*Visit)(int)){//初始条件：二叉树T存在，Visit是对结点操作的应用函数//操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T){InOrderTraverse(T-》lchild,Visit);//先中序遍历左子树Visit(T-》data);//再访问根结点InOrderTraverse(T-》rchild,Visit);//最后中序遍历右子树}}voidPostOrderTraverse(BiTreeT,void(*Visit)(int)){//初始条件：二叉树T存在，Visit是对结点操作的应用函数//操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)//T不空{PostOrderTraverse(T-》lchild,Visit);//先后序遍历左子树PostOrderTraverse(T-》rchild,Visit);//再后序遍历右子树Visit(T-》data);//最后访问根结点}}voidmain(){BiTreeT;InitBiTree(T);//初始化二叉树Tprintf(“按先序次序输入二叉树中结点的值,输入表示节点为空，输入范例：

　　“);CreateBiTree(T);//建立二叉树Tprintf(“先序递归遍历二叉树：

　　“);PreOrderTraverse(T,visit);//先序递归遍历二叉树Tprintf(“

　　中序递归遍历二叉树：

　　“);InOrderTraverse(T,visit);//中序递归遍历二叉树Tprintf(“

　　后序递归遍历二叉树：

　　“);PostOrderTraverse(T,visit);//后序递归遍历二叉树T}这样可以么？

　　求c#前中后序遍历二叉树的算法及思想

　　下面简单介绍一下几种算法和思路：先序遍历：.访问根结点.按先序遍历左子树;.按先序遍历右子树;.例如：遍历已知二叉树结果为：A-》B-》D-》G-》H-》C-》E-》F中序遍历：.按中序遍历左子树;.访问根结点;.按中序遍历右子树;.例如遍历已知二叉树的结果：B-》G-》D-》H-》A-》E-》C-》F后序遍历：.按后序遍历左子树;.按后序遍历右子树;.访问根结点;.例如遍历已知二叉树的结果：G-》H-》D-》B-》E-》F-》C-》A层次遍历：.从上到下,从左到右遍历二叉树的各个结点(实现时需要借辅助容器);.例如遍历已知二叉树的结果：A-》B-》C-》D-》E-》F-》G-》H附加代码：二叉遍历算法解决方案usingSystem;usingSystem.Collections.Generic;usingSystem.Text;namespacestructure{classProgram{二叉树结点数据结构的定义#region二叉树结点数据结构的定义//二叉树结点数据结构包括数据域,左右结点以及父结点成员;classnodes《T》{Tdata;nodes《T》Lnode,Rnode,Pnode;publicTData{set{data=value;}get{returndata;}}publiodes《T》LNode{set{Lnode=value;}get{returnLnode;}}publiodes《T》RNode{set{Rnode=value;}get{returnRnode;}}publiodes《T》PNode{set{Pnode=value;}get{returnPnode;}}publiodes(){}publiodes(Tdata){this.data=data;}}#endregion#region先序编历二叉树staticvoidPreOrder《T》(nodes《T》rootNode){if(rootNode!=null){Console.WriteLine(rootNode.Data);PreOrder《T》(rootNode.LNode);PreOrder《T》(rootNode.RNode);}}#endregion

　　计算机二级二叉树前序中序后序

　　二叉树遍历方式是数据结构的基础知识，作为计算机专业的大学生，我的理解如下：

　　它的遍历顺序是：先访问根结点，再进入这个根结点的左子树；以上述方式遍历完所有左子树后，再进入它的右子树，以同样的方式遍历右子树中的结点，即根结点→左子树→右子树。下图中为主根结点，为左子树，为右子树；在左子树中，为根结点，为左子树，为右子树；在右子树中，为根结点，为左子树，为右子树。依次将每个树中的根结点、左子树以及右子树分清，只到子树中只剩一个元素为止。综上可知，结果为→→→→→→。

　　它的遍历顺序是：先进入根结点的左子树，以同样方式遍历左子树结点，在访问当前的根结点，最后进入根结点的右子树，以同样方式遍历右子树结点，即左子树→根结点→右子树。由前序遍历中分析可知结果为→→→→→→。

　　它的遍历顺序是：先进入根结点的左子树，以同样方式遍历左子树结点，再进入根结点的右子树，以同样方式遍历右子树结点，左右子树都遍历完后，才能访问当前根结点，即左子树→右子树→根结点。由前序遍历中分析可知结果为→→→→→→。

　　试一试，二叉树例题与解答：

　　前序遍历：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“usingnamespacestd;constintmaxn=;structnode{intdata;node*lchild;node*rchild;};intn;intin;boolvis={false};vector《int》lev;node*create(vector《int》lev,intinl,intinr){if(lev.size()==)returnNULL;if(inl》inr)returnNULL;//printf(“

　　“);node*root=newnode;root-》data=lev;intk;for(k=inl;k《=inr;k++){if(lev)break;}for(intj=inl;j《=k-;j++)vis=true;vector《int》tempLeft,tempRight;//要函数体内新建for(inti=;i《lev.size();i++){if(vis==true)tempLeft.push_back(lev);elsetempRight.push_back(lev);}root-》lchild=create(tempLeft,inl,k-);root-》rchild=create(tempRight,k+,inr);returnroot;}voidpreorder(node*root){if(root==NULL)return;printf(“%d“,root-》data);preorder(root-》lchild);preorder(root-》rchild);}intmain(){scanf(“%d“,&n);intx;for(inti=;i《n;i++){scanf(“%d“,&x);lev.push_back(x);}for(intj=;j《n;j++)scanf(“%d“,∈);node*root=create(lev,,n-);preorder(root);return;}

　　二叉树遍历问题（前序，中序，后序)

　　前序遍历（DLR前序遍历也叫做先根遍历，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。若二叉树为空则结束返回，否则：（访问根结点（前序遍历左子树（前序遍历右子树注意的是：遍历左右子树时仍然采用前序遍历方法。中序遍历（LDR中序遍历也叫做中根遍历，可记做左根右。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：若二叉树为空则结束返回，否则：（中序遍历左子树（访问根结点（中序遍历右子树。注意的是：遍历左右子树时仍然采用中序遍历方法。后序遍历（LRD后序遍历也叫做后根遍历，可记做左右根。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：若二叉树为空则结束返回，否则：（后序遍历左子树。（后序遍历右子树。（访问根结点。注意的是：遍历左右子树时仍然采用后序遍历方法。如上图所示二叉树前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树遍历结果：a,b,e,f,c,g中序遍历，也叫中根遍历，顺序是左子树，根，右子树遍历结果：e,b,f,a,g,c后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根遍历结果：e,f,b,g,c,a