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

[题目分析]在中序线索树中非递归查找数据域为A的结点（设该结点存在其指针为P）并将数据域为x的Q结点插入到左子树中若P无左子女则Q成为P的左子女原P的左线索成为Q的左线索Q的右线索为P若P有左子树设P左子树中最右结点的右线索是结点Q结点Q的右线索是P

void InThrInsert(BiThrTree TQ; ElemType A)

//在中序线索二叉树T中查找其数据域为A的结点并在该结点的左子树上插入结点Q

{BiThrTree P=T;

while(P)

{while(P>LT== && P>data!=A) P=P>LL; //沿左子树向下

if (P>data==A) break; //找到数据域为A的结点退出循环

while(P>RT==) P=P>RL; //还没找到数据域为A的结点沿右线索找后继

P=P>RL; //沿右子树向下

}

if(P>LT==) //P没有左子树Q结点插入作P的左子女

{Q>LL=P>LL; Q>LT= //将P的左线索作为Q的左线索

}

else //P有左子树应修改P的左子树最右结点的线索

{Q>LL=P>LL;Q>LT=; //Q成为P的左子女

s=Q>LL; //s指向原P的左子女

while(s>RT==) s=s>RL; //查找P的左子树最右边的结点

s>RL=Q; //原P左子树上最右结点的右线索是新插入结点Q

}

P>LT=;P>LL=Q; //修改P的标记和指针

Q>RT=;Q>RL=P; //将Q链为P的左子女其中序后继是P;

}//结束InThrInsert

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