什么叫做二叉树的前驱、和后继？

详细一点，我很不明白，看不懂线索二叉树的图

华工大学生 · 2018-4-30 02:32:42

前驱就是接上去的那个结点,后继就是接下去的那两个(一个)结点.这个没有什么问题吧.
线索二叉树看起来确实很乱的,你关键要先把那些左右的0和1标好,然后看要求是先序中序还是后序,把它的序列写出来,根据这个序列去连线就不会错了.

热心网友 · 2018-4-30 02:32:41

　　线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：
　　若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。
　　还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索链表，链表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二叉树是一种物理结构。在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

什么叫做二叉树的前驱、和后继？

2 个回复