数据结构考研分类复习真题 第六章 答案 (五)[39]

[题目分析]在中序全线索化T树的P结点上插入以X为根的中序全线索化二叉树要对X有无左右子树进行讨论并修改X左(右)子树上最左结点和最右结点的线索在中序线索树上查找某结点p的前驱的规律是若p>ltag=则p>lchild就指向前驱否则其前驱是p的左子树上按中序遍历的最后一个结点查找某结点p的后继的规律是若p>rtag=则p>rchild就指向后继否则其后继是p的右子树上按中序遍历的第一个结点

int TreeThrInsert(BiThrTree TPX)

//在中序全线索二叉树T的结点P上插入以X为根的中序全线索二叉树返回插入结果信息

{if(P>ltag== && P>rtag==) {printf(P有左右子女插入失败\n) return(); }

if(P>ltag==) //P有左子女将X插为P的右子女

{if(X>ltag==) X>lchild=P; //若X无左子树 X的左线索(前驱)是P

else //寻找X的左子树上最左（下）边的结点

{q=X>lchild;

while(q>ltag==) q=q>lchild;

q>lchild=P;

}

if(X>rtag==) //修改X的右线索

X>rchild=P>rchild; //将P的右线索改为X的右线索

else //找X右子树最右面的结点

{q=X>rchild; while(q>rtag==) q=q>rchild;

q>rchild=P>rchild;

}

P>rtag=;P>rchild=X; //将X作为P的右子树

} //结束将X插入为P的右子树

else //P有右子女将X插入为P的左子女

{if(X>ltag==) //X无左子女

X>lchild=P>lchild; //将P的左线索改为X的左线索

else //X有左子女找X左子树上最左边的结点

{q=X>lchild;

while(q>ltag==) q=q>lchild;

q>lchild=P>lchild;

}

if(X>rtag==) X>rchild=P; //若X无右子树则X的右线索是P

else //X有右子树查其右子树中最右边的结点将该结点的后继修改为P

{q=X>rchild;

while(q>rtag==) q=q>rchild;

q>rchild=P;

}

P>ltag=; //最后将P的左标记置

P>lchild=X; //P的左子女链接到X

} //结束将X插入为P的左子女

} //结束Tree Thrfnsert

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []