中序线索二叉树前驱后继.doc

《中序线索二叉树前驱后继.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1#include23usingnamespacestd;45#defineMAX150067//二叉树定义8typedefstructBiTreeNode{9chardata;10BiTreeNode*lChild;11BiTreeNode*rChild;12intlTag,rTag;13}BiTreeNode;1415//全局变量16BiTreeNode*pre=NULL;17BiTreeNode*point[MAX+1];//构建二叉树时辅助,用于定位子节点1819//构建二叉树20BiTreeNode*CreateBiTree()21{22

2、BiTreeNode*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));23inti,j;chardata;24cin>>i>>data;25while(i!=0&&data!='#')26{27BiTreeNode*newNode=(BiTreeNode*)malloc(sizeof(BiTreeNode));28newNode->data=data;29newNode->lTag=0;newNode->rTag=0;30newNode->lChild=NULL;newNode->rChild=NULL;31point[i]=

3、newNode;32if(i==1)//为二叉树根节点33{34root=point[1];35}36else37{38j=i/2;39if(i%2==0)//为左孩子结点40{41point[j]->lChild=newNode;42}43else44{1point[j]->rChild=newNode;2}3}4cin>>i>>data;5}6returnroot;7}89//中序线索化二叉树,pre初始化为NULL10voidInthread(BiTreeNode*root)11{12if(root!=NULL)13{14Inthread(root->lChil

4、d);15if(root->lChild==NULL)16{17root->lTag=1;root->lChild=pre;18}19if(pre!=NULL&&pre->rChild==NULL)20{21pre->rTag=1;pre->rChild=root;22}23pre=root;24Inthread(root->rChild);25}26}272829//查找结点p的前驱结点30BiTreeNode*InPre(BiTreeNode*p)31{32if(p->lTag==1)returnp->lChild;33BiTreeNode*q=p->lChild

5、;34if(q==NULL){35cout<<"无前驱结点";36returnNULL;37}38while(q->rTag!=1)39{40q=q->rChild;41}42returnq;43}441//查找结点p的后继结点2BiTreeNode*InSub(BiTreeNode*p)3{4if(p->rTag==1)returnp->rChild;5BiTreeNode*q=p->rChild;6if(q==NULL){7cout<<"无后继结点";8returnNULL;9}10while(q->lTag!=1)11{12q=q->lChild;13}

6、14returnq;15}161718intmain()19{20charcmd;intindex;21do{22BiTreeNode*root=CreateBiTree();23Inthread(root);24cout<<"输入您要查找的结点,序号index";25cin>>index;26BiTreeNode*nodePre=InPre(point[index]);27BiTreeNode*nodeSub=InSub(point[index]);28if(nodePre!=NULL)29cout<<"结点"<

7、re->data<<"";30if(nodeSub!=NULL)31cout<<"结点"<data<<"";32cout<<"继续吗Y/y?";33cin>>cmd;34}while(cmd=='Y'

8、

9、cmd=='y');35return0;36}