(4). 在中序线索二叉树上查找任意结点在先序下的后继

这一操作的实现依据是：若一个结点是某子树在中序下的最后一个结点，则它必是该子树在先序下的最后一个结点。该结论可以用反证法证明。
下面就依据这一结论，讨论在中序线索二叉树上查找某结点在先序下后继结点的情况。设开始时，指向此某结点的指针为p。
1. 若待确定先序后继的结点为分支结点，则又有两种情况：
① 当p->ltag=0时，p->lchild为p在先序下的后继；
② ② 当p->ltag=1时，p->rchild为p在先序下的后继。
2. 若待确定先序后继的结点为叶子结点，则也有两种情况：
① 若p->rchild是头结点，则遍历结束；
② 若p->rchild不是头结点，则p结点一定是以p->rchild结点为根的左子树中在中序遍历下的最后一个结点，因此p结点也是在该子树中按先序遍历的最后一个结点。此时，若p->rchild结点有右子树，则所找结点在先序下的后继结点的地址为p->rchild->rchild；若p->rchild为线索，则让p＝p->rchild，反复情况2的判定。
在中序线索二叉树上寻找结点p的先序后继结点的算法如下：

(5). 在中序线索二叉树上查找任意结点在后序下的前驱

这一操作的实现依据是：若一个结点是某子树在中序下的第一个结点，则它必是该子树在后序下的第一个结点。该结论可以用反证法证明。
下面就依据这一结论，讨论在中序线索二叉树上查找某结点在后序下前驱结点的情况。设开始时，指向此某结点的指针为p。
1. 若待确定后序前驱的结点为分支结点，则又有两种情况：
① 当p->ltag=0时，p->lchild为p在后序下的前驱；
② 当p->ltag=1时，p->rchild为p在后序下的前驱。
2. 若待确定后序前驱的结点为叶子结点，则也有两种情况：
① 若p->lchild是头结点，则遍历结束；
② ② 若p->lchild不是头结点，则p结点一定是以p->lchild结点为根的右子
树中在中中序遍历下的第一个结点，因此p结点也是在该子树中按后序遍历的第一个结点。此时，若p->lchild结点有左子树，则所找结点在后序下的前驱结点的地址为p->lchild->lchild；若p->lchild为线索，则让p＝p->lchild，反复情况2的判定。
在中序线索二叉树上寻找结点p的后序前驱结点的算法如下：
BiThrTree IPostPretNode（BiThrTree head,BiThrTree p）
{/*在中序线索二叉树上寻找结点p的先序的后继结点，head为线索树的头结点*/
BiThrTree pre;

(6). 在中序线索二叉树上查找值为x的结点

利用在中序线索二叉树上寻找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。比如，先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。这样，既不用栈也不用递归就可以访问到二叉树的所有结点。

在中序线索二叉树上查找值为x的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为那结点的值与x比较的语句。下面给出其算法：

(7). 在中序线索二叉树上的更新

线索二叉树的更新是指，在线索二叉树中插入一个结点或者删除一个结点。一般情况下，这些操作有可能破坏原来已有的线索，因此，在修改指针时，还需要对线索做相应的修改。一般来说，这个过程的代价几乎与重新进行线索化相同。这里仅讨论一种比较简单的情况，即在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。
下面分两种情况来分析：
1. 若s的右子树为空，如图3.1 (a)所示，则插入结点p之后成为图3.1 (b)
所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。
2. 若s的右子树非空，如图3.2 (a)所示，插入结点p之后如图3.2 (b)所
示。S原来的右子树变成p的右子树，由于p没有左子树，故s成为p的中序前驱，p成为s的右孩子；又由于s原来的后继成为p的后继，因此还要将s原来的本来指向s的后继的左线索，改为指向p。