|
知识路径: > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 >
|
相关知识点:11个
|
|
|
|
以二叉链表作为存储结构时,只能找到左、右子树信息,不能直接得到节点在任一序列中的前驱和后继信息,最简单的方法是每个节点上增加两个指针域,但有点浪费。其实,n个节点的二叉链表中必定存在n+1个空链域,因此可用这些链域来存放节点的前驱和后继信息。改进后的节点结构如下:
|
|
|
|
|
|
|
|
|
|
|
以这种结构构成的二叉链表叫线索链表,其中指向节点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫线索化。
|
|
|
对给定的线索二叉树中的某个节点p,查找节点p的后继(中序),其特点为所有叶子节点的右链直接指示了后继,所有非终端节点的后继应是其右子树中第一个中序遍历的节点。
|
|
|
对给定的线索二叉树中的某个节点p,查找节点p的前驱(中序),其特点为若其左标志为"1",则左链为线索,指示其前驱,否则其前驱为左子树上最后遍历的一个节点。
|
|
|
可见,对线索二叉树进行遍历可通过线索找到相应的前驱和后继,而无须递归进行。
|
|
|
例如,对给定的中序线索化二叉树,查找节点*p的中序后继。在中序线索二叉树中,查找p指针的节点,其后继分为两种情况:若p→rtag=1,则p→rchild,即指向其后继节点;若p→rtag=0,则*p节点的中序后继必为其右子树中第一个中序遍历到的节点,即从*p的右子树开始,沿着左指针链向下找,直到找到一个没有左子树的节点,该节点就是*p的右子树中"最左下"的节点。其算法如下:
|
|
|
|