《数据结构中序线索二叉树.doc》由会员分享，可在线阅读，更多相关《数据结构中序线索二叉树.doc（12页珍藏版）》请在三一文库上搜索。
1、/线索二叉树的三叉链表结点类templateclass ThreadBinaryNodepublic:T data;ThreadBinaryNode*left,*right,*parent;int ltag,rtag;ThreadBinaryNode(T data,ThreadBinaryNode*left=NULL,ThreadBinaryNode*right=NULL,ThreadBinaryNode*parent=NULL)this-data=data;this-left=left;this-right=right;this-parent=parent;this-ltag=this-rt
2、ag=0;/ThreadBinaryNode.h#include ThreadBinaryNode.h template class ThreadBinaryTree /中序线索二叉树类 public: ThreadBinaryNode *root; ThreadBinaryTree(T prelist, int n);/以标明空子树的先根序列构造一棵中序线索二叉树 ThreadBinaryNode*search(T value);/查找值为value的结点,返回节点ThreadBinaryNode*inpre(ThreadBinaryNode *p); ThreadBinaryNode*in
3、sert(ThreadBinaryNode *p, T value, bool leftChild=true); /插入value作为p结点的孩子ThreadBinaryNode*insertroot(char value,bool rootleft);ThreadBinaryNode*findlast() ;ThreadBinaryNode*findfirst() ; ThreadBinaryTree(); void inorder(); /中根次序遍历中序线索二叉 ThreadBinaryNode* create(T prelist, int n, int &i,ThreadBinaryN
4、ode*t); /以标明空子树的先根次序遍历序列创建一棵子树 void inThread(ThreadBinaryNode *p, ThreadBinaryNode *&front); /中序线索化以p结点为根的子树 ThreadBinaryNode* search(ThreadBinaryNode *p, T value); /在以p为根的子树中查找首次出现的值为value的结点ThreadBinaryNode* innext(ThreadBinaryNode *p); /返回p在中根次序下的后继结点 void destroy(ThreadBinaryNode *p); /撤销以p结点为根的
5、子树void remove(ThreadBinaryNode *p);/删除;template ThreadBinaryTree:ThreadBinaryTree(T prelist, int n) /以标明空子树的先根序列构造一棵中序线索二叉树 int i=0;ThreadBinaryNode*p=NULL;root=create(prelist,n,i,p);ThreadBinaryNode*front=NULL;inThread(root,front); /中序线索化二叉树template ThreadBinaryNode* ThreadBinaryTree:create(T preli
6、st, int n, int &i,ThreadBinaryNode*t) /以标明空子树的先根序列创建一棵子树，算法同BinaryTree ThreadBinaryNode *p=NULL; if (in) T elem = prelisti; i+; if (elem!=NULL) p = new ThreadBinaryNode(elem);p-parent=t; p-left = create(prelist,n,i,p); p-right = create(prelist,n,i,p); return p;template ThreadBinaryNode* ThreadBinary
7、Tree:inpre(ThreadBinaryNode *p) ThreadBinaryNode *q=this-root;ThreadBinaryNode *temp=NULL;while (q!=NULL & q-ltag=0) /寻找根的最左边的后代结点，即第一个访问结点 q=q-left; while (q!=NULL) if(innext(q)=p)temp=q;return temp; q=innext(q); return temp; template void ThreadBinaryTree:inThread(ThreadBinaryNode* p, ThreadBinary
8、Node* &front) /中序线索化以p结点为根的子树，front指向p的前驱结点 if (p!=NULL) inThread(p-left, front); /中序线索化p的左子树 if (p-left=NULL) /若p的左子树为空 p-ltag=1; /设置左线索标记 p-left=front; /设置p的left为指向前驱front的线索 if (p-right=NULL) /若p的右子树为空 p-rtag=1; /设置右线索标记 if (front!=NULL & front-rtag=1) front-right=p; /设置前驱front的right为指向后继p的线索 fro
9、nt=p; inThread(p-right, front); /中序线索化p的右子树 template ThreadBinaryNode* ThreadBinaryTree:innext(ThreadBinaryNode *p) /返回p在中根次序下的后继结点 if (p-rtag=1) /若右子树为空 p=p-right; /则p-right是指向p后继结点的线索 else p=p-right; /进入右子树 while (p-ltag=0) /寻找最左边的后代结点 p=p-left; return p;template void ThreadBinaryTree:inorder() /中
10、根次序遍历中序线索二叉树，非递归算法 cout中根次序遍历中序线索二叉树: ; ThreadBinaryNode *p=root; while (p!=NULL & p-ltag=0) /寻找根的最左边的后代结点，即第一个访问结点 p=p-left; while (p!=NULL) coutdata ; p=innext(p); /返回p在中根次序下的后继结点 coutendl;template ThreadBinaryNode* ThreadBinaryTree:search(T value) /查找首次出现的值为value结点 return search(root, value); tem
11、plate ThreadBinaryNode* ThreadBinaryTree:search(ThreadBinaryNode *p, T value) /在以p为根的子树中查找 /先根次序遍历查找值为value的结点，返回首次出现结点指针，若未找到返回NULL ThreadBinaryNode *find=NULL; /记载找到结点 if (p!=NULL) if (p-data=value) return p; if(p-ltag=0)/查找成功，返回结点指针 find = search(p-left, value); /在左子树中查找，find指向找到结点，递归调用 if (find=
12、NULL & p-rtag=0) /若在左子树中未找到 find = search(p-right, value); /则继续在右子树中查找，递归调用 return find; /返回查找结果 template ThreadBinaryTree:ThreadBinaryTree() /析构函数 destroy(root); coutendl;template void ThreadBinaryTree:destroy(ThreadBinaryNode *p) /撤销以p结点为根的子树 /递归算法的后根次序遍历 if (p!=NULL) if (p-ltag=0) destroy(p-left)
13、; if (p-rtag=0) destroy(p-right); delete p; template void ThreadBinaryTree:remove(ThreadBinaryNode *p)if(p!=NULL)if(p!=this-root)if(p-ltag=1&p-rtag=1)/p为叶子节点ThreadBinaryNode *q=p-parent;/this-getParent(p);if(q-left=p)/左叶子节点q-left=p-left;q-ltag=1;else if(q-right=p)/右叶子节点q-right=p-right;q-rtag=1;p-par
14、ent=NULL;/将父母节点置空delete p;else if(p-ltag=0 & p-rtag=1)/p有左孩子，没右孩子ThreadBinaryNode *q=p-parent;/this-getParent(p);if(q!=NULL)if(q-left=p)ThreadBinaryNode *temp=this-inpre(p);q-left=p-left;p-left-parent=q;temp-right=p-right;p-parent=NULL;delete p;else if(q-right=p)ThreadBinaryNode *temp=this-inpre(p);
15、/找到p的前驱节点temp q-right=p-left;p-left-parent=q;temp-left=p-left;p-parent=NULL;delete p;else if(p-ltag=1&p-rtag=0)/p有右孩子，没左孩子ThreadBinaryNode *q=p-parent;/this-getParent(p);if(q!=NULL)if(q-left=p)ThreadBinaryNode *temp=this-innext(p);q-left=p-right;p-right-parent=q;temp-left=p-right;p-parent=NULL;delet
16、e p;else if(q-right=p)ThreadBinaryNode *temp=this-innext(p);q-right=p-right;p-right-parent=q;temp-left=p-right;p-parent=NULL;delete p;else if(p-ltag=0 & p-rtag=0)/p为二度节点ThreadBinaryNode *q=p-parent;/this-getParent(p);if(q!=NULL)if(q-left=p)ThreadBinaryNode *temp1=this-innext(p);ThreadBinaryNode *tem
17、p2=this-inpre(p);q-left=p-right;temp1-left=p-left;temp1-ltag=0;temp2-right=temp1;delete p;else if(q-right=p)ThreadBinaryNode *temp1=this-innext(p);ThreadBinaryNode *temp2=this-inpre(p);q-right=p-right;p-right-parent=q;temp1-left=p-left;p-left-parent=temp1;temp1-ltag=0;temp2-right=temp1;p-parent=NULL
18、;delete p;else if(p=this-root)if(p-right=NULL & p-left!=NULL)ThreadBinaryNode *temp=this-inpre(this-root);this-root=p-left;p-left-parent=NULL;temp-right=NULL;delete p;else if(p-left=NULL&p-right!=NULL)ThreadBinaryNode *temp=this-innext(this-root);this-root=p-right;p-right-parent=NULL;temp-left=NULL;
19、delete p;else if(p-left!=NULL & p-right!=NULL)ThreadBinaryNode *temp1=this-innext(p);ThreadBinaryNode *temp2=this-inpre(p);this-root=p-left;p-right-parent=NULL;temp2-right=p-right;p-right-parent=temp2;temp2-rtag=0;temp1-left=temp2;p-parent=NULL;delete p;template ThreadBinaryNode* ThreadBinaryTree:in
20、sert(ThreadBinaryNode *p, T value, bool leftchild) /插入value作为p结点的孩子 /若leftChild=true，插入结点作为左孩子，否则作为右孩子 ThreadBinaryNode *q=NULL;ThreadBinaryNode *temp=NULL; if (p!=NULL) if (leftchild) q = new ThreadBinaryNode(value,p-left,p); if(p-ltag=1)q-ltag=q-rtag=1;p-ltag=0;p-left=q;q-parent=p;q-left=NULL;else
21、 q-rtag=1;p-left = q;q-parent=p;p-left-parent=q; temp=inpre(p); temp-right=q; else q = new ThreadBinaryNode(value, p, p-right);if(p-rtag=1)q-ltag=q-rtag=1;p-rtag=0; p-right = q;q-parent=p;else q-ltag=1;p-right = q;q-parent=p;p-right-parent=q; temp=innext(p); temp-left=q; return q; /插入作为根结点template T
22、hreadBinaryNode* ThreadBinaryTree:insertroot(char value,bool rootleft) ThreadBinaryNode *p=this-root; ThreadBinaryNode *q=new ThreadBinaryNode(value);if(p=NULL) p=q; p-ltag=p-rtag=1; p-parent=NULL;else if(rootleft)this-root-parent=q;q-left=this-root;q-rtag=1; ThreadBinaryNode *temp=this-findlast();t
23、emp-rtag=1;temp-right=q; this-root=q;else this-root-parent=q;q-right=this-root;q-ltag=1; ThreadBinaryNode *temp=this-findfirst();temp-ltag=1;temp-left=q; this-root=q;return this-root;template ThreadBinaryNode* ThreadBinaryTree:findlast() ThreadBinaryNode *q=this-root;while (q!=NULL & q-ltag=0) q=q-l
24、eft; while (innext(q)!=NULL) q=innext(q); return q;template ThreadBinaryNode* ThreadBinaryTree:findfirst() ThreadBinaryNode *q=this-root;while (q!=NULL & q-ltag=0) q=q-left; /*while (innext(q)!=NULL) q=innext(q); */return q;/、主程序main#include #include ThreadBinaryTree.h int main() char prelist = A,B,
25、D,NULL,NULL,E,G,NULL,NULL,NULL,C,F,NULL,H,NULL,NULL,K; cout构造好的二叉树遍历如下:endl; ThreadBinaryTreetbitree(prelist,17); tbitree.inorder();char value=A; ThreadBinaryNode *find=tbitree.search(value);/find为根节点char Evalue=E; ThreadBinaryNode *Efind=tbitree.search(Evalue);/find为根节点char hvalue=D; ThreadBinaryNo
26、de *lnode=tbitree.search(hvalue);/lnode为二度节点coutn删除值为value的结点后的二叉树的遍历为:endl;tbitree.remove(find);tbitree.inorder();char lvalue=M; coutn插入在hvalue左边值为lvalue的结点后的二叉树的遍历为:endl;tbitree.insert(lnode,lvalue,true); tbitree.inorder(); char mvalue=Z; coutn根处插入值为mvalue的结点后的二叉树的遍历为:endl; tbitree.insertroot(mval
27、ue,true); /tbitree.insertroot(mvalue,false); tbitree.inorder(); char jvalue=F; ThreadBinaryNode *lfind=tbitree.search(jvalue);/find为根节点coutn删除值为jvalue的结点后的二叉树的遍历为:endl;tbitree.remove(lfind); tbitree.inorder(); char kvalue=T; coutn插入在Evalue左边值为kvalue的结点后的二叉树的遍历为:endl;tbitree.insert(Efind,kvalue,false); tbitree.inorder(); return 0;