| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 900 人关注过本帖
标题:中序线索化二叉树出错
只看楼主 加入收藏
大虫归来
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2011-11-14
结帖率:50%
收藏
 问题点数:0 回复次数:2 
中序线索化二叉树出错
    求指教,中序线索化二叉树后,二叉树中左子树指向的前驱和右子树指向的后继的指针还为空,比如按先序遍历输入二叉树AB##CD##E##,#为空结点。void MidThreadTree(ThreadTree T,ThreadTree pre)中那个地主有问题,求分析
程序代码:
#include <stdio.h>
#include <stdlib.h>

typedef enum _PointerTag{
    Link,    //Link=0指针
        Thread    //Thread线索
}PointerTag;

typedef struct _ThreadNode{
    char elem;
    PointerTag ltag,rtag;
    struct _ThreadNode *lchild,*rchild;
}ThreadNode,*ThreadTree;

/*
创建二叉树
*/
void CreateThreadTree(ThreadTree *T)
{
    char ch;
   
    ch = getchar();
   
    if(ch == '#')*T = NULL;
    else
    {
        *T = (ThreadNode *)malloc(sizeof(ThreadNode));
        printf("0x%x\r\n",*T);
        (*T)->elem = ch;
        CreateThreadTree(&((*T)->lchild));
        CreateThreadTree(&((*T)->rchild));
    }   
}

/*
先序遍历二叉树
*/
void PreThreadTreeOrder(ThreadTree T)
{
    if(T)
    {
        printf("%3c",T->elem);
        PreThreadTreeOrder(T->lchild);
        PreThreadTreeOrder(T->rchild);
    }
}

/*
中序遍历二叉树
*/
void MidThreadTreeOrder(ThreadTree T)
{
    if(T)
    {
        MidThreadTreeOrder(T->lchild);
        printf("%3c",T->elem);
        MidThreadTreeOrder(T->rchild);
    }
}

/*
后序遍历二叉树
*/
void PostThreadTreeOrder(ThreadTree T)
{
    if(T)
    {
        PostThreadTreeOrder(T->lchild);
        PostThreadTreeOrder(T->rchild);
        printf("%3c",T->elem);
    }
}

/*
中序线索化二叉树
*/
void MidThreadTree(ThreadTree T,ThreadTree pre)
{
    if(T)
    {
        //printf("pre = 0x%x\r\n",pre);
        MidThreadTree(T->lchild,pre);
       
        if(T->lchild == NULL)
        {
            T->ltag = Thread;
            T->lchild = pre;
        }
        else T->ltag = Link;
       
        if(T->rchild == NULL)T->rtag = Thread;
        else T->rtag = Link;

        if(pre)
        {
            if(pre->lchild == NULL)pre->ltag = Thread;
            else pre->ltag = Link;

            if(pre->rchild == NULL)pre->rtag = Thread;
            else pre->rtag = Link;
           
            if(pre && pre->rtag == Thread)pre->rchild = T;
        }       
        pre = T;
       
        MidThreadTree(T->rchild,pre);
    }
}

/*
在中序线索化二叉树中寻找结点的前驱
*/
ThreadTree MidFindPreElem(ThreadTree T)
{
    ThreadTree pre;
   
    pre = T->lchild;
    if(T->ltag == Thread)return pre;
    else
    {
        while(pre->rtag == Link)
        {
            pre = pre->rchild;
        }
    }
   
    return pre;
}

/*
在中序线索化二叉树中寻找结点的后继
*/
ThreadTree MidFindNextElem(ThreadTree T)
{
    ThreadTree next;
   
    next = T->rchild;
    if(T->rtag == Thread)return next;
    else
    {
        while(next->ltag == Link)
        {
            next = next->lchild;
        }
    }
   
    return next;
}

/*
遍历中序线索化二叉树
*/
void MidThreadTreeTraverse(ThreadTree T)
{
    ThreadTree p;

    if(T)
    {
        p = T;
        while(p->ltag == Thread)p = p->lchild;
        while(p)
        {           
            printf("%3c\r\n",p->elem);
            printf("0x%x",p);
            p = MidFindNextElem(p);
            printf("\t0x%x\r\n",p);
        }
    }
}

/*
寻找中序线索化二叉树中的某个结点
*/
ThreadTree MidFindThreadTreeElem(ThreadTree T,char elem)
{
    ThreadTree p;
   
    if(T)
    {
        p = T;
        while(p->ltag == Thread)p = p->lchild;
        while(p && p->elem != elem)
        {
            p = MidFindNextElem(p);
        }
    }
   
    return p;
}

void OperateThreadTree(void)
{
    ThreadTree T,p,pre=NULL;
   
    printf("按先序次序输入二叉树的结点(结点为字符,字符'#'表示空树):\r\n");
    CreateThreadTree(&T);
    printf("先序遍历二叉树的结点: \r\n");
    PreThreadTreeOrder(T);
    printf("\r\n");
    printf("中序遍历二叉树的结点: \r\n");   
    MidThreadTreeOrder(T);
    printf("\r\n");
    printf("后序遍历二叉树的结点: \r\n");
    PostThreadTreeOrder(T);
    printf("\r\n");
   
    p = T;
    printf("AAAAAAAAAAAAAAAAAA\r\n");
    printf("pre = 0x%x\r\n",pre);
    printf("0x%x\r\n",T);
    printf("0x%x\r\n",T->lchild);
    printf("0x%x\r\n",T->lchild->lchild);

    MidThreadTree(T,pre);
   
    printf("\r\n\r\n");
    printf("BBBBBBBBBBBBBBBBBB\r\n");
    printf("pre = 0x%x\r\n",pre);
    printf("0x%x\r\n",T);
    printf("0x%x\r\n",T->lchild);
    printf("0x%x\r\n",T->lchild->lchild);

    printf("中序线索二叉树的遍历:\r\n");
    MidThreadTreeTraverse(T);
    printf("\r\n");
   
}

int main(void)
{
    OperateThreadTree();
   
    return NULL;
}

搜索更多相关主题的帖子: 二叉树 color 地主 
2013-12-18 22:07
菜鸟学习篇
Rank: 2
等 级:论坛游民
帖 子:8
专家分:39
注 册:2013-12-18
收藏
得分:0 
帅哥  你的问题主要有两点  第一:PRE一定要是一个全局变量,你这么写会在函数结束的时候弾栈出去,就会清零。第二: if(pre && pre->rtag == Thread)pre->rchild = T;你有了右子树的判断,为什么没有左子树。。。也就是 你的前驱会丢失吧,
2013-12-19 20:24
大虫归来
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2011-11-14
收藏
得分:0 
我的本意是编写中序线索化二叉树开头元素的前驱为空,结尾元素的后继为空。理解的还不到位,我再仔细想,谢谢楼上啊
2013-12-19 22:35
快速回复:中序线索化二叉树出错
数据加载中...
 
   



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

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