摘要
提出非递归后序遍历二叉树的新方法,二址栈法;它借助一个二址堆栈,栈中每个元素由某结点地址及其右孩地址构成,不妨简称根址和右孩址。主要思路是,p指向二叉树T之后;若p非空,则p和*p的右孩地址入栈,p移指其左孩,无论其左孩是否为空;否则,若p为空,有两种情况,第一种情况,栈顶右孩址非空,p取该值,即p移指那右孩,并置栈顶右孩址为空;第二种情况,栈顶右孩址为空,出栈,栈顶根址到q而访问*q,p不动;如此循环,直到栈和p均为空。
出处
《福建电脑》
2017年第10期114-115,53,共3页
Journal of Fujian Computer