后序线索⼆叉树
后序线索⼆叉树
后序线索⼆叉树的构造
三叉链表结构
结构体要⽤三叉链表，因为在遍历中序线索⼆叉树的时候需要到某个节点的后继结点，对于右孩⼦来讲，其后继结点即为它的双亲，所以需要到其双亲结点，故要⽤三叉链表
bool CreateThreadTree(ThreadTree &T, ThreadTree parent)树的创建需要多加⼀个parent参数，对于根节点的parent置为NULL, 在创建树的时候就传⼊NULL作为参数
后序线索⼆叉树和中序，前序有所不同，需要特别注意
typedef struct ThreadNode{
ElemType data;//数据元素
struct ThreadNode *lchild,*rchild,*parent;//左右孩⼦指针，指向双亲的指针@@@
int ltag;//
int rtag;//左右线索标记
}ThreadNode,*ThreadTree;
PostThread
后序线索⼆叉树的构造， 左右根
注意体会@@@处的作⽤
//后序线索⼆叉树的构造，左右根
void PostThread(ThreadTree &p,ThreadTree &pre){
if(p){
if(p->ltag !=1)//@@@  这⾥因为p->lchild可能是p的前驱结点，//如果不判断ltag，则会死循环，
PostThread(p->lchild,pre);//递归，线索化左⼦树
if(p->rtag !=1)//@@@
PostThread(p->rchild, pre);//递归，线索化右⼦树
if(p->lchild ==NULL){//左⼦树为空，建⽴前驱线索
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&& pre->rchild==NULL){
pre->rchild=p;//建⽴前驱结点的后继线索
pre->rtag=1;
}
pre=p;//标记当前结点成为刚刚访问过的结点
}//if(p != NULL)
}
CreatePostThread
通过后序遍历建⽴后序线索⼆叉树：
注意：因为后序遍历根为最后⼀个被遍历的结点，所以不能简单地⽤pre->rchild==NULL；⽽是需要判断其有⽆右孩⼦
//通过后序遍历建⽴后序线索⼆叉树的主过程算法如下：
void CreatePostThread(ThreadTree &T){
ThreadTree pre=NULL;
if(T){//⾮空⼆叉树，线索化
PostThread(T,pre);//线索化⼆叉树
/*
pre->rchild==NULL;//处理遍历的最后⼀个结点
pre->rtag=1;
*/
if(pre->rchild==NULL){//@@@
//因为后序遍历的处理遍历的最后⼀个结点是整颗树的根节点，
//所以不能简单地pre->rchild==NULL
pre->rtag=1;
}
else{
pre->rtag=0;
}
/
/printf("CreatePostThread Finished\n");
}
}
后序线索⼆叉树的遍历
Firstnode
求后序线索⼆叉树中，后序序列下的第⼀个结点
思路：
1. 先到最左下结点，但此结点不⼀定是叶⼦结点，因 为它可能有右孩⼦，但是没有左孩⼦
2. 再看它有⽆右孩⼦，有则 重复 1. ，即递归Firstnode
3. ⽆右孩⼦，说明它就是要的结点，return p
//求后序线索⼆叉树中，后序序列下的第⼀个结点
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0){//先⾛到最左下结点，不⼀定是叶⼦结点，
p=p->lchild;//因为它可能有右孩⼦，⽽没有左孩⼦
}
if(p->rtag ==0){//再看它有⽆右孩⼦，若有右孩⼦，则递归Firstnode
Firstnode(p->rchild);
}
else{//若⽆右孩⼦，说明它为要的结点，return
return p;
}
}
Nextnode
求后序线索⼆叉树中，结点p在后序序列下的后继
1.先判断有⽆双亲，⽆双亲说明为根节点，即后序遍历的最后⼀个结点
2.有双亲则看它⽗节点有⽆右孩⼦，且⾃⼰不是右孩⼦，(如果⾃⼰就是那个右孩⼦的话，递归的话会死循环，因为他们之间的
指针形成了个圈)，
若⽗节点有右孩⼦，则Fistenode(⽗节点的右孩⼦), 即到⽗节点右孩⼦(⽗节点的右孩⼦可能是⼀棵⼩型⼦树)的后续遍历的第⼀个结点
3.若⽗节点⽆右孩⼦，说明应该遍历⽗节点了。任何结点都有⽗节点(除了根节点)
//求后序线索⼆叉树中，结点p在后序序列下的后继
ThreadNode *Nextnode(ThreadNode *p){
if(!p->parent){//说明p⽆双亲，p为根节点
printf("根节点在后序遍历中为最后⼀个结点\n");
return NULL;
}
if(p->parent->rtag==0&&**p->parent->rchild != p**){//右孩⼦指针
return Firstnode(p->parent->rchild);
}
else{// ltag==1 直接返回后继线索
return p->parent;
}
}
完整测试代码c++
/
/后序线索⼆叉树
#include<stdio.h>
#include<stdlib.h>
#define ElemType char
//tag为0表⽰指向左/右孩⼦，为1表⽰指向结点的前驱/后继
typedef struct ThreadNode{
ElemType data;//数据元素
struct ThreadNode *lchild,*rchild,*parent;//左右孩⼦指针，指向双亲的指针@@@
int ltag;//
int rtag;//左右线索标记
}ThreadNode,*ThreadTree;
void visit(ThreadTree T){
printf("%c ",T->data);
}
//后序线索⼆叉树的构造，左右根
void PostThread(ThreadTree &p,ThreadTree &pre){
if(p){
if(p->ltag !=1)//@@@  这⾥因为p->lchild可能是p的前驱结点，//如果不判断ltag，则会死循环，PostThread(p->lchild,pre);//递归，线索化左⼦树
if(p->rtag !=1)//@@@
PostThread(p->rchild, pre);//递归，线索化右⼦树
if(p->lchild ==NULL){//左⼦树为空，建⽴前驱线索
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&& pre->rchild==NULL){
pre->rchild=p;//建⽴前驱结点的后继线索
pre->rtag=1;
}
pre=p;//标记当前结点成为刚刚访问过的结点
}//if(p != NULL)
}
//通过后序遍历建⽴后序线索⼆叉树的主过程算法如下：
void CreatePostThread(ThreadTree &T){
ThreadTree pre=NULL;
if(T){//⾮空⼆叉树，线索化
PostThread(T,pre);//线索化⼆叉树
/*
pre->rchild==NULL;//处理遍历的最后⼀个结点
pre->rtag=1;
*/
if(pre->rchild==NULL){
//因为后序遍历的处理遍历的最后⼀个结点是整颗树的根节点，
//所以不能简单地pre->rchild==NULL
pre->rtag=1;
}
else{
else{
pre->rtag=0;
}
//printf("CreatePostThread Finished\n");
}
}
//求后序线索⼆叉树中，后序序列下的第⼀个结点
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0){//先⾛到最左下结点的结点，不⼀定是叶⼦结点，
p=p->lchild;//因为它可能有右孩⼦，⽽没有左孩⼦
}
if(p->rtag ==0){//再看它有⽆右孩⼦，若有右孩⼦，则递归Firstnode
Firstnode(p->rchild);
}
else{//若⽆右孩⼦，说明它为要的结点，return
return p;
}
}
//求后序线索⼆叉树中，结点p在后序序列下的后继
ThreadNode *Nextnode(ThreadNode *p){
if(!p->parent){//说明p⽆双亲，p为根节点
//printf("根节点在后序遍历中为最后⼀个结点\n");
return NULL;
}
if(p->parent->rtag==0&& p->parent->rchild != p){
//右孩⼦指针，且右孩⼦不是⾃⼰，说明⾃⼰是左孩⼦  @@@先序中序后序遍历二叉树
return Firstnode(p->parent->rchild);
}
else{// ltag==1 直接返回后继线索
return p->parent;
}
}
利⽤上⾯的两个算法，可以写出不含头结点的后序线索⼆叉树的后序遍历算法void Postorder(ThreadNode *T){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
visit(p);
}
}
//创建线索⼆叉树，按前序输⼊， #表⽰空节点
bool CreateThreadTree(ThreadTree &T, ThreadTree parent){
ElemType ch;
scanf("%c",&ch);
if(ch =='#'){
//printf("您要创建⼀棵空树吗？\n");
T=NULL;
return false;
}
else{
T=(ThreadTree)malloc(sizeof(ThreadNode));
T->ltag=T->rtag=0;
if(!T){
printf("malloc failure\n");
return false;
}
T->data = ch;
T->parent = parent;
CreateThreadTree(T->lchild,T);
CreateThreadTree(T->rchild,T);
return true;
}
}
//后序销毁左右根
//后序销毁左右根
bool DestroyThreadTree(ThreadTree T){
if(T==NULL){
printf("空节点\n");
return false;
}
if(T->ltag!=1){//@@@说明左指针指向的是孩⼦结点，⽽⾮线索标志
DestroyThreadTree(T->lchild);
}
//printf("%c->rtag %d\n",T->data,T->rtag);
if(T->rtag!=1){//@@@
DestroyThreadTree(T->rchild);
}
printf("销毁%c\n",T->data);
free(T);//@@@'
T=NULL;
return true;
}
//后序递归遍历线索⼆叉树
void PostOrder(ThreadTree T){
if(T){
if(T->ltag!=1)
PostOrder(T->lchild);
if(T->rtag !=1)
PostOrder(T->rchild);
visit(T);
}
}
int main(){
ThreadTree T=NULL;
printf("按前序输⼊⼆叉树中节点的值(输⼊#表⽰空节点)\n"); CreateThreadTree(T,NULL);//输⼊前序，建⽴⼆叉树
CreatePostThread(T);//通过后序遍历建⽴先序线索⼆叉树
ThreadNode *p=Firstnode(T);//求后序遍历下的第⼀个结点
printf("\n后序遍历的第⼀个结点p: %c\n",p->data);
ThreadNode* r=Nextnode(p);//求后序遍历下p的后继
printf("p的后继r: %c\n",r->data);
printf("后序遍历线索⼆叉树(递归PostOrder ≈正常BinaryTree遍历): \n"); PostOrder(T);
printf("\n");
printf("\n后序遍历线索⼆叉树(⾮递归Postorder ≈ Firstnode+Nextnode): \n"); Postorder(T);
printf("\n⽤完要记得销毁哦!\n");
DestroyThreadTree(T);
return0;
}
测试样例1

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。