分析复习数据结构的过程中,觉得二叉树前中后序遍历的非递归实现还是不太好想的,所以结合老师给出的思想,整理了一下自己的思路,记在这里,留日后翻看
递归实际就是栈的先进后出的性质,所以用栈来实现非递归算法。
递归回溯的时候会重新获得当前状态的全部信息,但是非递归实现不会自然有这些,难点就是保存需要的信息。
对于任意节点,只要访问之后先后入栈其非空的右、左孩子即可
中序遍历访问一个节点之前,其左子树的节点已经全部被访问过。
因此根据栈先进后出的特性,入栈一个节点之后,要入栈其左孩子,入栈左孩子后又得入栈左孩子的左孩子…就是说向左入栈到尽头。
这样在栈中访问栈顶时,他的左子树节点已经被全部d出(访问),这个栈顶就可以直接被访问。然后在根据上述规则入栈其右孩子…
后序遍历p p.l p.r .. .. .. ..
根据上边两个的思路,这个大概得按这个顺序入栈:p、p.r、p.l,d出顺序为p.l、p.r、p,后序序列。
不过由于后序遍历的特点,有一个问题:分支结点出现在栈顶时,既可能是正在构建栈的过程(比如接上,此时p.l为栈顶,该继续压栈),又可能是回溯的过程(比如d出了p.l和p.r后p成为栈顶,该访问了)。那究竟访问还是继续压栈呢?
因此我构建了第二个栈s2,用来同步保存s1中结点的深度。
对于任一状态下的栈顶p,满足如下条件之一时访问并d出p:
p无孩子,即p为叶结点
上一次输出结点的深度比p的大(正在回溯)
否则将p的子节点压入。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)