在线客服:
亚博直播 亚博直播
全国服务热线:010-34915482
您的位置:首页 > 新闻中心 >

二叉树的非递归遍历

浏览 100次 来源:【jake推荐】 作者:-=Jake=-    时间:2021-01-20 02:01:12
[摘要] 二叉树的非递归遍历对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现。递归实现非递归实现中序遍历递归实现非递归实现后序遍历递归实现非递归实现

二叉树的非递归遍历

二叉树是非常重要的数据结构,许多其他数据结构都基于二叉树的演变。对于二叉树,有三种遍历方法:前序,中序和后序。因为树定义本身是递归定义,所以使用递归方法不仅容易理解树的三个遍历,而且代码也非常简洁。如果将非递归方法用于树遍历,则必须使用堆栈来模拟实现。在这三种遍历中,前递阶和中阶遍历的非递归算法易于实现,而后递归的非递归遍历则相对困难。

一.遍历

按照“根节点-左子右子”的顺序访问预遍历。

1.递归实现

void preOrder1(BinTree *root)     //递归前序遍历 
{
if(root!=NULL)
{
cout
<<root->data<<"";
preOrder1(root
->lchild);
preOrder1(root
->rchild);
}
}

2.非递归实现

根据以前的遍历访问的顺序,首先访问根节点,然后分别访问左子节点和右子节点。也就是说,对于任何节点,都可以将其视为根节点,因此可以直接对其进行访问。访问后亚博电竞 ,如果其左子节点不为空,则将按照相同规则访问其左子树;否则,将访问左子树。当访问其左子树时,然后访问其右子树。因此,处理过程如下:

对于任何节点P:

1)访问节点P并将节点P推入堆栈;

2)确定节点P的左子节点是否为空,如果为空,则取栈顶节点并执行弹出操作,并将栈顶节点的右子节点设置为当前节点P,循环到1);如果不为空,则将P的左子节点设置为当前节点P;

3)直到P为NULL并且堆栈为空,遍历才结束。

void preOrder2(BinTree *root)     //非递归前序遍历 
{
stack
<BinTree*> s;
BinTree
*p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout
<<p->data<<"";
s.push(p);
p
=p->lchild;
}
if(!s.empty())
{
p
=s.top();
s.pop();
p
=p->rchild;
}
}
}

二.按顺序遍历

按“左子-根-右子”的顺序访问中间顺序。

1.递归实现

void inOrder1(BinTree *root)      //递归中序遍历
{
if(root!=NULL)
{
inOrder1(root
->lchild);
cout
<<root->data<<"";
inOrder1(root
->rchild);
}
}

2.非递归实现

根据中间顺序遍历的顺序,对于任何节点二叉树遍历非递归,首先访问左子节点凤凰体育 ,然后将左子节点视为一个节点,然后继续访问其左子节点,直到遇到左子节点为止child可以访问为空的节点二叉树遍历非递归,然后根据相同的规则访问右边的子树。因此,处理过程如下:

对于任何节点P亚博app

1)如果其左子节点不为空,则将P放在堆栈上,并将P的左子节点设置为当前P,然后在当前节点P上执行相同的处理;

2)如果其左子元素为空,则取栈的顶部元素并执行弹出操作YABO88 ,访问栈的顶部节点,然后将当前P设置为栈顶节点的右侧子元素堆栈;

3)遍历结束,直到P为NULL并且堆栈为空

void inOrder2(BinTree *root)      //非递归中序遍历
{
stack
<BinTree*> s;
BinTree
*p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p
=p->lchild;
}
if(!s.empty())
{
p
=s.top();
cout
<<p->data<<"";
s.pop();
p
=p->rchild;
}
}
}

三.后遍历

以“左子右子根节点”的顺序访问后遍历。

1.递归实现

void postOrder1(BinTree *root)    //递归后序遍历
{
if(root!=NULL)
{
postOrder1(root
->lchild);
postOrder1(root
->rchild);
cout
<<root->data<<"";
}
}

2.非递归实现

后遍历的非递归实现是三种遍历方法中最困难的。因为在后遍历中,必须确保左孩子和右孩子都已被访问,并且在右孩子可以访问根节点之前确保左孩子访问,这给过程控制带来了困难。下面介绍两个想法。

第一个想法:对于任何节点P,将其放在堆栈上,然后向下搜索其左子树,直到找到没有左子节点的节点,并且该节点出现在堆栈的顶部,但是不能从堆栈中弹出并在此时访问,因此仍可以访问其正确的子级。因此,按照相同的规则以相同的方式处理右子树。当访问正确的孩子时,该节点再次出现在堆栈的顶部。此时,可以弹出并访问它。这样可以确保正确的访问顺序。可以看出,在此过程中,每个节点两次出现在堆栈顶部,并且只有在第二次出现在堆栈顶部时才可以访问。因此,还需要设置一个变量来标识节点是否是第一次出现在堆栈顶部。

void postOrder2(BinTree *root)    //非递归后序遍历
{
stack
<BTNode*> s;
BinTree
*p=root;
BTNode
*temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索,直至出现没有左子树的结点
{
BTNode
*btn=(BTNode *)malloc(sizeof(BTNode));
btn
->btnode=p;
btn
->isFirst=true;
s.push(btn);
p
=p->lchild;
}
if(!s.empty())
{
temp
=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp
->isFirst=false;
s.push(temp);
p
=temp->btnode->rchild;
}
else//第二次出现在栈顶
{
cout
<<temp->btnode->data<<"";
p
=NULL;
}
}
}
}

