線索二叉樹的運算
查找某結點*p在指定次序下的前趨和後繼結點
()在中序線索二叉樹中查找結點*p的中序後繼結點
在中序線索二叉樹中查找結點*p的中序後繼結點分兩種情形
① 若*p的右子樹空(即p>rtag為Thread)則p>rchild為右線索直接指向*p的中序後繼【例】下圖的中序線索二叉樹中
結點D的中序後繼是A
② 若*p的右子樹非空(即p>rtag為Link)則*p的中序後繼必是其右子樹中第一個中序遍歷到的結點也就是從*p的右孩子
開始沿該孩子的左鏈往下查找直至找到一個沒有左孩子的結點為止該結點是*p的右子樹中最左下的結點即*P的中序後繼結
點
【例】上圖的中序線索二叉樹中
A的中序後繼是F它有右孩子;
F的中序後繼是H它無右孩子;
B的中序後繼是D它是B的右孩子
在中序線索二叉樹中求中序後繼結點的過程可具體算法如下
BinThrNode *InorderSuccessor(BinThrNode *p)
{//在中序線索樹中找結點*p的中序後繼設p非空
BinThrNode *q;
if (p>rtag==Thread) //*p的右子樹為空
Return p>rchild; //返回右線索所指的中序後繼
else{
q=p>rchild; //從*p的右孩子開始查找
while (q>ltag==Link)
q=q>lchild; //左子樹非空時沿左鏈往下查找
return q; //當q的左子樹為空時它就是最左下結點
} //end if
}
該算法的時間復雜度不超過樹的高度h即O(h)
()在中序線索二叉樹中查找結點*p的中序前趨結點
中序是一種對稱序故在中序線索二叉樹中查找結點*p的中序前趨結點與找中序後繼結點的方法完全對稱具體情形如下
① 若*p的左子樹為空則p>child為左線索直接指向*p的中序前趨結點;
【例】上圖所示的中序線索二叉樹中F結點的中序前趨結點是A
② 若*p的左子樹非空則從*p的左孩子出發沿右指針鏈往下查找直到找到一個沒有右孩子的結點為止該結點是*p的左
子樹中最右下的結點它是*p的左子樹中最後一個中序遍歷到的結點即*p的中序前趨結點
【例】上圖所示中序線索二叉樹中結點E左子樹非空其中序前趨結點是I
在中序線索二叉樹中求中序前趨結點的過程可具體算法如下
BinThrNode *Inorderpre(BinThrNode *p)
{//在中序線索樹中找結點*p的中序前趨設p非空
BinThrNode *q;
if (p>ltag==Thread) //*p的左子樹為空
return p>lchild; //返回左線索所指的中序前趨
else{
q=p>lchild; //從*p的左孩子開始查找
while (q>rtag==Link)
q=q>rchild; //右子樹非空時沿右鏈往下查找
return q; //當q的右子樹為空時它就是最右下結點
} //end if
}
由上述討論可知對於非線索二叉樹僅從*p出發無法找到其中序前趨(或中序後繼)而必須從根結點開始中序遍歷才能找到
*p的中序前趨(或中序後繼)線索二叉樹中的線索使得查找中序前趨和中序後繼變得簡單有效
From:http://tw.wingwit.com/Article/program/sjjg/201311/23876.html
