中序穿线二叉树.doc
#include<iostream>using namespace std;template<class T>struct TBtnode T d; int lflag; int rflag; TBtnode *lchild; TBrnode *rchild;template<class T>class InTBinaryTree private:TBtnode<T> *BT; public:InTBinaryTree() BT=NULL;return;void CreateBinaryTree(T);void CreateInTBinaryTree();void InTTree(); ;template<class T>void InTBinaryTree<T>:CreateBinaryTree(T end) TBtnode<T> *p; T x; cin>>x; if(x=end) return; p=new TBtnode<T> 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;template<class T>static Create(TBtnode<T> *p,int k,T end) TBtnode<T> *q; T x; cin>>x; if(x!=end) q=new TBtnode<T> 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;template<class T>void InTBinaryTree<T>:CreateInTBinaryTree() TBtnode<T> *p,*q=NULL; p=BT; CreateInTTree(p,&q); /生成中序线索二叉链表，p当前q先前结点 return; template<class T>static CreateInTTree(TBtnode<T> *p,TBtnode<T> *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;template<class T>void InTBinaryTree<T>:InTTree() TBtnode<T> *p; if(BT=NULL) return; p=BT; while(p->lflag=0) p=p->lchild; /沿左链找到叶子结点(中序序列首结点)； cout<<p->d<<” “; while(p->rchild!=NULL) /沿右链扫描后件； if(p->rflag=1) /若当前结点的右标志域为1，则当前结点 p=p->rchild; /的指针值为其后件的存储序号；else p=p->rchild; /若当前结点的右指针值不空，则 while(p->lflag=0)&&(p->lchild!=NULL) /沿右子树的左链扫描 p=p->lchild;cout<<p->d<<” “; cout<<endl; return;参考调试程序：int main() InTBinaryTree<int> b;/建立一棵二叉树对象b，数据域为整型 cout<<”请输入各结点值，以-1为结束符”<<endl; b.CreateBinaryTree(-1); b.CreateInTBinaryTree(); cout<<”中序序列为：”<<endl; b.InTTree(); return 0;例如输入：18 20 09 -1 -1 25 47 -1 -1 -1 36 -1 12 06 -1 -1 33 -1 -1结果为： 9 20 47 25 18 36 6 12 33