第二个想法:确保仅在左子节点和右子节点访问之后才能访问根节点,因此对于任何节点P,都应首先将其放在堆栈中。如果P没有左孩子或右孩子,则可以直接访问它。或者如果P有一个左孩子或一个右孩子,但已经访问了它的左孩子和右孩子,则也可以直接访问该节点。如果不是以上两种情况,则将P的右子元素和左子元素依次放在栈上,以确保每次获取栈顶元素时,先访问左子元素,再访问右子元素。子节点,左子节点和右子节点都在根节点上。之前要参观的地点。

void postOrder3(BinTree *root)     //非递归后序遍历
{
stack
<BinTree*> s;
BinTree
*cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur
=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre
!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout
<<cur->data<<""; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre
=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur
->rchild);
if(cur->lchild!=NULL)
s.push(cur
->lchild);
}
}
}

四.整个程序的完整代码

/*二叉树的遍历* 2011.8.25*/ 

#include
<iostream>
#include
<string.h>
#include
<stack>
usingnamespace std;

typedef
struct node
{
char data;
struct node *lchild,*rchild;
}BinTree;

typedef
struct node1
{
BinTree
*btnode;
bool isFirst;
}BTNode;


void creatBinTree(char*s,BinTree *&root) //创建二叉树,s为形如A(B,C(D,E))形式的字符串
{
int i;
bool isRight=false;
stack
<BinTree*> s1; //存放结点
stack<char> s2; //存放分隔符
BinTree *p,*temp;
root
->data=s[0];
root
->lchild=NULL;
root
->rchild=NULL;
s1.push(root);
i
=1;
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight
=false;
}
elseif(s[i]==',')
{
isRight
=true;
}
elseif(s[i]==')')
{
s1.pop();
s2.pop();
}
elseif(isalpha(s[i]))
{
p
=(BinTree *)malloc(sizeof(BinTree));
p
->data=s[i];
p
->lchild=NULL;
p
->rchild=NULL;
temp
=s1.top();
if(isRight==true)
{
temp
->rchild=p;
cout
<<temp->data<<"的右孩子是"<<s[i]<<endl;
}
else
{
temp
->lchild=p;
cout
<<temp->data<<"的左孩子是"<<s[i]<<endl;
}
if(s[i+1]=='(')
s1.push(p);
}
i
++;
}
}

void display(BinTree *root) //显示树形结构
{
if(root!=NULL)
{
cout
<<root->data;
if(root->lchild!=NULL)
{
cout
<<'(';
display(root
->lchild);
}
if(root->rchild!=NULL)
{
cout
<<',';
display(root
->rchild);
cout
<<')';
}
}
}

void preOrder1(BinTree *root) //递归前序遍历
{
if(root!=NULL)
{
cout
<<root->data<<"";
preOrder1(root
->lchild);
preOrder1(root
->rchild);
}
}

void inOrder1(BinTree *root) //递归中序遍历
{
if(root!=NULL)
{
inOrder1(root
->lchild);
cout
<<root->data<<"";
inOrder1(root
->rchild);
}
}

void postOrder1(BinTree *root) //递归后序遍历
{
if(root!=NULL)
{
postOrder1(root
->lchild);
postOrder1(root
->rchild);
cout
<<root->data<<"";
}
}

void preOrder2(BinTree *root) //非递归前序遍历
{
stack
<BinTree*> s;
BinTree
*p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout
<<p->data<<"";
s.push(p);
p
=p->lchild;
}
if(!s.empty())
{
p
=s.top();
s.pop();
p
=p->rchild;
}
}
}

void inOrder2(BinTree *root) //非递归中序遍历
{
stack
<BinTree*> s;
BinTree
*p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p
=p->lchild;
}
if(!s.empty())
{
p
=s.top();
cout
<<p->data<<"";
s.pop();
p
=p->rchild;
}
}
}

void postOrder2(BinTree *root) //非递归后序遍历
{
stack
<BTNode*> s;
BinTree
*p=root;
BTNode
*temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索,直至出现没有左子树的结点
{
BTNode
*btn=(BTNode *)malloc(sizeof(BTNode));
btn
->btnode=p;
btn
->isFirst=true;
s.push(btn);
p
=p->lchild;
}
if(!s.empty())
{
temp
=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp
->isFirst=false;
s.push(temp);
p
=temp->btnode->rchild;
}
else//第二次出现在栈顶
{
cout
<<temp->btnode->data<<"";
p
=NULL;
}
}
}
}

void postOrder3(BinTree *root) //非递归后序遍历
{
stack
<BinTree*> s;
BinTree
*cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur
=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre
!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout
<<cur->data<<""; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre
=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur
->rchild);
if(cur->lchild!=NULL)
s.push(cur
->lchild);
}
}
}


int main(int argc, char*argv[])
{
char s[100];
while(scanf("%s",s)==1)
{
BinTree
*root=(BinTree *)malloc(sizeof(BinTree));
creatBinTree(s,root);
display(root);
cout
<<endl;
preOrder2(root);
cout
<<endl;
inOrder2(root);
cout
<<endl;
postOrder2(root);
cout
<<endl;
postOrder3(root);
cout
<<endl;
}
return0;
}

老王
本文标签:递归,中序遍历,前序遍历

推荐阅读

最新评论