问题
单项选择题
对于任意非空二叉树,要设计出其后序遍历的非递归算法而不使用堆栈结构,最合适的方法是对该二叉树采用()存储结构。
A.三叉链表
B.二叉链表
C.顺序
D.索引
答案
参考答案:A
解析:
若二叉树采用二叉链表结构,则链表中只有孩子结点的地址,而无双亲结点的地址,而遍历过程中又需要结点的双亲结点的地址,为此,遍历操作设置一个堆栈来达到这个目的。如果不设置堆栈,则需要采用三叉链表结构,因为三叉链表中除了孩子结点的地址以外,还保存了结点的双亲结点的地址,故选择A。