數據結構考研分類復習真題 第六章 答案 (五)[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

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23696.html