穿线树

1、穿线树：

在二叉链表存储形式的二叉树中，把节点中空指针利用成为周游线索。原来为空的左指针指向结点在某种周游序列下的前驱，原来为空的右指针指向结点在同一种周游序列下的后继。这样的二叉树称为穿线树。

.. 可以有中序穿线树，前序穿线树，后序穿线树。每种穿线树可以只穿一半。穿线树的目的是利用空指针的存储空间，建立周游线索。为了区分线索和指针，需在每个结点中增加两个标志位，分别标识左右指针域是实际指针还是线索。

2、中序周游中序穿线树：先从穿线树的根出发，一直沿左指针，找到“最左”(它一定是中序的第一个

结点)；然后反复地找结点的中序后继。一个结点的右指针如果是线索，则右指针就是下一个要周游的结点，如果右指针不是线索，则它的中序后继是其右子树的“最左”结点。

3、穿线树节点的插入：

往中序穿线树里插入结点的算法，规定插入这样进行：newpointer指向要插入的新结点，pointer指向穿线二叉树里的一个结点。将新结点插进来作为pointer指向的结点的右子树的根。pointer指向的结点的原来的右子树现在作为新结点的右子树(新结点的左子树为空)。即在中序序列里，新结点刚好插到p所指向的结点的后面。pointer的新后继结点是newpointer，newpointer的后继是pointer->rightchild()。如果Pointer的右子树不空，则右子树的最左结点线索指向newpointer；若空，则pointer的右线索给newpointer继承。