數據結構考研分類復習真題 第六章 答案 (五)[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

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23700.html