【题目】设中序线索二叉树的结点结构为:|left|ltag|data|rtag|right|. 现已知中序线索
二叉树的根结点地址root。设计一程序,打印出该线索二叉树的中序遍历结果.不得
再使用O(n)级的辅存空间。
【来源】上海交通大学96年第十题(15')
【解答】intravers(root:bitree)
finished:=false;t:=root;
while not finished do
【
while t↑.ltag=0 do t:=t↑.lch // 左孩子不空
write(t↑.data); // 访问左孩子
if t↑.rtag=1 then
【t:=t↑.rch;{后继结点}
write(t↑.data);{访问当前根结点}
t:=t↑.rch{访问当前根结点的右孩子}
】
else
t:=t↑.rch; // 右孩子不空
if t↑.rch=nil then finished:=true
】