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

[题目分析]在中序穿线树中找结点的双亲最简单情况是顺线索就可找到例如结点的左子女的右线索和右子女的左线索都指向双亲但对于有左右子女的结点来说则要利用中序穿线树中线索向上指向祖先的特点若结点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)

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