数据结构实验六树的遍历

系统管理员 2022-06-05 01:55 191阅读 0赞

### 一、实验目的 ###

掌握树的创建、遍历的方法。

### 二、实验内容 ###

利用树的扩展先根遍历序列创建度为3的树，然后实现树的先根次序、后根次序遍历。

### 三、实验内容准备 ###

在对树做任何运算之前，树本身必须存在。因此，首先必须创建树，实际上就是建立树的存储结构。例树的扩展前序序列为"AB\#\#\#C\#\#\#D\#\#\#"，则由此建立的树的先根次序序列为：ABCD,后序序列为：BCDA

### 四、实验要求 ###

1、理解并调试好程序。

2、增加树的按层次遍历并重新调试。

3、写出实验报告。

### 五、源码 ###

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    #include <queue>
    #define m 3
    #define MAXLEN 100
    using namespace std;
    
    
    typedef char datatype;
    typedef struct node
    {
        datatype data;
        struct node *child[m];
    } node;
    typedef  node *tree;
    /********************************************************/
    /*  函数功能:根据树的前序遍历结果建立一棵3度树	  	   */
    /*  函数返回值:树根地址								   */
    /*  文件名:tree.h,函数名:createtree ()		            */
    /********************************************************/
    
    tree  createtree()
    {
        /*按前序遍历顺序建立一棵3度树的递归算法*/
    
        int i;
        char ch;
        tree t;
        if ((ch=getchar())=='#')  t=NULL;
        else
        {
            t=(tree) malloc (sizeof(node));
            t->data=ch;
            for (i=0; i<m; ++i)
                t->child[i]= createtree();
        }
        return t;
    }
    
    void preorder(tree t)
    {
        int i;
        if (t)
        {
            printf("%c",t->data);
            for (i=0; i<m; i++)
                preorder(t->child[i]);
        }
    }
    
    void postorder(tree t)
    {
        int i;
        if (t)
        {
            for (i=0; i<m; i++)
                postorder(t->child[i]);
            printf("%c",t->data);
        }
    }
    /*********************树的层次******************************/
    queue<tree>q;
    void cengciorder(tree t)
    {
        if(t)
        {
            q.push(t);
        }
        while(!q.empty())
        {
            cout<<q.front()->data;
            for(int i=0; i<m; i++)
            {
                if(q.front()->child[i]!=NULL)
                    q.push(q.front()->child[i]);
            }
            q.pop();
        }
    }
    /*************************************************************/
    int main()
    {
        tree t;
        t=createtree();
        preorder(t);
        printf("\n");
        postorder(t);
        printf("\n");
        cengciorder(t);
        printf("\n");
        return 0;
    }

### 五、树的层次遍历（STL实现） ###

queue<tree>q;
    void cengciorder(tree t)
    {
        if(t)
        {
            q.push(t);
        }
        while(!q.empty())
        {
            cout<<q.front()->data;
            for(int i=0; i<m; i++)
            {
                if(q.front()->child[i]!=NULL)
                    q.push(q.front()->child[i]);
            }
            q.pop();
        }
    }