怎么线索二叉树？

发布网友发布时间：2022-03-31 18:17

共1个回答

热心网友时间：2022-03-31 19:46

用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左右孩子结点的指针域，所以从任一结点出发只能直接找到该结点的左右孩子结点，而无法直接找到该结点在某种遍历序列中的前驱和后继结点。为了保存遍历后结点的前驱和后继信息，可采用增加向前和向后的指针，但这种方法增加了存储开销，不可取。对于具有n个结点的二叉树，采用二叉链表存储结构时，每个结点有两个指针域，总共有2n个指针域，其中有n＋1个空指针域。由此，利用这些空链域来存放遍历后结点的前驱和后继信息，这就是线索二叉树构成的思想。由于遍历方法不同，所获得的线性序列中，结点的前驱和后继也不同，因此线索二叉树又分为前序线索二叉树、中序线索二叉树和后序线索二叉树。

1.线索二叉树的基本概念（1）线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针称为线索。

（2）线索链表：把加上了线索的二叉链表称为线索链表。

（2）线索化：使二叉链表中结点的空链域存放以某种次序遍历得到的前驱或后继信息的过程称为线索化。

（4）线索二叉树：加上线索的二叉树称为线索二叉树。