搜索
编程论坛 → 开发语言 → 『 数据结构与算法 』 → 带头结点的双向二叉线索树的线索化及其遍历问题，还有后序的不能完成，谁来帮帮忙？
标题：带头结点的双向二叉线索树的线索化及其遍历问题，还有后序的不能完成，谁来 ...
只看楼主
xichong
Rank: 7Rank: 7Rank: 7
来　自：四川南充
等　级：黑侠
威　望：2
帖　子：146
专家分：582
注　册：2009-6-10
结帖率：100%
楼主
 已结贴√  问题点数：50 回复次数：1 
带头结点的双向二叉线索树的线索化及其遍历问题，还有后序的不能完成，谁来帮帮忙？
#include <stdio.h>//测试值：abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrNode *pre;//全局变量
////////
BiThrTree CreatBiThrTree()//先序创建二叉树
{
    TElemType ch;
    BiThrTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(0);
        T->data=ch;
        ////
        T->LTag=Link;
        T->RTag=Link;
        /////////////indispensable**
        T->lchild=CreatBiThrTree();
        T->rchild=CreatBiThrTree();
    }
    return T;
}
void Visit(char data)
{
    printf("%c",data);
}
/////////////////////////////////////////////////////

void PreThreading(BiThrNode *p)//先遍历二叉树
{
    if (p)
    {
        if (!p->lchild)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (!p->rchild)
            p->RTag = Thread;
        if (pre&&pre->RTag==Thread)
            pre->rchild = p;
        pre=p;
        if (p->LTag==Link)
            PreThreading(p->lchild);
        if (p->RTag==Link)
            PreThreading(p->rchild);
    }
}
BiThrNode* PreOrderThreading(BiThrNode *T)//先序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        PreThreading(T);//先序遍历进行先序线索化
        pre->rchild=Thrt;//最后一个结点线索化
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
    return(Thrt);
}

void PreorderTraverse_Thr(BiThrNode *T)//**先序**遍历线索二叉树
{
        //遍历先序线索二叉树
    BiThrTree p=T->lchild;//
    Visit(p->data);
    while (p->rchild!=T)//根左右
    {
       if (p->LTag==Link)
            p=p->lchild;
       else
            p=p->rchild;
        Visit(p->data);
    }
}



//////////////////////////////////////////////////////////
void InThreading(BiThrNode *p)//中序遍历二叉树
{
    if(p)
    {
        InThreading(p->lchild);//左子树线索化
        if(!p->lchild)//前驱线索
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if(!pre->rchild)//后继线索
        {
            pre->RTag=Thread;
            pre->rchild=p;
        }
        pre=p;//保持pre指向p的前驱
        InThreading(p->rchild);//右子树线索化
    }
}
BiThrNode* InOrderThreading(BiThrNode *T)//中序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        InThreading(T);//中序遍历进行中序线索化
        pre->rchild=Thrt;//最后一个结点线索化
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
    return(Thrt);
}
void InorderTraverse_Thr(BiThrNode *T)//(forward)中序遍历线索二叉树
{
    BiThrNode *p;
    p=T->lchild;
    while(p!=T)//空树或遍历结束时,p=T
    {
        while(p->LTag==Link)
            p=p->lchild;
        Visit(p->data);//访问左子树为空的结点
        while(p->RTag==Thread&&p->rchild!=T)//访问后继结点p->rchild!=T
        {
            p=p->rchild;
            Visit(p->data);
        }
        p=p->rchild;
    }
}
void BackInorderTraverse_Thr(BiThrNode *T)//(back)中序遍历线索二叉树
{
    BiThrNode *p;
    p=T->rchild;
    while(p!=T)
    {
        while(p->LTag==Thread&&p->lchild!=T)
        {
            Visit(p->data);//访问中序遍历的最后一个结点
            p=p->lchild;//直接访问其前驱
        }
        Visit(p->data);//访问根节点
        p=p->lchild;//转向左子树
        while(p->RTag==Link)
            p=p->rchild;//找到左子树在中序遍历时的最后一个结点，进入下一次循环
    }
}

//////////////////////////////////////////////////////
void AfterThreading(BiThrNode *p)//后序遍历二叉树
{
    if (p)
    {
        AfterThreading(p->lchild);
        AfterThreading(p->rchild);
        if (!p->lchild)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (!p->rchild)
            p->RTag=Thread;
        if (pre&&pre->RTag==Thread)
            pre->rchild=p;
        pre=p;
    }
}
BiThrNode* AfterOrderThreading(BiThrNode *T)//后序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        AfterThreading(T);//后序遍历进行先序线索化
    //    pre->rchild=Thrt;//
    //    pre->RTag=Thread;
    //    Thrt->rchild=pre;
    }
    return(Thrt);
    printf("*********!\n");
}

