非递归前序遍历 °前序的程序实现(非递归) e 前序:A、L、B、E、C、D 1、根结点进栈 2、结点出栈,被访问 3、结点的右、左儿子(非空)进栈 4、反复执行2、3,至栈空为止。 D出栈访问 访问访问D进栈等 A进栈A出栈C、LL出栈E、BB出栈E出栈C出栈 后,栈 访问进栈访问进栈访问 <B> L <E> <E> <A> <c> <C> <c> <c> <c> <D> 分析:p的前序的直接后继q:1、p有左儿子,则q=该左儿子;2、p无左儿子,有右儿子,则 q=该右儿子;3、p无左儿子、右儿子,搜索其祖先结点的右儿子送q。找不到结束。非递归前序遍历 B C D E L A •前序的程序实现（非递归）： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。 e.g: 前序：A、L、B、E、C、D <A> <C> <L> <C> <E> <B> <C> <E> <C> <C> <D> A出栈 访问 L出栈 访问 B出栈 访问 E出栈 访问 C出栈 访问 D出栈访问 后，栈空 结束 A进栈 C、L 进栈 E、B 进栈 D进栈 分析：p的前序的直接后继q: 1、p有左儿子，则q=该左儿子； 2、p无左儿子，有右儿子，则 q=该右儿子； 3、 p无左儿子、右儿子 ，搜索其祖先结点的右儿子送q。找不到结束