[題目分析]在中序全線索化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
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23695.html
