二叉树的递归非递归遍历详解
程序员文章站
2024-01-15 12:57:16
...
1、二叉树的递归非递归遍历详解
树的节点
#typedef char elemtype
typedef struct BTNode
{
elemtype data;
BTNode * Leftchild;
BTNode * Rightchild;
}BTNode,*BiTree;
//递归先序遍历
先序遍历顺序:根-》左子树-》右子树
void PreOrder(BTNode * root)
{
if(NULL == root)
{
return ;
}
cout<<root->data<<" ";
PreOrder(root->leftchild);
PreOrder(root->Rightchild);
}
//递归中序遍历
先序遍历顺序:左子树-》根-》右子树
void InOrder(BTNode * root)
{
if(NULL == root)
{
return ;
}
PreOrder(root->leftchild);
cout<<root->data<<" ";
PreOrder(root->Rightchild);
}
//递归后序遍历
先序遍历顺序:左子树-》右子树-》根
void PreOrder(BTNode * root)
{
if(NULL == root)
{
return ;
}
PreOrder(root->leftchild);
PreOrder(root->Rightchild);
cout<<root->data<<" ";
}
这里以先序遍历为例,画图说明
图片只画了先序遍历的一部分,按照上图一次类推,将得到完整的先序遍历结果;同理可得中序和后序遍历结果。
//非递归遍历
//非递归中序遍历
递归底层就是通过数据结构栈实现的,实现先进后出,所以非递归遍历将用到栈实现
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
1:如果当前节点存在,进栈并遍历左子树
2:否则退栈并访问数据,然后遍历右子树
void NiceInOrder(BTNode * root)
{
if(NULL == root)
{
return ;
}
BTNode* p=root;
stack<BTNode*> st;
while(!st.empty() || p!=NULL)
{
if(p!=NULL)
{
st.push(p);
p=p->Leftchild;
}
else
{
p=st.top();
st.pop();
cout<<p->data<<" ";
p=p->Rightchild;
}
}
}
//非递归先序遍历
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
1:如果当前节点存在,访问数据并进栈,再遍历左子树
2:否则退栈,然后遍历右子树
void NicePreOrder(BTNode* root)
{
if(NULL == root)
{
return ;
}
BTNode* p=root;
stack<BTNode*> st;
while(p!=NULL || !st.empty())
{
if(p!=NULL)
{
cout<<p->data<<" ";
st.push(p);
p=p->Leftchild;
}
else
{
p=st.top();
st.pop();
p=p->Rightchild
}
}
}
//非递归后序遍历
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
1:如果当前节点开始,进栈并遍历左子树,直到左子树为空
2:如果栈顶元素的右子树为空,或者栈顶节点的右孩子为刚访问过得节点,则退栈并访问
3:否则,遍历右子树
void NicePostOrder(BTNode* root)
{
if(NULL == root)
{
return ;
}
BTNode* p=root;
BTNode* q=NULL:
stack<BTNode*> st;
while(p!=NULL || !st.empty())
{
if(p!=NULL)
{
st.push(p);
p=p->Leftchild;
}
else
{
p=st.top();
if(p->Rightchild==NULL || p->Rightchild==q)
{
cout<<p->data<<" ";
st.pop();
q=p;
p=NULL;
}
else
{
p=p->Rightchild;
}
}
}
}
这里以非递归先序遍历为图解,解释程序执行过程
中序遍历只是在每次出栈的时候访问数据,过程相似
后序遍历需要主要的是需要用一个标志q来标记节点是否访问过,每次访问过p要置为NULL,否则就会陷入死循环。代码是下面这一段
if(p->Rightchild==NULL || p->Rightchild==q)
{
cout<<p->data<<" ";
st.pop();
q=p;
p=NULL;
}
好了,到此处二叉树的三种遍历就全部说完了,之后会介绍二叉树的其他操作!
推荐阅读
-
二叉树的递归非递归遍历详解
-
【c++】c++模板类,实现二叉树非递归遍历
-
二叉树模板 先中后序遍历,非递归算法,层次遍历,叶子结点数,深度
-
二叉树的非递归遍历模板
-
优雅的二叉树非递归遍历模板
-
php+mysql不用递归实现的无限级分类实例(非递归),mysql递归
-
【LeetCode】104. Maximum Depth of Binary Tree 二叉树的深度 DFS BFS 递归方式 迭代方式 JAVA
-
php实例分享之通过递归实现删除目录下的所有文件详解_php实例
-
php+mysql不用递归实现的无限级分类实例(非递归)_php实例
-
PHP递归遍历指定目录的文件并统计文件数量的方法_PHP教程