二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现
二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[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;
}
二叉树先、中、后序的简单理解
答：(3)中序遍历：ba 后序遍历：ab 由后序遍历序列可知b为e的右子树的根结点。由中序遍历序列中可看出，a为根结点b的右子结点。树的结构如下：例子2：已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是（gdbehfca）。(1)先序遍历：abdgcefh 中序遍历：dgbaechf 先序...
二叉树的前序,中序,后序
答：对于例题的后序遍历的答案是，gdbehfca.解答过程：1）定义解释：树的遍历的三种情况，是根据左子树、右子树、根这3者的不同访问次序来定义的。根左右（根先访问），则为先序遍历；左根右，则为中序遍历；左右根，则为后序遍历。2）已知先序和中序遍历结果，求树的结构和后序遍历结果：先序遍历...
二叉树的后序序列是什么?
答：详解为：前序序列的顺序是根、左、右，序列ABCD第一个一定是根结点，A是根节点。中序序列顺序是左、根、右，因为A是根节点，所以DCB位于A左侧，A右侧没有结点，B是DCB三个结点中的根。前序序列是中左右，根结点为A；中序序列是左中右，左子树BCD；遵循遍历序列的规则排列出二叉树，得出后序...
二叉树中,什么是前序,中序。后序!
答：2、若在左右子树的后面被访问叫做后序，其顺序为左右根 3、特点为后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点 二叉树是数据结构中常被问到的相关知识点，也是需要了解的一个知识点，可以总结一下二叉树的前序、中序、后序遍历的...
什么是二叉树的先序、中序和后序?
答：先序，中序，后序，是按照访问根的先后顺序来定义的。先序是“根左右”，中序是“左根右”，后序是“左右根”。ABC，如果是先序，A是根，B是左叶，C是右叶;ABC如果是中序，A是左叶，B是根，C是右叶。先序序列ABDEFCGHIJK，说明A是这个树的总根;中序EFDBCGAJIKH，说明E是最底层最左边的...
建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法都需要...
答：//===LRN 后序遍历=== void Postorder(BinTree T){ if(T) { Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf("%c",T->data); //访问结点 } } //===采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=== int TreeDepth(...
二叉树的前序遍历、中序遍历、后序遍历有什么口诀吗
答：解：第一步：根据前序遍历第一个节点为根节点得知，A为根 第二步：根据中序DBEAC得知，A前面的是左子树，说明 DBE在 A左侧，C在右侧，目前可以得出AC的位置 第三步：根据剩下的前序 BDEC 得知，B为根 第四步：根据剩下的中序 DBE 得知，D在B左侧，E在B右侧，所以可以画出整个二叉树图 本文...
已知二叉树的中序序列,后序序列,怎么求前序序列
答：确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。递归求解树。将左子树和右...
怎么根据二叉树的前序,中序,确定它的后序
答：怎么根据二叉树的前序，中序，确定它的后序 二叉树遍历分为三类：前序遍历，中序遍历和后序遍历。前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树；并且在遍历左，右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树；...
计算机,数据结构,二叉树的遍历,先序遍历,后序遍历,中序遍历,急急急急...
答：中序遍历为ABCD,前序遍历序列为CABD 前序遍历先访问根，所以C为根，在中序遍历中先访问左子树，再访问根，最后访问右子树，所以在中序序列中，C前面的为左子树，第二个访问的是左子树的根A以此类推可得这样的一棵二叉树：C / \ A D \ B 对这棵二叉树后序遍历可得后序序列为BADC ...
