带头结点的中序线索化
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*/
}
}
线索化二叉树
在当前结点p非空时所作的处理如下：
1)左子树线索化
2)对空指针线索化：
①如果p的左孩子为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre(前驱);
②如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1，让pre的右孩子指针指向p(后继);
3)将pre指向刚访问过的结点p，即pre = p;
4)右子树线索化。
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=0;
}
if(!pre->rchild) /*pre的右孩子为空*/
{
pre->RTag=1; /*给pre加上右线索*/
pre->rchild=p; /*pre的右孩子指针指向p(后继)*/
}
else
{
pre->RTag=0;
}
pre=p; /*保持pre指向p的前驱*/
InThreading(p->rchild); /*右子树递归线索化*/
}
}
中序线索二叉树next node
获得前一个节点/后一个节点
Insucc()函数
Node * ThreadedBinaryTree::get_successor(Node * node)
{
if (node->right_thread)
return node->right;
Node * p = node->right;
while (p->left_thread == false) //已线索化，故此处只能用left_thread来判断左子树的情况
p = p->left;
return p;
}
Node * ThreadedBinaryTree::get_precursor(Node * node)
{
if (node->left_thread)
return node->left;
Node * p = node->left;
while (p->right_thread == false) //已线索化，故此处只能用right_thread来判断右子树的情况
p = p->right;
return p;
}
线索二叉树遍历
这个是中序遍历二叉线索树
template <class T>
void ThreadBinaryTree<T>::tinorder()
{
threaded_pointer temp = root;
for (;;) {
temp = Insucc(temp);
if (temp==root) break;
printf(“%3c”, temp->data);
}
}