为什么要研究线索二叉树:当用二叉链表作为二叉树的存储结构时,可以很方便地找到某个结点的左右孩子;但一般情况下,无法直接找到该结点在某种遍历序列中的前驱和后继结点
利用二叉链表中的空指针域:
如果某个结点的左孩子为空,则将空的左孩子指针域改为其前驱
如果某个结点的右孩子为空,则将空的右孩子指针域改为其后继
这种改变指向的指针称为“线索”,加上了线索的二叉树称为线索二叉树(Threaded Binary Tree)
对二叉树按某种遍历次序使其变成线索二叉树的过程叫线索化
为区分lchild和rchild指针到底是指向孩子的指针,还是指向前驱或者后继的指针,对二叉链表中每个结点增设两个标志域ltag和rtag,并约定:
(1)ltag=0,lchild指向该结点的左孩子
(2)ltag=1,lchild指向该结点的前驱
(3)rtag=0,rchild指向该结点的右孩子
(4)rtag=1,rchild指向该结点的后继
定义:
typedef struct BiThrNode{
int data;
int ltag,rtag;
struct BiThrNode lchild,rchild;
}BiThrNode, BiThrTree
