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

[题目分析]线索化是在遍历中完成的因此对于二叉树进行前序中序后序遍历在访问根结点处进行加线索的改造就可实现前序中序和后序的线索化

BiThrTree pre=null;//设置前驱

void PreOrderThreat(BiThrTree BT)

//对以线索链表为存储结构的二叉树BT进行前序线索化

{if (BT!=null)

{if (BT>lchild==null){BT>ltag=; BT>lchild=pre;}//设置左线索

if (pre!=null && pre>rtag==) pre>rchild=BT; //设置前驱的右线索

if (BT>rchild==null) BT>rtag=; //为建立右链作准备

pre=BT;//前驱后移

if (BT>ltag==) PreOrderThreat(BT>lchild); //左子树前序线索化

PreOrderThreat(BT>rchild); //右子树前序线索化

}//if (BT!=null) }结束PreOrderThreat

BiThrTree pre==null;

void InOrderThreat(BiThrTree T)//对二叉树进行中序线索化

{if (T)

{InOrderThreat(T>lchild); //左子树中序线索化

if (T>lchild==null) {T>ltag=; T>lchild=pre; } //左线索为pre;

if (pre!=null && pre>rtag==) pre>rchild=T;} //给前驱加后继线索

if (T>rchild==null) T>rtag=; //置右标记为右线索作准备

pre=BT;//前驱指针后移

InOrderThreat(T>rchild); //右子树中序线索化

} }//结束InOrderThreat

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