V1EERIE
个人学习笔记
实验十 线索二叉树的操作

access_time
brush 524个字
whatshot 561 ℃
百度收录:无法查询

一、 实验目的

  1. 能够用高级语言描述二叉树的二叉线索存储结构;
  2. 能够用高级语言编写中序线索化二叉树的算法实现。

二、 实验内容

编程完成如下操作:

  1. 创建二叉链表表示的二叉树;
  2. 对创建的二叉树进行中序线索化;
  3. 按中序遍历创建的中序线索二叉树。
  4. 在中序线索二叉树中查找给定结点*p的中序序列中的后继的算法。
  5. 在中序线索二叉树中查找给定结点*p的中序序列中的前趋的算法。

三、 实验要求

  1. 假设二叉树的结点值是字符,先根据输入一棵二叉树标明空子树的完整先根遍历序列或者根据输入一棵二叉树的先根遍历序列和中根遍历序列或者根据输入一棵二叉树的后根遍历序列和中根遍历序列,建立一棵以二叉链表表示的二叉树,并输出建立后的二叉树的先根、中根、后根遍历序列,观察其建立的二叉树是否正确;
  2. 对上述建立的二叉树,进行中序线索化;
  3. 按中序遍历的顺序输出此中序线索二叉树;
  4. 在中序线索二叉树中查找给定结点*p的中序序列中的后继的算法;
  5. 在中序线索二叉树中查找给定结点*p的中序序列中的前趋的算法。

四、 源程序代码

#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef char TElemType;
typedef enum
{
    Link,
    Thread
} PointerTag;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

BiThrTree pre;

Status CreateTree(BiThrTree &T)
{
    char data;
    scanf("%c", &data);
    if (data != '#')
    {
        if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
        {
            printf("申请结点空间失败");
            return ERROR;
        }
        else
        {
            T->data = data;
            CreateTree(T->lchild);
            CreateTree(T->rchild);
        }
    }
    else
        T = NULL;
    return OK;
}

Status InThreading(BiThrTree p)
{

    if (p)
    {
        InThreading(p->lchild);
        if (!p->lchild)
        {
            p->LTag = Thread;
            p->lchild = pre;
        }
        else
            p->LTag = Link;
        if (!pre->rchild)
        {
            pre->RTag = Thread;
            pre->rchild = p;
        }
        else
            pre->RTag = Link;
        pre = p;
        InThreading(p->rchild);
    }
    return OK;
}

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
    if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
        return ERROR;
    Thrt->LTag = Link;
    Thrt->RTag = Thread;
    Thrt->data = -1;
    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;
}

Status InOrderThraverse_Thr(BiThrTree T)

{
    BiThrTree p = T->lchild;
    while (p != T)
    {
        while (p->LTag == Link)
            p = p->lchild;
        printf("%c", p->data);
        while (p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            printf("%c", p->data);
        }
        p = p->rchild;
    }
    printf("\n");
    return OK;
}

BiThrTree InorderNext(BiThrTree p)
{
    BiThrTree q;
    if (p->RTag == 1)
        return (p->rchild);
    else
    {
        for (q = p->rchild; q->LTag == 0; q = q->lchild)
            ;
        return (q);
    }
}

BiThrTree InorderPre(BiThrTree p)
{
    BiThrTree q;
    if (p->LTag == 1)
        return (p->lchild);
    else
    {
        for (q = p->lchild; q->RTag == 0; q = q->rchild)
            ;
        return (q);
    }
}

BiThrTree Search(BiThrTree T, TElemType x)
{
    BiThrTree p;
    if (T == NULL)
        return NULL;
    p = T;
    while (p->LTag == 0)
        p = p->lchild;
    while (p != T && p->data != x)
        p = InorderNext(p);

    if (p == T)
    {
        printf("Not Found the data!\n");
        return NULL;
    }
    else
        return p;
}

int main()
{
    BiThrTree T, Thrt, p, q, r;
    TElemType ch;
    printf("输入前序二叉树:\n");
    CreateTree(T);
    InOrderThreading(Thrt, T);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(Thrt);
    printf("请输入要查找的值:\n");
    getchar();
    scanf("%c", &ch);
    p = Search(Thrt, ch);
    if (p)
    {
        q = InorderNext(p);
        if (q->data == -1)
            printf("为中序遍历的最后一个结点,无后继\n");
        else
            printf("%c在中序遍历下的后继为%c\n", p->data, q->data);
        r = InorderPre(p);
        if (r->data == -1)
            printf("为中序遍历的第一个结点,无前驱\n");
        else
            printf("%c在中序遍历下的前驱为%c\n", p->data, r->data);
    }
    return 0;
}

五、 运行结果

oXJ2RS.png
oXJgG8.png
oXJRxg.png
oXJcPf.png

六、 实验总结与体会

  1. 实现了线索二叉树的存储和基本操作
  2. 体会了二叉树线索对前驱后继查找的优化
  3. 学习了线索的重要性

#如无特别声明,该文章均为 V1EERIE 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2021 年 12 月 25 日


create 添加新评论


account_circle
email
language
textsms





关于 DreamCat

主题名称:DreamCat | 版本:X2.6.220211

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WhiteBearcn | DFFZMXJ

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2022 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信