void AfterorderTraverse_Thr(BiThrNode *T)//**后序**遍历线索二叉树
{
        //遍历后序线索二叉树
    BiThrTree p=T->lchild;//
    Visit(p->data);
    while (p->rchild!=T)//左右根
    {
        if (p->LTag==Link)
            p=p->lchild;
        if(p->RTag==Thread)//直接后继结点
        {
            p=p->lchild;
            Visit(p->data);
        }
        if(p->LTag==Thread&&p->RTag==Link)//左儿子空，右儿子不空，访问右儿子
        {
            p=p->rchild;
            Visit(p->data);
        }
        if(p->LTag==Thread&&p->RTag==Thread)//左儿子空，右儿子空，访问根结点
            Visit(p->data);
    }
}
void main()
{
    BiThrNode *t,*thr;
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<说明：例如参考数据为:abc@@de@g@@f@@@，则用空格键表示@,输完后再输入一个回车键.>\n");
    t=CreatBiThrTree();
    printf("中序线索化二叉树...\n");
    thr=InOrderThreading(t);
    printf("线索化工作已经完成!\n");
    printf("中序(前向)遍历中序线索二叉树:\n");
    InorderTraverse_Thr(thr);
    printf("\n");
    printf("中序(逆向)遍历中序线索二叉树:\n");
    BackInorderTraverse_Thr(thr);
    printf("\n");
    printf("先序线索化二叉树...\n");
    thr=PreOrderThreading(t);
    printf("先序遍历先序线索二叉树:\n");
    PreorderTraverse_Thr(thr);
    printf("\n");
    printf("后序线索化二叉树...\n");
    thr=AfterOrderThreading(t);
    printf("后序遍历后序线索二叉树:\n");
    AfterorderTraverse_Thr(thr);
    printf("\n");
}
搜索更多相关主题的帖子: 遍历　结点　线索　
2010-05-13 15:40
hzh512
Rank: 9Rank: 9Rank: 9
等　级：蜘蛛侠
威　望：6
帖　子：234
专家分：1333
注　册：2009-6-5
第 2 楼
 得分:50 
赞楼主，你把二叉树学了个遍。
给你后序遍历的。
程序代码：
#include <stdio.h>//测试值：abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild, *parent;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrNode *pre;//全局变量
////////
BiThrTree CreatBiThrTree(BiThrNode *par);//先序创建二叉树
void Visit(char data);
void AfterThreading(BiThrNode *p);//后序遍历二叉树
BiThrNode* AfterOrderThreading(BiThrNode *T);//后序线索化二叉树
void AfterorderTraverse_Thr(BiThrNode *T);//**后序**遍历线索二叉树
void main()
{
    BiThrNode *t,*thr=NULL;
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入空格键:\n");
    printf("<说明：例如参考数据为:abc@@de@g@@f@@@，则用空格键表示@,输完后再输入一个回车键.>\n");
    t=CreatBiThrTree(thr);

 printf("后序线索化二叉树...\n");
    thr=AfterOrderThreading(t);
    printf("后序遍历后序线索二叉树:\n");
    AfterorderTraverse_Thr(thr);
    printf("\n");
}

BiThrTree CreatBiThrTree(BiThrNode *par)//先序创建二叉树
{
    TElemType ch;
    BiThrTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(0);
        T->data=ch;
  T->parent = par;
        ////
        T->LTag=Link;
        T->RTag=Link;
        /////////////indispensable**
        T->lchild=CreatBiThrTree(T);
        T->rchild=CreatBiThrTree(T);
    }
    return T;
}
void AfterThreading(BiThrNode *p)//后序遍历二叉树
{
    if (p)
    {
        AfterThreading(p->lchild);
        AfterThreading(p->rchild);
        if (!p->lchild)
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if (!p->rchild)
            p->RTag=Thread;
        if (pre&&pre->RTag==Thread)
            pre->rchild=p;
        pre=p;
    }
}
BiThrNode* AfterOrderThreading(BiThrNode *T)//后序线索化二叉树
{
    BiThrNode *Thrt;
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
  T->parent=Thrt;
        pre=Thrt;
        AfterThreading(T);//后序遍历进行先序线索化
//  T->rchild = Thrt;
    //    pre->rchild=Thrt;//
    //    pre->RTag=Thread;
    //    Thrt->rchild=pre;
    }
    return(Thrt);
    printf("*********!\n");
}
void AfterorderTraverse_Thr(BiThrNode *T)//**后序**遍历线索二叉树
{
        //遍历后序线索二叉树
 BiThrTree p = T, q;

 while (p->rchild != NULL)

 {
  if (p->RTag == Thread)
  {
   p=p->rchild;
            Visit(p->data);
  }
  else
  {
   q= p->parent;
   if (q == T)
   {
    break;
   }
   else
   {
    if (q->RTag == Thread || q->rchild == p)
    {
     p = q;
     Visit(p->data);
    }
    else
    {
     q = q->rchild;
     while (q->LTag != Thread)
     {
      q = q->lchild;
     }
     p=q;
     Visit(p->data);
    }
   }
  }

 }
}
void Visit(char data)
{
    printf("%c",data);
}


编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段
2010-05-13 20:37



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-306509-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.019638 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved