考研笔记-计算机之数据结构:层次结构-树(二叉树线索)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

二叉树的线索

遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息（前驱和后继均指以某种次序遍历所得序列中的前驱和后继），这种信息只有在遍历的动态过程中才能得到。在有n个结点的二叉链表中必定存在n+1个空链域（因为n个结点的二叉链表中共有2n个链域，n个结点的二叉树中共有n-1个分支，所以剩余n+1个空链域），可利用这些空链域存放结点的前驱和后继信息，并作如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继；同时每个结点添加两个标志域LTag和RTag分别标志lchild和rchild指示左孩子或前驱及右孩子或后继（添加两个标志域相对于直接添加两个指针域指示前驱和后继要节省空间，因标志域占用的空间比指针域小的多）。

二叉树结点中的指针若用于指示前驱或后继，而不是左、右孩子，则称该指针为线索。

加入线索的二叉链表称为线索链表。

加入线索的二叉树称为线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

二叉树的线索化的实质是在遍历的过程中，将二叉链表结点的空指针域改为指向前驱或后继的线索，同时设置标识位的过程。

线索二叉树的遍历

在线索二叉树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空为止。在后序线索二叉树上找后继结点时有时需要知道双亲结点，故在后序线索二叉树上进行遍历时需要栈的支持；在中序和先序线索二叉树上找后继结点时无需知道双亲结点，故在中序和先序线索二叉树上进行遍历时不需栈的支持；

可仿照线性表的存储结构，在二叉树的线索链表上添加一个头结点，并令其rchild域指向二叉树的根结点，且其RTag=LINK，其lchild域指向中序遍历时访问的最后一个结点，且其LTag= THREAD；令二叉树中序序列中的第一个结点的lchild域（必为空）和最后一个结点的rchild域（必为空）均指向头结点，即头结点的后继为中序序列的第一个结点，前驱为中序序列的最后一个结点。中序序列的第一个结点的前驱和最后一个结点的后继均为头结点。因而建立起二叉树的双向线索链表。

在中序线索二叉树中确定结点的前驱和后继的方法

在中序线索二叉树上遍历二叉树，其时间复杂度仍为，但常数因子要比在二叉链表上遍历二叉树小，且不需设栈。

二叉树的插入

在二叉树中可以插入一棵根结点的左子树或右子树为空的树。

二叉树的删除

在二叉树中可以删除以指定结点为根的整棵子树。