吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 1214|回复: 1
收起左侧

[求助] 线索二叉树的线索化

[复制链接]
ing 发表于 2020-5-16 19:38


为什么执行 pre=p 后,pre的左右孩子和 p 不同?
捕获0.PNG
捕获.PNG
捕获2.PNG



调试的输入:ABDH##I##EJ###CF##G##
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

#define OK 1
#define ERROR 0

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;  /* Link==0表示指向左右孩子指针, */
/* Thread==1表示指向前驱或后继的线索 */
typedef  struct BiThrNode   /* 二叉线索存储结点结构 */
{
    TElemType data; /* 结点数据 */
    struct BiThrNode *lchild, *rchild;  /* 左右孩子指针 */
    PointerTag LTag;
    PointerTag RTag;        /* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil='#'; /* 字符型以空格符为空 */

Status visit(TElemType e)
{
    printf("%c ",e);
    return OK;
}

/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{
    TElemType h;
    scanf("%c",&h);

    if(h==Nil)
        *T=NULL;
    else
    {
        *T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=h; /* 生成根结点(前序) */
        CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
        if((*T)->lchild) /* 有左孩子 */
            (*T)->LTag=Link;
        CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
        if((*T)->rchild) /* 有右孩子 */
            (*T)->RTag=Link;
    }
    return OK;
}

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
    if(p)
    {
        InThreading(p->lchild); /* 递归左子树线索化 */
        if(!p->lchild) /* 没有左孩子 */
        {
            p->LTag=Thread; /* 前驱线索 */
            p->lchild=pre; /* 左孩子指针指向前驱 */
        }
        if(!pre->rchild) /* 前驱没有右孩子 */
        {
            pre->RTag=Thread; /* 后继线索 */
            pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
        }
        pre=p; /* 保持pre指向p的前驱 */
        InThreading(p->rchild); /* 递归右子树线索化 */
    }
}

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    p=T->lchild; /* p指向根结点 */
    while(p!=T)
    { /* 空树或遍历结束时,p==T */
        while(p->LTag==Link)
            p=p->lchild;
        if(!visit(p->data)) /* 访问其左子树为空的结点 */
            return ERROR;
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            visit(p->data); /* 访问后继结点 */
        }
        p=p->rchild;
    }
    return OK;
}

int main()
{
    pre = (BiThrTree)malloc(sizeof(BiThrNode));
    pre->lchild = NULL;
    pre->rchild = NULL;
    BiThrTree T;
    CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InThreading(T);
    InOrderTraverse_Thr(T); /* 中序遍历(输出)二叉线索树 */
    printf("\n");

    return 0;
}

免费评分

参与人数 1吾爱币 +1 热心值 +1 收起 理由
Corina + 1 + 1 我很赞同!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

天上飞来一只 发表于 2020-5-16 21:04
本帖最后由 天上飞来一只 于 2020-5-16 21:10 编辑

[C] 纯文本查看 复制代码
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include "string.h"
#include "stdio.h"   
#include "stdlib.h"  
#include "io.h" 
#include "math.h" 
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
#define MAXSIZE 100 /* 存储空间初始分配量 */
 
typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;        /* Link==0表示指向左右孩子指针, */
                                                                                /* Thread==1表示指向前驱或后继的线索 */
typedef  struct BiThrNode        /* 二叉线索存储结点结构 */
{
        TElemType data;        /* 结点数据 */
        struct BiThrNode *lchild, *rchild;        /* 左右孩子指针 */
        PointerTag LTag;
        PointerTag RTag;                /* 左右标志 */
} BiThrNode, *BiThrTree;
 
TElemType Nil='#'; /* 字符型以空格符为空 */
 
Status visit(TElemType e)
{
        printf("%c ",e);
        return OK;
}
 
/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{
        TElemType h;
        scanf("%c",&h);
 
        if(h==Nil)
                *T=NULL;
        else
        {
                *T=(BiThrTree)malloc(sizeof(BiThrNode));
                if(!*T)
                        exit(OVERFLOW);
                (*T)->data=h; /* 生成根结点(前序) */
                CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
                if((*T)->lchild) /* 有左孩子 */
                        (*T)->LTag=Link;
                CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
                if((*T)->rchild) /* 有右孩子 */
                        (*T)->RTag=Link;
        }
        return OK;
}
 
BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
        if(p)
        {
                InThreading(p->lchild); /* 递归左子树线索化 */
                if(!p->lchild) /* 没有左孩子 */
                {
                        p->LTag=Thread; /* 前驱线索 */
                        p->lchild=pre; /* 左孩子指针指向前驱 */
                }
                if(!pre->rchild) /* 前驱没有右孩子 */
                {
                        pre->RTag=Thread; /* 后继线索 */
                        pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
                }
                pre=p; /* 保持pre指向p的前驱 */
                InThreading(p->rchild); /* 递归右子树线索化 */
        }
}
/*--------------------------------------------------------------注意-----------------------------------------------------------*/
/*注意 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{
        *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!*Thrt)
                exit(OVERFLOW);
        (*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 OK;
}
/*--------------------------------------------------------------注意end-----------------------------------------------------------*/
/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
        BiThrTree p;
        p=T->lchild; /* p指向根结点 */
        while(p!=T)
        { /* 空树或遍历结束时,p==T */
                while(p->LTag==Link)
                        p=p->lchild;
                if(!visit(p->data)) /* 访问其左子树为空的结点 */
                        return ERROR;
                while(p->RTag==Thread&&p->rchild!=T)
                {
                        p=p->rchild;
                        visit(p->data); /* 访问后继结点 */
                }
                p=p->rchild;
        }
        return OK;
}
 
int main()
{
        BiThrTree H,T;
        printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
         CreateBiThrTree(&T); /* 按前序产生二叉树 */
        InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
        printf("中序遍历(输出)二叉线索树:\n");
        InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
        printf("\n");
         
        return 0;
}
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2025-1-22 11:14

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表