按照阅读递归算法的方法模拟执行中序遍历是什么意思

来源：蜘蛛抓取(WebSpider) 时间：2020-04-18 11:06 标签：

用递归和非递归的方式分别按照二叉树先序、中序和后序打印所有的节点。约定：先序遍历顺序为跟、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根 

 

 
 
 

 
 
 

 
 
 
 

 
 

 
 

   第一步：申请一个新的栈，记为stack然后将头节点head压入stack中。
 
 

   第二步：从stack中弹出栈顶节点记为cur，然后打印cur节点的值再将节点cur的右孩子節点（不为空的话）先压入stack中，最后将cur的左孩子节点（不为空的话）压入stack中
 
 

   第三步：不断重复第二步，直到stack为空全部过程结束。
 
 

 
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 

 

 
 

 
 

   第一步：申请一个新的栈记为stack。初始时令变量cur=head。
 
 

   第二步：先把cur节点压入栈中对以cur节点为头节点的整棵子树来说，依次把左边界压入栈中即不停地令cur=cur->left，然后重复第二步
 
 

   第三步：不断重复第二步，直到发现cur为空此时从stack中弹出一个节点，记为node打印node的值，并且让cur=node->right然后继續步骤2。
 
 

   第四步：当stack为空且cur为空时整个过程停止。
 
 

 
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 
 

 
 

 
 

 
 

 第一步：申请一个栈记为s1，然后将头节点haea压入s1中
 
 

 第二步：从s1中弹出的节点记为cur，嘫后依次将cur的左孩子节点和右孩子节点压入s1中
 
 

 第三步：在整个过程中，每一个从s1中弹出的节点都放进s2中
 
 

 第四步：不断重复第二步和第彡步，直到s1为空过程停止。
 
 

 第五步：从s2中依次弹出节点并打印打印的顺序就是后续遍历的顺序。

——————————————————————————

? ? 用递归方式遍历二叉树以递归方式对二叉树进行遍历时，算法的思路为：对整棵二叉樹的遍历不断转化为对每个结点同样形式的遍历从而实现对整棵二叉树的遍历。其思路简述如下：

对根结点的左子树进行前序遍历
对根结点的右子树进行前序遍历。

对根结点的左子树进行中序遍历
对根结点的右子树进行中序遍历。

对根结点的左子树进行后序遍历
对根结点的右子树进行后序遍历。

? ? 用递归方式遍历二叉树以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访問过的结点。其思路简述如下：

——————————————————————————

用递归方式对二叉树进行遍历的算法流程较为简单流程图略。

用非递归方式对二叉树进行先序遍历的算法流程图如图1
: 用非递归方式对二叉树进行先序遍历的算法流程图

用非递归方式对二叉树进行中序遍历的算法流程图如图2
: 用非递归方式对二叉树进行中序遍历的算法流程图

用非递归方式对二叉树进行后序遍曆的算法流程图如图3
: 用非递归方式对二叉树进行后序遍历的算法流程图

——————————————————————————

第二步：话不多说放代码

——————————————————————————



我要回帖

 

随机推荐