数据结构-线索二叉树-题解(C++代码)

641 阅读 0 评论 0 点赞

```cpp
#include <iostream>
using namespace std;
struct A
{
    char data;
    struct A *lchild;
    struct A *rchild;
    int ltag=0, rtag=0;
};
typedef A *PA;
void InThreading(PA &p, PA &pre);
void InOrderThreading(PA &Thr, PA &T);
void InOrderTranverse(PA &Thr);
void init(PA &T);
int main()
{
    PA Thr,T;
    init(T);
    InOrderThreading(Thr,T);
    InOrderTranverse(Thr);
    cout<<endl;
    system("pause");
    return 0;
}

void init(PA &T)
{
    char a;
    cin.get(a);
    if (a == ' ')
    {
        T = NULL;
    }
    else
    {
        T = new A;
        T->data = a;
        init(T->lchild);
        init(T->rchild);
    }
}

void InOrderThreading(PA &Thr, PA &T)
{
    Thr = new A;
    Thr->rchild = Thr;
    PA pre;
    Thr->ltag = 0;
    if (!T)
        Thr->lchild = Thr;
    else
    {
        Thr->lchild = T;
        pre = Thr;
        InThreading(T, pre);
        Thr->rchild = pre;
        Thr->rtag = 1;
        pre->rchild = Thr;
        pre->rtag = 1;
    }
}

void InThreading(PA &p, PA &pre)
{
    if (p)
    {
        InThreading(p->lchild, pre);
        if (!p->lchild)
        {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (!pre->rchild)
        {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThreading(p->rchild, pre);
    }
}

void InOrderTranverse(PA &Thr)
{
    PA p = Thr->lchild;
    while (p != Thr)
    {
        while (p->ltag == 0)
            p = p->lchild;
        cout << p->data << " ";
        while (p->rtag == 1 && p->rchild != Thr)
        {
            p = p->rchild;
            cout << p->data << " ";
        }
        p = p->rchild;
    }
}

```

0.0分

1 人评分

本文分类：题解列表
浏览次数：641 次浏览
发布日期：2020-03-13 20:12:44
本文链接：https://blog.dotcpp.com/a/67905

上一篇 > 蓝桥杯算法训练VIP-一元三次方程求解-题解(Python代码)
下一篇 > 数据结构-自底向上的赫夫曼编码-题解(C++代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构-线索二叉树-题解(C++代码)

评论列表共有 0 条评论

发表评论取消回复

数据结构-线索二叉树-题解(C++代码)

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复