二叉树遍历:前序,中序,后序,层序的递归以及非递归实现
树,是一种在实际编程中经常遇到的数据结构,它的逻辑很简单:除根节点之外每个节点都有且只有一个父节点,除叶子节点之外所有节点都有一个或多个子节点。我们说的二叉树,就是指子节点最多2个的树。
二叉树中,最重要的操作就是遍历。二叉树的遍历分为:
1.前序遍历:先访问根节点,再访问左子节点,最后访问右子节点。
2.中序遍历:先访问左子节点,再访问根节点,最后访问右子节点。
3.后序遍历:先访问左子节点,再访问右子节点,最后访问根节点。
4.层序遍历:也就是我们说的“广度优先”或者“宽度优先”遍历。先访问第一层节点,再访问第二层...直到最后一层。每一层的访问顺序都是从左到右。
在本文中,将写出二叉树的前中后序遍历的递归实现以及非递归实现,还有层序遍历的实现。
首先,我们给出二叉树的定义。
typedef struct BinaryTree
{
int _data;
struct BinaryTree * _lchild;
struct BinaryTree * _rchild;
}Tree,*pTree;
可以看到,一个树中节点结构包括值域,左孩子节点和右孩子节点。叶子节点的左右孩子为空。
然后是三种遍历的递归实现。
- 前序遍历的递归实现
void PreOrderRecursion(pTree node)
{
if(node == nullptr) return;
cout<<node->_data<<" ";
PreOrderRecursion(node->_lchild);
PreOrderRecursion(node->_rchild);
}
从根节点开始,先打印出根节点的值,再递归左子树,最后递归右子树。
中序、后序遍历的思想和前序一样,只需要调整打印的顺序即可,所以下面不再赘述。
void InOrderRecursion(pTree node)
{
if(node == nullptr) return;
InOrderRecursion(node->_lchild);
cout << node->_data<<" ";
InOrderRecursion(node->_rchild);
}
void PostOrderRecursion(pTree node)
{
if(node == nullptr) return;
PostOrderRecursion(node->_lchild);
PostOrderRecursion(node->_rchild);
cout << node->_data<<" ";
}
接下来是三种遍历的非递归实现。我们说到其实递归的本质就是栈,既然不使用递归,那么我们就要用到栈。
其中,前序遍历和中序遍历的思想也十分相似,只是后序遍历有些许不同。
此处前序遍历的非递归有两种实现,思想有些许不同。
前序遍历的非递归实现方法1:
思想:使用栈,首先判断输入合法性。随后将头节点首先入栈 ,保证栈中开始至少有一个元素。使用一个while循环,只要栈还非空就一直进行。循环体中首先获取栈顶节点,将其打印后直接出栈,并将其的右孩子和左孩子依次入栈(如果存在的话)。根据栈的FILO特性,最后入栈的左孩子将在下一轮中成为栈顶元素。这样就能满足前序遍历的特点。
void PreOrderIteration1(pTree node)
{
if(node == nullptr) return;
stack<pTree> s;
pTree p = node;
s.push(p);
while(!s.empty())
{
p = s.top();
cout<<p->_data<<" ";
s.pop();
if(p->_rchild) s.push(p->_rchild);
if(p->_lchild) s.push(p->_lchild);
}
}
前序遍历非递归实现方法2:
思想:循环开始,从栈顶节点(除第一次是根节点)开始不断左探,入栈并打印,直到左孩子为空;然后指针指向栈顶元素的右孩子,开启下一轮循环。
void PreOrderIteration2(pTree node)
{
stack<pTree> s;
pTree p = node;
while(!s.empty() || p != nullptr)
{
while(p != nullptr) //不断左探的过程
{
cout<< p->_data << " ";
s.push(p);
p = p->_lchild;
}
if(!s.empty()) //最后访问右孩子
{
p = s.top();
s.pop();
p = p->_rchild;
}
}
}
总地来说,还是第一种方法更好理解也便于记忆。
中序遍历非递归实现:
思想:与前序遍历非递归方法2的思想相同,只是不在不断左探的时候打印,而是在出栈的时候打印。
void InOrderIteration(pTree node)
{
if (node == nullptr) return;
pTree p = node;
stack<pTree> s;
while(!s.empty() || p != nullptr)
{
while(p != nullptr)
{
s.push(p);
p = p->_lchild;
}
if(!s.empty())
{
p = s.top();
cout << p->_data <<" ";
s.pop();
p = p->_rchild;
}
}
}
后序遍历非递归实现:
思想:相对于前序和中序,后续遍历的实现就稍显麻烦。我们要保证一个节点要在左孩子和右孩子之后才能访问,那么有下面三种情况:
1.它是叶子节点,没有左右孩子。可以直接访问。
2.它有左右孩子,但是左右孩子都已经被访问过,也可以直接访问该节点。
3.有左右孩子,且左右孩子没有访问过。此时要先入栈右孩子,再入栈左孩子。
为了确认一个节点的左右孩子是否被访问过,我们就要定义一个pPre指针。访问过一个节点后,就将pPre指向它,在下一轮判断就可以通过p->lchild || p->rchild == pPre来作为子节点是否被访问过的条件了。
void PostOrderIteration(pTree node)
{
pTree pCur = node; //用来保存当前节点的指针
pTree pPre = nullptr; //保存上一个访问的节点的指针
stack<pTree> s;
s.push(pCur);
while(s.!empty())
{
pCur = s.top();
if((pCur->_lchild == nullptr && pCur->_rchild == nullptr) || //没有左右孩子的情况
(pPre != nullptr && (pPre == pCur->_lchild || pPre == pCur->_rchild))) //左右孩子访问过的情况
{
cout << pCur->_data << " ";
s.pop();
pPre = pCur;
}
else
{
if(pCur->_rchild != nullptr) s.push(pCur->_rchild);
if(pCur->_lchild != nullptr) s.push(pCur->_lchild);
}
}
}
最后是层序遍历。和其他三种遍历不同的是,层序遍历使用队列来实现。先进先出也很符合层序遍历的特点。
void LevelOrder(pTree node)
{
pTree p = node;
if(node == nullptr) return;
queue<pTree> q;
for(q.push(p);q.size();q.pop()) //只要队列不空就一直出队
{
p = q.front();
cout << p->_data <<" ";
if(p->_lchild) q.push(p->_lchild);
if(p->_rchild) q.push(p->_rchild);
}
}
上一篇: 二叉树前序中序后序遍历(递归和非递归)以及层序遍历代码
下一篇: 树莓派,运行python+opencv+pyqt5编写的程序报错[g_object_new_with_properties: assertion ‘G_TYPE_IS_OBJECT (object_]
推荐阅读
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
C二叉树前序遍历中序遍历后续遍历递归非递归
-
二叉树遍历 前序遍历 后序遍历 中序遍历 非递归前序遍历 二叉树遍历非递归
-
【LeetCode】二叉树各种遍历大汇总(秒杀前序、中序、后序、层序)递归 & 迭代
-
python实现二叉树的层序、前序、中序、后序、之字形遍历
-
左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(Java版)
-
二叉树的定义 以及前中后序,层序遍历