精华内容
下载资源
问答
  • 二叉树的创建与遍历

    2020-11-22 20:45:02
    C语言 数据结构实验四 二叉树的创建与遍历 【实验内容】 按扩展先序遍历序列输入二叉树中结点的值,(用‘#’表示空),构造一棵二叉树; 1、 以递归算法实现二叉树的先序、中序、后序遍历; 2、求·二叉树的深度和...

    C语言 数据结构实验四 二叉树的创建与遍历

    【实验内容】
    按扩展先序遍历序列输入二叉树中结点的值,(用‘#’表示空),构造一棵二叉树;
    1、 以递归算法实现二叉树的先序、中序、后序遍历;
    2、求·二叉树的深度和结点个数;
    3、 实现二叉树的层次遍历(采用队列实现)。

    typedef  char  TElemType;
    typedef  struct  BiTnode
    { TElemType  data;                       //保存树结点的数据元素,比如字符A、B、C等
      struct   BiTnode  *lchild, *rchild;    //左右子树的指针
    } BiTnode,*BiTree;
    /*先序输入创建二叉树*/
    void CreateBTree(BiTree &b)      //根结点指针b唯一标识整个二叉树存储结构
    {
        char ch;                    //输入树结点数据元素
        scanf("%c",&ch);
        if(ch=='#')  b=NULL;        //#表示空
        else
        {
            b=(BiTree)malloc(sizeof(BiTnode));
            b->data=ch;                      //按先序遍历序列输入
            CreateBTree(b->lchild);
            CreateBTree(b->rchild);
        }
    }
    void preorder(BiTree b)              //先序遍历递归算法
    {
        if(b!=NULL)
        {
            printf("%c\t",b->data);      //访问根结点
            preorder(b->lchild);       //先序遍历左子树
            preorder(b->rchild);       //先序遍历右子树
        }
    }
    void inorder(BiTree b)                //中序遍历递归算法
    {
        if(b!=NULL)
        {
            inorder(b->lchild);       //中序遍历左子树
            printf("%c\t",b->data);     //访问根结点
            inorder(b->rchild);       //中序遍历右子树
        }
    }
    void postorder(BiTree b)                 //后序遍历递归算法
    {
        if(b!=NULL)
        {
            postorder(b->lchild);     //后序遍历左子树
            postorder(b->rchild);     //后序遍历右子树
            printf("%c\t",b->data);     //访问根结点
        }
    }
    
    /*递归算法求二叉树深度*/
    int BTdepth(BiTree b)
    {
        int lchilddp,rchilddp;
        if(b==NULL)  return(0);   //空树深度为0
        else
        {
            lchilddp=BTdepth(b->lchild);    //左子树深度为lchilddp
            rchilddp=BTdepth(b->rchild);    //右子树深度为rchilddp
            return(lchilddp>rchilddp)?(lchilddp+1):(rchilddp+1);
        }
    }
    /*递归算法求二叉树结点个数*/
    int BTsum(BiTree b)
    {
        if(b==NULL)  return(0);
        else
            return(BTsum(b->lchild)+BTsum(b->rchild)+1);   //结点个数等于左子树结点与右子树结点个数之和加上根结点
    }
    
    /*运用队列实现层次遍历*/
    void levelorder(BiTree b)
    {
        SqQueue *q;
        InitQueue(q);
        if(b!=NULL)
            enQueue(q,b);            //树不为空,将结点入队
        while(!QueueEmpty(q))
        {
            deQueue(q,b);            //队列不为空时,对头y结点出队,左孩右孩入队
            printf("%c\t",b->data);
            if(b->lchild!=NULL)
                enQueue(q,b->lchild);
            if(b->rchild!=NULL)
                enQueue(q,b->rchild);
        }
        DestroyQueue(q);
    }
    

    利用队列先进先出的特点实现层次遍历,要注意创建队列结构体时,用的是指针型数组存取队列元素。

    typedef struct
    {
        BiTree data[MaxSize];        //数组保存树结点指针
        int front,rear;
    }SqQueue;
    
    展开全文
  • C++二叉树的创建与遍历实验报告 作者: 日期 ? 二叉树的创建与遍历 一 实验目的 1.学会实现二叉树结点结构和对二叉树的基本操作 2.掌握对二叉树每种操作的具体实现学会利用递归和非递归方法编写对二叉树这种递归数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,416
精华内容 566
关键字:

二叉树的创建与遍历