[題目分析]在中序穿線樹中找結點的雙親最簡單情況是順線索就可找到例如結點的左子女的右線索和右子女的左線索都指向雙親但對於有左右子女的結點來說則要利用中序穿線樹中線索向上指向祖先的特點若結點p是結點q右子樹中中序遍歷最左下的結點p的左線索指向q若結點p是結點q左子樹上中序遍歷最右下的結點p的右線索指向是q反過來通過祖先找子女就容易了另外若結點q的後繼是中序穿線樹的頭結點則應特殊考慮
void FFA(BiThrTree tpq)//在中序穿線樹t上求結點p的雙親結點q
{q=p; //暫存
while(q>RTAG==) q=q>RLINK; //找p的中序最右下的結點
q=q>RLINK; //順右線索找到q的後繼（p的祖先結點）
if (q==t) q=t>LLINK; //若後繼是頭結點則轉到根結點
if (q==p) {printf(根結點無雙親\n)return; }
if (q>LLINK==p) return(q); else q=q>LLINK; //准備到左子樹中找p
while (q>RLINK!=p) q=q>RLINKreturn(q); } //找最右結點的過程中回找到p
}//結束FFA
[算法討論]本題也可以先求結點p最左下結點的前驅線索請讀者自己寫出算法
[題目分析]帶頭結點的中序線索樹其頭結點的lchild指向二叉樹的根結點頭結點的rchild域指向中序遍歷的最後一個結點而二叉樹按中序遍歷的第一個結點的lchild和最後一個結點的rchild指向頭結點故從頭結點找到根結點後順後繼訪問二叉樹在中序線索樹中找前序的後繼已在第題進行了詳細的討論這裡不再贅述中序線索樹在上面的四應用題已畫過多個這裡也不重復
void PreorderInThreat(BiTrhTree tbt)
//前序遍歷一中序全線索二叉樹tbttbt是頭結點指針
{bt=tbt>lchild;
while(bt)
{while(bt>ltag==){printf(bt>data); bt=bt>lchild;}//沿左分枝向下
printf(bt>data); //遍歷其左標志為的結點准備右轉
while(bt>rtag== && bt>rchild!=tbt) bt=bt>rchild;//沿右鏈向上
if (bt>rchild!=tbt) bt=bt>rchild;//沿右分枝向下
}
}//結束PreorderInThreat
時間復雜度O(n)
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23699.html
