2 qq 33286911 qq_33286911 于 2016.02.03 18:01 提问

数据结构关于二叉树遍历的一道题 在线等~

利用栈的基本操作写出先序遍历二叉树的非递归算法
要求进栈的元素最少,

并指出下列二叉树中需进栈的元素。

图片说明

这是答案:

图片说明

根据上述代码,

(1)左子树lchild不需要入栈吗?

(2)入栈顺序是什么?

(3)最后一行代码 if (top>0) bt=s[top--] 是什么意思?

(4)如果是中序或后序,入栈顺序又是什么?

谢谢大神们啦~~ O(∩_∩)O

2个回答

caozhy
caozhy   Ds   Rxr 2016.02.03 18:12
已采纳

3
if (top>0) bt=s[top--]
出栈。取出top位置的元素,并且堆栈往后收缩一个。
4
中序需要将父节点入栈
后序不需要堆栈

caozhy
caozhy   Ds   Rxr 2016.02.03 18:09

(1)不需要,因为它永远是最先访问,相当于入栈后立刻就弹出了。所以不需要
(2)需要将当前节点两个子节点入栈,每次出栈的时候再压入它的子节点。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!