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

void InOrderThreat(BiThrTree thrt)

//thrt是指向中序全线索化头结点的指针本算法中序遍历该二叉树

{p=thrt>lchild; //p指向二叉树的根结点当二叉树为空时p指向thrt

whild(p!=thrt)

{while（p>ltag==) p=p>lchild;//沿左子女向下

visit(*p);//访问左子树为空的结点

while(p>rtag== && p>rchild!=thrt){p=p>rchild;visit(*p);}//沿右线索访问后继结点

p=p>rchild;//转向右子树

} }//结束InOrderThread

[题目分析]若使新插入的叶子结点S成T右子树中序序列的第一个结点则应在T的右子树中最左面的结点（设为p）处插入使S成为结点p的左子女则S的前驱是T后继是p

void ThrTreeInsert(BiThrTree TS)

//在中序线索二叉树T的右子树上插入结点S使S成为T右子树中序遍历第一个结点

{p=T>rchild; //用p去指向T的右子树中最左面的结点

while(p>ltag==) p=p>lchild;

S>ltag=;S>rtag=; //S是叶子其左右标记均为

S>lchild=T;S>rchild=p;//S的前驱是根结点T后继是结点p

p>lchild=S;p>ltag=; //将p的左子女指向S 并修改左标志为

}//结束 ThrTreeInsert

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