二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现
二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[cpp] view plaincopy
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储：
[csharp] view plaincopy
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
二叉树三种递归的遍历方法：
先序遍历访问根节点→先序遍历左子树→先序遍历右子树
中序遍历中序遍历左子树→访问根节点→中序遍历右子树
后序遍历后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法：
[cpp] view plaincopy
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法：
有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历：
[cpp] view plaincopy
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历：
[cpp] view plaincopy
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历：
[cpp] view plaincopy
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法：（用队列的方法）
[cpp] view plaincopy
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}
已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）
[cpp] view plaincopy
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]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
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();
}
#include using namespace std;//二叉树链式存储的头文件 typedef char datatype;//结点属性值类型 typedef struct node // 二叉树结点类型 { datatype data; struct node* lchild,*rchild; }bintnode; typedef bintnode *bintree; bintree root;//指向二叉树结点指针 //下面是些栈的操作 为非递归实现做准备 typedef struct stack//栈结构定义 { bintree data[100];//data元素类型为指针 int tag[100];//为栈中元素做的标记，，用于后续遍历 int top;//栈顶指针 }seqstack; void push(seqstack *s,bintree t)//进栈 { s->data[++s->top]=t; } bintree pop(seqstack *s) //出栈 { if(s->top!=-1) {s->top--; return(s->data[s->top+1]); } else return NULL; } //按照前序遍历顺序建立一棵给定的二叉树 void createbintree(bintree *t) { char ch; if((ch=getchar())== '-') *t=NULL; else { *t=(bintnode*)malloc(sizeof(bintnode));//产生二叉树根结点 (*t)->data=ch; createbintree(&(*t)->lchild);//递归实现左孩子的建立 createbintree(&(*t)->rchild);//递归实现右孩子的建立 } } //二叉树前序遍历递归实现 void preorder(bintree t)//t是指针变量，而不是结点结构体变量 {if(t) { coutdatalchild); preorder(t->rchild); } } //二叉树前序遍历非递归实现 void preorder1(bintree t) { seqstack s; s.top=-1;//top 的初始值为-1； while((t)||(s.top!=-1))//当前处理的子树不为空或者栈不为空，则循环 { while(t) { coutdatalchild; } if(s.top>-1) { t=pop(&s);//当前子树根结点出栈 t=t->rchild;//访问其右孩子 } } } //二叉树中序遍历递归算法 void inorder(bintree t) { if(t) { inorder(t->lchild); coutdatarchild); } } // 二叉树中序遍历非递归算法 void inorder1(bintree t) { seqstack s; s.top=-1; while((t!=NULL)||(s.top!=-1)) { while(t) { push(&s,t); t=t->lchild;//子树跟结点全部进栈 } if(s.top!=-1) { t=pop(&s); coutdatarchild;//进入右孩子访问 } } } //后续递归遍历二叉树 void postorder(bintree t) { if(t) { postorder(t->lchild); postorder(t->rchild); coutdatalchild;//进入左子树访问。（左子树根结点全部进栈） } while((s.top>-1)&&(s.tag[s.top]==1)) { t=s.data[s.top]; coutdata-1) { t=s.data[s.top]; s.tag[s.top]=1;//进入右孩子前，标志tag变为1； t=t->rchild;//进入右孩子 } else t=NULL; } } int main() { bintree tree; cout<<"输入根结点：" ; createbintree(&tree); cout<<"
前序递归遍历二叉树；"; preorder(tree); cout<<"
前序非递归遍历二叉树："; preorder1(tree); cout<<"
-------------------------------
"; cout<<"
中序遍历递归二叉树；"; inorder(tree); cout<<"
中序非递归遍历二叉树："; inorder1(tree); cout<<"
----------------------------
"; cout<<"
后序递归遍历二叉树："; postorder(tree); cout<<"
后序非递归遍历二叉树："; postorder1(tree); cout<<endl; }
using namespace std;//二叉树链式存储的头文件
typedef char datatype;//结点属性值类型
typedef struct node // 二叉树结点类型
{
datatype data;
struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;//指向二叉树结点指针
//下面是些栈的操作 为非递归实现做准备
typedef struct stack//栈结构定义
{
bintree data[100];//data元素类型为指针
int tag[100];//为栈中元素做的标记，，用于后续遍历
int top;//栈顶指针
}seqstack;
void push(seqstack *s,bintree t)//进栈
{
s->data[++s->top]=t;
}
bintree pop(seqstack *s) //出栈
{
if(s->top!=-1)
{s->top--;
return(s->data[s->top+1]);
}
else
return NULL;
}
//按照前序遍历顺序建立一棵给定的二叉树
void createbintree(bintree *t)
{
char ch;
if((ch=getchar())== '-')
*t=NULL;
else
{
*t=(bintnode*)malloc(sizeof(bintnode));//产生二叉树根结点
(*t)->data=ch;
createbintree(&(*t)->lchild);//递归实现左孩子的建立
createbintree(&(*t)->rchild);//递归实现右孩子的建立
}
}
//二叉树前序遍历递归实现
void preorder(bintree t)//t是指针变量，而不是结点结构体变量
{if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//二叉树前序遍历非递归实现
void preorder1(bintree t)
{
seqstack s;
s.top=-1;//top 的初始值为-1；
while((t)||(s.top!=-1))//当前处理的子树不为空或者栈不为空，则循环
{
while(t)
{
cout<<t->data<<" ";//访问当前子树根结点
s.top++;
s.data[s.top]=t;
t=t->lchild;
}
if(s.top>-1)
{
t=pop(&s);//当前子树根结点出栈
t=t->rchild;//访问其右孩子
}
}
}
//二叉树中序遍历递归算法
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
// 二叉树中序遍历非递归算法
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL)||(s.top!=-1))
{
while(t)
{
push(&s,t);
t=t->lchild;//子树跟结点全部进栈
}
if(s.top!=-1)
{
t=pop(&s);
cout<<t->data<<" ";//输出跟结点，其实也就是左孩子或者有孩子（没有孩子的结点是他父亲的左孩子或者有孩子）
t=t->rchild;//进入右孩子访问
}
}
}
//后续递归遍历二叉树
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
};
//后序遍历 非递归实现
void postorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t)||(s.top!=-1))
{
while(t)
{
s.top++;
s.data[s.top]=t;//子树根结点进栈
s.tag[s.top]=0;//设此根结点标志初始化为0，表示左右孩子都么有访问，当访问完左子树，tag变为1；
t=t->lchild;//进入左子树访问。（左子树根结点全部进栈）
}
while((s.top>-1)&&(s.tag[s.top]==1))
{
t=s.data[s.top];
cout<<t->data<<" ";//没有孩子的根结点，也就是它父亲的左孩子或者右孩子
s.top--;
}
if(s.top>-1)
{
t=s.data[s.top];
s.tag[s.top]=1;//进入右孩子前，标志tag变为1；
t=t->rchild;//进入右孩子
}
else
t=NULL;
}
}
int main()
{
bintree tree;
cout<<"输入根结点：" ;
createbintree(&tree);
cout<<"\n 前序递归遍历二叉树；";
preorder(tree);
cout<<"\n 前序非递归遍历二叉树：";
preorder1(tree);
cout<<"\n-------------------------------\n";
cout<<"\n 中序遍历递归二叉树；";
inorder(tree);
cout<<"\n 中序非递归遍历二叉树：";
inorder1(tree);
cout<<"\n----------------------------\n";
cout<<"\n 后序递归遍历二叉树：";
postorder(tree);
cout<<"\n 后序非递归遍历二叉树：";
postorder1(tree);
cout<<endl;
}
二叉树的前序中序后序怎么看
二叉树的前序中序后序看法如下：先序遍历（先根遍历）：先访问根节点，然后访问左子树，最后访问右子树。例如，对于二叉树1一2一3一4一5，先序遍历的结果为1一2一3一4一5。中序遍历（中根遍历）：先访问左子树，然后访问根节点，最后访问右子树。例如，对于二叉树1一2一3一4一5，中序遍历的...
二叉树中,什么是前序,中序。后序!
2、若在左右子树的后面被访问叫做后序，其顺序为左右根 3、特点为后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点 二叉树是数据结构中常被问到的相关知识点，也是需要了解的一个知识点，可以总结一下二叉树的前序、中序、后序遍历...
二叉树中序序列和前序序列有什么不同?
详解为：前序序列的顺序是根、左、右，序列ABCD第一个一定是根结点，A是根节点。中序序列顺序是左、根、右，因为A是根节点，所以DCB位于A左侧，A右侧没有结点，B是DCB三个结点中的根。前序序列是中左右，根结点为A；中序序列是左中右，左子树BCD；遵循遍历序列的规则排列出二叉树，得出后序...
先序遍历、中序遍历、后序遍历之间有何关系?
后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。在二叉树中，求后...
二叉树前序中序后序
二叉树前序中序后序 前序遍历 前序遍历是三种遍历顺序中最简单的一种，因为根节点是最先访问的，而我们在访问一个树的时候最先遇到的就是根节点。递归法 递归的方法很容易实现，也很容易理解：我们先访问根节点，然后递归访问左子树，再递归访问右子树，即实现了根->左->右的访问顺序，因为使用的...
二叉树中什么是前序、中序、后序?
其实这个顺序就是表示根节点所在的位置，左子树和右子树的顺序是固定的，都是先左后右。所以根结点与左右子树的关系就构成了三种顺序：1. 若在左右子树的前面被访问叫做前序，其顺序为根左右 2. 若在左右子树的中间被访问叫做中序，其顺序为左根右 3. 若在左右子树的后面被访问叫做后序，其顺序为...
二叉树的先序、中序、后序是如何确定的?
1、根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树，G右侧的HMZ必然是root的右子树。3、观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的rot的lefichild...
怎么根据二叉树的前序,中序,确定它的后序
怎么根据二叉树的前序，中序，确定它的后序 二叉树遍历分为三类：前序遍历，中序遍历和后序遍历。前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树；并且在遍历左，右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树；...
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉...
【答案】：B B。【解析】二叉树的遍历有3种：前序、中序和后序。后序遍历首先遍历左子树或左子结点，然后遍历右子树或右子结点，最后访问根结点；中序遍历首先遍历左子树或左子结点，然后访问根结点，最后遍历右子树或右子结点；后序遍历首先访问根结点，然后遍历左子树或左子结点，最后遍历右子树或...
数据结构二叉树前序、中序、后续?
又由于中序遍历左根右为8 6，可知8为根节点6的左子树 因此该子树根节点为6，左子树为8，无右子树 如果按你说的右为8，那么其中序遍历应为6 8而不是8 6 总之先通过前序遍历可以确定根节点，再通过中序遍历才能确定左右子树 一定要两者结合才能得到二叉树的完整结构，不能只看其中之一 码字不易...
易寒消可： #include<iostream.h> #include<stdlib.h>typedef char ElemType;struct BTreeNode {ElemType data;BTreeNode*left;BTreeNode*right; };void InitBTree(BTreeNode*& BT) {BT=NULL; } void CreateBTree(BTreeNode*& BT,char*a) {const int ...
忻城县18264816011： 求二叉树的遍历算法 - ？
易寒消可： 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...
忻城县18264816011： .二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现. - ？
易寒消可： #include using namespace std;//二叉树链式存储的头文件 typedef char datatype;//结点属性值类型 typedef struct node // 二叉树结点类型 { datatype data; struct node* lchild,*rchild; }bintnode; typedef bintnode *bintree; bintree root;//指向二叉树...
忻城县18264816011： 二叉树的中序、前序、后序的递归、非递归遍历算法,应包含建树的实现 - ？
易寒消可： #include ＂stdlib.h＂#include ＂iostream＂ using namespace std;#define ok 1#define null 0 typedef char telemtype; typedef struct bitnode {telemtype data;<br> struct bitnode *lchild,*rchild;<br> }bitnode,*bitree;/* void visit(bitnode *p) {printf(＂%c＂,...
忻城县18264816011： 设计一个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 // 清空二...
忻城县18264816011： 建立一棵二叉树,要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历. - ？
易寒消可： 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码.Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf(＂%d ＂,T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...
忻城县18264816011： 二叉数的前序、中序、后续三种方式的递归与非递归的算法. - ？
易寒消可： 小哥分这么少=============tree.cpp=============#include<iostream>#include<queue>#include<stack>#include<fstream> using namespace std;#include＂tree.h＂//构造二叉树 template<class T> bool bitree<T>::insert(const T& e) { btnode<T...
忻城县18264816011： C语言版数据结构 如何理解二叉树的前、中、后序的递归和非递归遍历?? - ？
易寒消可： 就我看来递归遍历是很容易理解的,除非你不懂C语言递归,难理解的也就是后序非递归遍历.分2步,1、理解前中后遍历流程;2、看算法,回味遍历流程.
忻城县18264816011： 二叉树前序遍历与中序遍历非递归程序思路怎么是一样的? - ？
易寒消可： 大体思路差不多,但节点访问位置不一样, 先序的话,是先访问,然后节点压栈,移到左子树,至节点空退栈,移到右子树. 而中序的话,是先节点压栈,移到左子树,至节点空退栈,访问节点,然后移到右子树另外,所谓前序、中序、后序遍历,全称是前根序遍历,中根序遍历,后根序遍历,不管哪种遍历,访问左子树 一定在 访问右子树之前,不同的就是根的访问时机.所以三种递归/或非递归,程序思路都是一样的.
忻城县18264816011： 二叉树遍历,递归与非递归,前序中序后序遍历,C代码 - ？
易寒消可： #include<stdio.h> #include<stdlib.h> typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }bitnode,*bitree;//二叉树节点类型和节点指针类型 bitree create()//先序创建 { bitree root=NULL; char c; scanf(＂%c＂,&c); fflush(stdin); if(c=='#')...
