数据结构实验三二叉树的层次遍历

忘是亡心i 2022-06-06 13:41 160阅读 0赞

# 实验五 二叉树 #

## 一、实验目的 ##

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

## 二、实验内容 ##

利用二叉树的扩展前序遍历序列创建二叉树，然后实现二叉树的前序、中序和后序遍历。

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

在二叉树做任何运算之前，二叉树本身必须存在。因此，首先必须创建二叉树，实际上就是建立二叉树的存储结构。建立二叉树的存储结构就是建立二叉链表。例二叉树的扩展前序序列为"ABC\#\#D\#E\#\#F\#\#"，则由此建立的二叉树的中序序列为：CBDEAF,后序序列为：CEDBFA

## 源码： ##

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <queue>
    using namespace std;
    #define N 100
    char *a="ABC##D#E##F##";  /*扩充二叉树树t的前序序列*/
    typedef struct node /*二叉树结构定义*/
    {
        char data;
        struct node *lchild,*rchild;
    } binnode;
    typedef binnode *bintree;
    
    
    /*函数creatbintree (根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/
    bintree  creatbintree()
    {
        char ch=*a++;
        bintree t;
        if  (ch=='#')  t=NULL;
        else
        {
            t=(bintree)malloc(sizeof(binnode));
            t->data=ch;
            t->lchild=creatbintree();
            t->rchild=creatbintree();
        }
        return t;
    }
    
    
    void preorder(bintree t)  /*前序递归遍历二叉树*/
    {
        if (t)
        {
            printf("%c",t->data);
            preorder(t->lchild);
            preorder(t->rchild);
        }
    }
    void inorder(bintree t)  /*中序递归遍历二叉树*/
    {
        if (t)
        {
    
    
            inorder(t->lchild);
            printf("%c",t->data);
            inorder(t->rchild);
        }
    }
    void postorder(bintree t)  /*后序递归遍历二叉树*/
    {
        if (t)
        {
    
    
            postorder(t->lchild);
            postorder(t->rchild);
            printf("%c",t->data);
        }
    }
    
    
    /*************************************二叉树的层次遍历***********************************/
    queue<binnode*>q;
    void ccc(bintree t)
    {
        if(t!=NULL)
        {
            q.push(t);
            while(!q.empty())
            {
                cout<<q.front()->data;
                if(q.front()->lchild!=NULL)
                    q.push(q.front()->lchild);
                if(q.front()->rchild!=NULL)
                    q.push(q.front()->rchild);
                    q.pop();
            }
        }
    }
    /*****************************************************************************************/
    int main()
    {
        bintree t;
        t=creatbintree();   /*建立二叉树t的存储结构*/
        printf("二叉树的前序序列为：\n");
        preorder(t);   /*前序非递归遍历二叉树*/
        printf("二叉树的中序序列为：\n");
        inorder(t);   /*中序非递归遍历二叉树*/
        printf("二叉树的层次遍历序列为：\n");
        ccc(t);   /*中序非递归遍历二叉树*/
        return 0;
    }

## 四、实验要求： ##

1、 理解并调试好本程序；

2、 增加二叉树的按层遍历算法并重新调试。

3、 写出实验报告。

### 二叉树的层次遍历（STL实现） ###

/*************************************二叉树的层次遍历***********************************/
    queue<binnode*>q;
    void ccc(bintree t)
    {
        if(t!=NULL)
        {
            q.push(t);
            while(!q.empty())
            {
                cout<<q.front()->data;
                if(q.front()->lchild!=NULL)
                    q.push(q.front()->lchild);
                if(q.front()->rchild!=NULL)
                    q.push(q.front()->rchild);
                    q.pop();
            }
        }
    }
    /*****************************************************************************************/