基本信息

---

下载

文档摘要

---

线索二叉树线索二叉树的概念当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能得到结点在遍历序列中的前驱和后继信息。如何找到遍历过程中动态得到的每个结点的直接前驱和直接后继(第一个和最后一个除外)呢?可以采用两种方法：第一种方法是将二叉树遍历一遍，在遍历的过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表中的空链域，将结点遍历过程中的前驱和后继信息保存下来。一棵具有n个结点的二叉树，有n+1个空闲的指针域未用，可以用这些空闲的指针域存放结点的直接前驱和后继信息。对结点的指针域做如下规定：(1)若结点有左孩子，则l