中序穿线二叉树.doc

#includeusing namespace std;templatestruct tbtnode t d; int lflag; int rflag; tbtnode *lchild; tbrnode *rchild;templateclass intbinarytree private:tbtnode *bt; public:intbinarytree() bt=null;return;void createbinarytree(t);void createintbinarytree();void inttree(); ;templatevoid intbinarytree:createbinarytree(t end) tbtnode *p; t x; cinx; if(x=end) return; p=new tbtnode; p-d=x;p-lchild=null;p-rchild=null;p-lflag=0;p-rflag=0; bt=p; create(p,1,end); create(p,2,end);return;templatestatic create(tbtnode *p,int k,t end) tbtnode *q; t x; cinx; if(x!=end) q=new tbtnode; q-d=x;q-lchild=null;q-rchild=null;q-lflag=0;q-rflag=0; if(k=1) p-lchild=q; /连接到左子树； if(k=2) p-rchild=q; create(q,1,end); /输入左子结点的值； create(q,2,end);return 0;templatevoid intbinarytree:createintbinarytree() tbtnode *p,*q=null; p=bt; createinttree(p,&q); /生成中序线索二叉链表，p当前q先前结点 return; templatestatic createinttree(tbtnode *p,tbtnode *q) if(p!=null) createinttree(p-lchild,q);if( (*q!=null)&(*q)-rchild=null) (*q)-rchild=p; /若先前访问结点的右指针为空，则将当前访问结点的(*q)-rflag=1; /序号填入，并置右标志域为1；if(p-lchild=null) p-lchild=(*q); /若当前访问结点的左指针为空，则将先前访问结点的 p-lflag=1; /序号填入，并置左标志域为1；*q=p; /记住当前访问结点，即当前变为先前；createinttree(p-rchild,q); return 0;templatevoid intbinarytree:inttree() tbtnode *p; if(bt=null) return; p=bt; while(p-lflag=0) p=p-lchild; /沿左链找到叶子结点(中序序列首结点)； coutdrchild!=null) /沿右链扫描后件； if(p-rflag=1) /若当前结点的右标志域为1，则当前结点 p=p-rchild; /的指针值为其后件的存储序号；else p=p-rchild; /若当前结点的右指针值不空，则 while(p-lflag=0)&(p-lchild!=null) /沿右子树的左链扫描 p=p-lchild;coutd” “; coutendl; return;参考调试程序：int main() intbinarytree b;/建立一棵二叉树对象b，数据域为整型 cout”请输入各结点值，以-1为结束符”endl; b.createbinarytree(-1); b.createintbinarytree(); cout”中序序列为：”endl; b.inttree(); return 0;例如