在中序遍历过程中,结点的后继是遍历其右子树时访问的第一个结点,也就是右子树中位于最左下的结点。例如图 3 中结点 * ,后继结点为结点 c ,是其右子树中位于最左边的结点。反之,结点的前趋是左子树最后访问的那个结点。 如果该结点是父结点的左孩子,且父结点有右子树,后继结点为父结点的右子树在后序遍历列出的第一个结点。 使用后序遍历建立的线索二叉树,在真正使用过程中遇到链表的断点时,需要访问父结点,所以在初步建立二叉树时,宜采用三叉链表做存储结构。 |
在中序遍历过程中,结点的后继是遍历其右子树时访问的第一个结点,也就是右子树中位于最左下的结点。例如图 3 中结点 * ,后继结点为结点 c ,是其右子树中位于最左边的结点。反之,结点的前趋是左子树最后访问的那个结点。 如果该结点是父结点的左孩子,且父结点有右子树,后继结点为父结点的右子树在后序遍历列出的第一个结点。 使用后序遍历建立的线索二叉树,在真正使用过程中遇到链表的断点时,需要访问父结点,所以在初步建立二叉树时,宜采用三叉链表做存储结构。 |