数据结构中序线索二叉树

数据结构中序线索二叉树数据结构中序线索二叉树 //线索二叉树的三叉链表结点类 template class ThreadBinaryNode { public: T data; ThreadBinaryNode*left,*right,*parent; int ltag,rtag; ThreadBinaryNode(T data,ThreadBinaryNode*left=NULL,ThreadBinaryNode*right=NULL,ThreadBinaryNod e*parent=NULL) { this-...

数据结构中序线索二叉树 //线索二叉树的三叉链表结点类 template class ThreadBinaryNode { public: T data; ThreadBinaryNode*left,*right,*parent; int ltag,rtag; ThreadBinaryNode(T data,ThreadBinaryNode*left=NULL,ThreadBinaryNode*right=NULL,ThreadBinaryNod e*parent=NULL) { this->data=data; this->left=left; this->right=right; this->parent=parent; this->ltag=this->rtag=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*insert(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,ThreadBinaryNode*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结点为根的子树 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 prelist[], int n, int &i,ThreadBinaryNode*t) { //以标明空子树的先根序列创建一棵子树，算法同BinaryTree ThreadBinaryNode *p=NULL; if (i(elem); p->parent=t; p->left = create(prelist,n,i,p); p->right = create(prelist,n,i,p); } } return p; } template ThreadBinaryNode* ThreadBinaryTree::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, ThreadBinaryNode* &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的线索 front=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() //中根次序遍历中序线索二叉树，非递归算法 { cout<<"中根次序遍历中序线索二叉树: "; ThreadBinaryNode *p=root; while (p!=NULL && p->ltag==0) //寻找根的最左边的后代结点，即第一个访问结点 p=p->left; while (p!=NULL) { cout<data<<" "; p=innext(p); //返回p在中根次序下的后继结点 } cout< ThreadBinaryNode* ThreadBinaryTree::search(T value) //查找首次出现的值为value结点 { return search(root, value); } template 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==NULL && p->rtag==0) //若在左子树中未找到 find = search(p->right, value); //则继续在右子树中查找，递归调用 } return find; //返回查找结果 } template ThreadBinaryTree::~ThreadBinaryTree() //析构函数 { destroy(root); cout< void ThreadBinaryTree::destroy(ThreadBinaryNode *p) //撤销以p结点为根的子树 { //递归算法的后根次序遍历 if (p!=NULL) { if (p->ltag==0) destroy(p->left); 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->parent=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);//找到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; delete 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 *temp2=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; 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; 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::insert(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 { 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 ThreadBinaryNode* 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(); temp->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->left; 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','D',NULL,NULL,'E','G',NULL,NULL,NULL,'C','F',NULL,'H',NULL,NULL,'K'}; cout<<"构造好的二叉树遍历如下:"<tbitree(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'; ThreadBinaryNode *lnode=tbitree.search(hvalue);//lnode为二度节点 cout<<"\n删除值为"< *lfind=tbitree.search(jvalue);//find为根节点 cout<<"\n删除值为"<

                    本文档为【数据结构中序线索二叉树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构中序线索二叉树

你可能还喜欢