数据结构课程设计报告之线索二叉树

更新时间:2023-06-15 15:05:07 阅读: 评论:0

线索二叉树
一  目的
程序从文件中读取每个结点的信息,然后建立一个二叉树。通过菜单的形式,选择不同的线索化方式,然后再对线索化的二叉树经行遍历并输出对应的结果。
二  需求分析
1、文件的读入
程序首先要从一个文件中读入结点的信息。故需建立一个文件,在文件中,给出每个结点的信息。
2、菜单的实现
由于需要建立两种不同的线索二叉树,故需要一个菜单,来选择需要进行的操作,并输出操作的结果。
3、树的建立
从文件中,读入每个结点的信息。然后建立起树,然后再对已建立的树进行相应的线索化。
4、树的线索化
      根据菜单的选择,对已建立的树经行相对应的线索化。
5、输出遍历的结果
      对每种不同的线索化的的树,给出相对应的算法。然后,根据算法把每种遍历的结果输出。
三  概要设计zyg
1、主程序模块
商誉会计(1)主程序模块
int main()
端午节用英语怎么说{
    welcome(); //通过welcome()模块来让用户控制,做线索化的工作。
    return 0;
}
六级425分算过吗
(2)可线索化单元模块—实现各种线索化的抽象数据类型;通过welcome()模块来调用每个线索化模块。
2、建立二叉树的模块
bool CreatBinTree();
函数会根据用户输入的文件名,打开一个存储了树中每个结点的文件,且是用广义表的形式给出结点信息的文件。
操作结果:根据文件中广义表的形式,建立相对应的二叉树,该树的根节点为root。
3、线索化的抽象数据类型
void CreatInThread();
void CreatInThread(Node *current,Node *&front)
current是中序遍历下,当前遍历的结点的指针。front是中序遍历下,current结点的前驱的指针。
    操作结果:对建立的二叉树完成中序线索化。
    void CreatPostThread();
    void CreatPostThread(Node *current,Node *&front)
    current是后续遍历下,当前遍历的结点的指针。front是后续遍历下,current结点的前驱的指针。
    操作结果:对已建立的二叉树完成后续线索化。
4、输出结果的抽象数据类型
void InOrder()
操作结果:输出中序线索二叉树的中序遍历的结果。
Node* InFirst(Node *current)
current是中序线索二叉树中指向一个结点的指针。
操作结果:返回以current为根的树的中序遍历下的第一个结点的指针。
Node* InNext(Node *current)
current是中序线索二叉树中指向一个结点的指针。
操作结果:返回中序遍历下,current结点的后继结点的指针。
void PostOrder()
操作结果:输出后续线索二叉树的后续遍历结果。n2成绩查询
Node* PostFirst(Node *current)
current是后续线索二叉树中指向一个结点的指针。
操作结果:返回以current为根的树的后续遍历下的第一个结点的指针。
Node* PostNext(Node *current)
current是后续线索二叉树中指向一个结点的指针。
操作结果:返回后续遍历下,current结点的后继结点的指针。
四  详细设计
二叉树中,每个结点的定义
struct Node
{
    char ch;      //每个结点的信息域
    int ltag;      //左孩子指针标志域
    int rtag;      //右孩子指针标志域
    Node *left;    //左孩子
    Node *right;  //右孩子
    Node *parent;  //双亲结点
};
线索二叉树的抽象数据类型
class ThreadTree                  //线索二叉树的抽象数据类型
{
public:
    ThreadTree();                    //构造函数
    bool CreatBinTree();            //从文件中读取数据并建立二叉树
    void CreatInThread();            //对二叉树进行中序线索化   
新东方 北京
    void CreatInThread(Node *current,Node *&front);
    Node* InFirst(Node *current);    //寻找中序下的第一个结点
    Node* InNext(Node *current);    //寻找中序下当前结点的后继结点裙子的拼音
    void InOrder();                  //对中序线索二叉树进行遍历
    void CreatPostThread();          //对二叉树进行后序线索化
    void CreatPostThread(Node *current,Node *&front);
    Node* PostFirst(Node *current);  //需找后序下的第一个结点
    Node* PostNext(Node *current);  //寻找后序下当前结点的后继结点
    void PostOrder();                //对后序线索二叉树进行遍历
    void DeleteInTree();            //析构中序线索二叉树
    void DeletePostTree();          //析构后续线索二叉树
private:
    Node *root;
};
整个流程图如下:
常用英语对话
五  调试分析
1.程序首先要解决文件的形式问题,即文件中存储树的形式,可以给出树的先序遍历序列,也可以给出树的广义表形式。该程序中,是给出的广义表的形式。
2.改程序可以从文件中读取信息,然后把二叉树建立起来。
王强 新东方
3.建立二叉树后,就需要对二叉树进行线索化。这就必须知道线索二叉树的定义,才能知道对二叉树线索化的大概算法,最终把线索二叉树通过函数建立起来。
4.线索化完成后,还要对树经行遍历。若对树经行普通的中序或后续遍历,则对改程序没有任何的意义。所以,要充分理解线索二叉树的好处与优势,并分析出对线索二叉树遍历的比较快速的算法。

本文发布于:2023-06-15 15:05:07,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/fan/78/961065.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:线索   二叉树   结点   遍历   中序   建立   结果   后续
相关文章
留言与评论(共有 0 条评论)
   
验证码:
推荐文章
排行榜
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图