📝3️⃣线索化二叉树
当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，儿不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中得到，为此引入线索二叉树来保存这些动态过程中得到的有关前驱和后继的信息。
✨相关概念
普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快顺藤摸瓜而遍历整个树。
【线索】：指结点前驱和后继的指针。
【线索二叉树】：加上线索额二叉树。
【线索化】：对二叉树以某种次序遍历使其变为线索二叉树的过程。
【线索链表】：加上线索二叉链表。
✨实现方法
通过两种保存前驱和后继的方法：
- 利用空链域： 二叉链表n有（n+1）个空链域。
- 增加两个域：fwd 和 bwd。
在线索化二叉树时，若结点有左子树，则lchild指向其左孩子，否则，lchild指向其直接前驱（即线索）。同理，若结点有右子树，则rchild指向其右孩子，否则，rchild指向其直接后继。
为了避免混淆，增加两个标志域。
| lchild | LTag | data | RTag | rchild |
若 LTag：= 0，lchild指向其左孩子，若 LTag：= 1，rchild指向其前驱。
同理，若 RTag：= 0，lchild指向其右孩子，若 RTag：= 1，rchild指向其后继。
✨类型定义
typedef struct BiThrNode { TElemType data; struct BiThNode *lchild,*rchild;//左右孩子指针 int LTag, RTag;//左右标记 }BiThrNode,*BiThrNode;
✨以结点p为根结点中序线索化
【算法步骤】
- 如果p非空，左子树递归线索化。
- 如果p的左孩子为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre（前驱）；否则将p的LTag置为0。
- 如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1，让pre的右孩子指针指向p（后继）；否则将pre的RTag置为0。
- 将pre指向刚访问过的结点p，即pre = p。
- 右子树递归线索化。
【算法描述】
void InThreading(BiThrTree p) { //pre是全局变址，初始化时其右孩子指针为空，便于在树的最左点开始建线索 if(p) InThreading (p-> lchild) ;//左子树递归线索化 if (! p-> lchild) //p的左孩子为空 ｛ p-> LTag=1; //给p加上左线索 p-> lchild=pre; //p的左孩子指针指向pre(前驱） } else p->LTag=O; if (! pre-> rchild) //pre的右孩子为空 ｛ pre-> RTag=1; //给pre加上右线索 pre-> rchld=p; //pre的右孩子指针指向p(后继） } else p->RTag=O; pre=p; //保持pre指向p的前驱 InThrending (p-> rchild) ; //右子树递归线索化 }
✨带头结点的二叉树中序线索化
【算法描述】
void InOrderThreading(BiThrTree &Thrt,BiThrTree T) { //中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 Thrt = new BiThrNode;//建立头结点 Thrt -> LTag = 0;//头结点有左孩子，若树非空，则其左孩子为树根 Thrt -> RTag = 1;//头结点的右孩子指针为右线索 Thrt -> rchild = Thrt;//初始化时右指针指向自己 if(!T) Thrt -> lchild = Thrt;//若树为空，则左指针也指向自己 else { Thrt -> lchild = T;//头结点的左孩子指向根 pre = Thrt;//pre初值指向头结点 InThreading(T);//对以T为根的二叉树进行中序线索化 pre -> rchild = Thrt;//线索化完成后，pre为最右节点，pre的右线索指向头结点 pre -> RTag = 1; Thrt -> rchild = pre;//头结点的右线索指向pre } }
