《中序穿线二叉树.doc》由会员分享，可在线阅读，更多相关《中序穿线二叉树.doc（3页珍藏版）》请在三一办公上搜索。
1、#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:Create
2、BinaryTree(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=N
3、ULL;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
4、*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
5、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;例如输入：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
