数据结构中线索二叉树.doc

《数据结构中线索二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//线索二叉树的三叉链表结点类templateclassThreadBinaryNode{public:Tdata;ThreadBinaryNode*left,*right,*parent;intltag,rtag;ThreadBinaryNode(Tdata,ThreadBinaryNode*left=NULL,ThreadBinaryNode*right=NULL,ThreadBinaryNode*parent=NULL){this->data=data;this->left=left;this->right=right;thi

2、s->parent=parent;this->ltag=this->rtag=0;}};////ThreadBinaryNode.h#include"ThreadBinaryNode.h"templateclassThreadBinaryTree//中序线索二叉树类{public:ThreadBinaryNode*root;ThreadBinaryTree(Tprelist[],intn);//以标明空子树的先根序列构造一棵中序线索二叉树ThreadBinaryNode*search(Tvalue);//查找值为value的结点,返回节点Thr

3、eadBinaryNode*inpre(ThreadBinaryNode*p);ThreadBinaryNode*insert(ThreadBinaryNode*p,Tvalue,boolleftChild=true);//插入value作为p结点的孩子ThreadBinaryNode*insertroot(charvalue,boolrootleft);ThreadBinaryNode*findlast();ThreadBinaryNode*findfirst();~ThreadBinaryTree();voidinorder(

4、);//中根次序遍历中序线索二叉ThreadBinaryNode*create(Tprelist[],intn,int&i,ThreadBinaryNode*t);//以标明空子树的先根次序遍历序列创建一棵子树voidinThread(ThreadBinaryNode*p,ThreadBinaryNode*&front);//中序线索化以p结点为根的子树ThreadBinaryNode*search(ThreadBinaryNode*p,Tvalue);//在以p为根的子树中查找首次出现的值为value的结点ThreadBinaryNo

5、de*innext(ThreadBinaryNode*p);//返回p在中根次序下的后继结点voiddestroy(ThreadBinaryNode*p);//撤销以p结点为根的子树voidremove(ThreadBinaryNode*p);//删除};templateThreadBinaryTree::ThreadBinaryTree(Tprelist[],intn){//以标明空子树的先根序列构造一棵中序线索二叉树inti=0;ThreadBinaryNode*p=NULL;root=create(prelist,

6、n,i,p);ThreadBinaryNode*front=NULL;inThread(root,front);//中序线索化二叉树}templateThreadBinaryNode*ThreadBinaryTree::create(Tprelist[],intn,int&i,ThreadBinaryNode*t){//以标明空子树的先根序列创建一棵子树，算法同BinaryTreeThreadBinaryNode*p=NULL;if(i

7、hreadBinaryNode(elem);p->parent=t;p->left=create(prelist,n,i,p);p->right=create(prelist,n,i,p);}}returnp;}templateThreadBinaryNode*ThreadBinaryTree::inpre(ThreadBinaryNode*p){ThreadBinaryNode*q=this->root;ThreadBinaryNode*temp=NULL;while(q!