首页 > 美文鉴赏

数据结构--二叉树操作

更新时间:2023-06-30 14:28:55 阅读： 评论：0

实验目的：
1.  基本要求：深刻理解二叉树性质和及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法； 拔丝南瓜
2.  较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
实验内容：
1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：
        1…建立树
        2…前序遍历树
        3…中序(非递归)遍历树
      4…后序遍历树
        0…结束
2）实验要求：在程序中定义下述函数，并实现要求的函数功能： 
CreateTree(): 按从键盘输入的前序序列，创建树
  PreOrderTree()：前序遍历树（递归）
  InOrderTree()：中序(非递归)遍历树
  LaOrderTree(): 后序遍历树（递归）
3）实验提示:
✧二叉链表存储数据类型定义
      # define ElemType char  //元素类型
        typedef struct BiTNode
          { ElemType data;
            struct BiTNode *lchild,*rchild;
            }BiTNode,*BiTree;
✧元素类型可以根据实际情况选取。
4）注意问题:
✧注意理解递归算法的执行步骤。
✧注意字符类型数据在输入时的处理。
✧重点理解如何利用栈结构实现非递归算法
2．编写算法交换二叉树中所有结点的左、右子树（实验类型：综合型）
1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树
2）实验要求：以二叉链表作为存储结构
3) 实现提示：设二叉树的根指针未t，且以二叉链表表示，可利用一个类型为qstack的指针来实现，且栈单元包含两个域，一个为data，另一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。
4）注意问题:
✧注意理解算法中栈结构的利用
3．试编写按层次顺序遍历二叉树的算法（实验类型：综合型）
1）问题描述：编写按层次顺序遍历二叉树的算法
2）实验要求：以二叉链表作为存储结构
3) 实现提示：本算法要采用一个队列q，先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树目的。
4）注意问题:
✧理解算法中队列结构的利用
4．实现一个哈夫曼编/译码系统（实验类型：综合型）
1）问题描述：利用哈夫曼编码进行信息通信可以大大编写按层次顺序遍历二叉树的算法提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。
2）实验要求：一个完整的系统应具有以下功能：
(1) I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
(2) E：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
(4) P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
(5) T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3) 实现提示：
(1) 文件CodeFile的基类型可以设为字节型。
(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。
(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
5．森林（孩子兄弟链表）的建立与遍历（实验类型：验证型）
1）问题描述：以“孩子兄弟二叉链表”为存储结构，建立和遍历一个森林
2）实验要求：以“孩子兄弟二叉链表”作为存储结构
3) 实现提示：
✧可参考二叉树的前序遍历和中序遍历算法
4）注意问题:
✧理解二叉树与树的对应关系
✧理解树和森林遍历的实质
实验内容（应包括实验题目、实验要求、实验任务等）
附录（可包括源程序清单或其它说明）
实验源程序代码如下：
第一题：
#include <stdio.h>
西游记怎么画
#include <stdlib.h>
#include<iostream.h>
#define Max 50
typedef char EType;
typedef struct BiTNode
{
    EType data;
    struct BiTNode *lchild,*rchild;
}BiTNode;
typedef BiTNode *BiTree;
BiTree root;
BiTree Create()
{
牛肉烧笋子的做法
    char ch;
    BiTree T;
    cin>>ch;
    if(ch=='#')
        T=NULL;
招商计划方案    el
    {
        if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
            exit(1);
        T->data=ch;
        T->lchild=Create();
        T->rchild=Create();
    }
    return T;
}
void PreOrderTree(BiTree root)/////////前序遍历树（递归）
{
    if(root==NULL)
        return;
    cout<<root->data;综合学科
    PreOrderTree(root->lchild);
    PreOrderTree(root->rchild);
}
void InOrderTree(BiTree root) //////////////中序(非递归)遍历树
{
    BiTree p,stack[Max];
    int top=0;
    if(root==NULL)
        return;
    p=root;
    while(!(p==NULL&&top==0))
甘肃专科    {
        while(p!=NULL)
        {
           
            if(top<Max-1)
            {
                stack[top]=p;
                top++;
            }
            el
            {
                cout<<"栈溢出!!"<<endl;
                return;
            }
            p=p->lchild;
        }
        if(top<=0)
            return;
        el
        {
            top--;
            p=stack[top];
            cout<<root->data;
            p=p->rchild;
        }
    }
}
void LaOrderTree(BiTree root)  ///////////////后序遍历树（递归）
黑枸杞的作用{
    if(root==NULL)
        return;
    PreOrderTree(root->lchild);
    PreOrderTree(root->rchild);
    cout<<root->data;
}
void main()
{
    BiTree T;
    int choice;
    for(;;)
    {
        cout<<endl;
        cout<<"============================="<<endl;
        cout<<"1.建立新树"<<endl;
        cout<<"2.先序遍历树"<<endl;
        cout<<"3.中序遍历树"<<endl;
        cout<<"4.后序遍历树"<<endl;
        cout<<"0.退出程序"<<endl;
        cout<<"请输入选项序号："<<endl;
        cin>>choice;
        if(choice==0)
            break;
        switch(choice)
        {
        ca 1:
            cout<<"开始建立新树:"<<endl;
            T=Create();
            break;
        ca 2:
            cout<<"先序遍历树的结果为："<<endl;
            PreOrderTree(T);
            break;
        ca 3:
            cout<<"中序遍历树的结果为："<<endl;
            InOrderTree(T);
            break;
        ca 4:
            cout<<"后序遍历树的结果为："<<endl;
            LaOrderTree(T);
            break;
关于节约的名言        }
    }
}
第二题：
#include<iostream.h>
#include<stdlib.h>
typedef char elemtype;
#define maxnode 100
typedef elemtype sqbitree[maxnode];

本文发布于:2023-06-30 14:28:55，感谢您对本站的认可！

本文链接：https://www.wtabcd.cn/fanwen/fan/89/1061675.html

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

上一篇：公路工程常用法语词汇
下一篇：c++实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序）
标签：遍历   算法   二叉树   实验   类型   编码
相关文章
留言与评论（共有 0 条评论）
   
验证码：
推荐文章
排行榜
热门标签
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图