爱问知识人 爱问共享资料 医院库

二叉树的遍历操作实现

首页

二叉树的遍历操作实现

二. 实验内容与要求
1.建立二叉树二叉链存贮结构。
2. 根据二叉树的括号表示方法,建立一棵二叉树。
3. 根据建立的二叉树的二叉链存贮结构,进行二叉树的遍历,输出相应序列。
4. 对建立的二叉树求其叶子结点数、度为2的结点数、求树的高度、以括号表示法输出二叉树。

提交回答

全部答案

    2018-05-15 04:39:29
  •   // S_lbecs。cpp : 定义控制台应用程序的入口点。
    //链表二叉树的定义和操作
    #include "stdafx。h"
    #include "stdio。h"
    #include "malloc。
      h"
    #include "string。h"
    #include "stdlib。h"
    #define Max 20 //最大节点个数
    typedef struct node{
    char data;
    struct node *lchild,*rchild; //左边孩子的指针 和 右边孩子的指针
    }BinTNode;
    typedef BinTNode *BinTree; //定义二叉树的指针
    int NodeNum,leaf; //NodeNum是结点数 leaf是叶子数
    //基于先序遍历算法创建二叉树
    //要求输入先序序列,其中加入虚结点“#”以示空指针的位置
    BinTree CreatBinTree(void){
    BinTree T;
    char ch;
    scanf("%c",&ch);
    if(ch=='#') //读入# 返回空指针
    return(NULL);
    else{
    T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
    T->data=ch;
    T->lchild=CreatBinTree(); //构造左子树
    T->rchild=CreatBinTree(); //构造右子树
    return(T);
    }
    }
    //DLR 先序遍历
    //访问根节点 先序遍历左子树 先序遍历右子树
    void Preorde(BinTree T){
    if(T){
    printf("%c",T->data); //访问结点 D
    Preorde(T->lchild); //先序遍历左子树 L
    Preorde(T->rchild); //先序遍历右子树 R
    }
    }
    //LDR 中序遍历
    void Inorder(BinTree T){
    if(T){
    Inorder(T->lchild); //中序遍历左子树 L
    printf("%c",T->data); //访问结点 D
    Inorder(T->rchild); //中序遍历右子树 R
    }
    }
    //LRD 后序遍历
    void Postorder(BinTree T){
    if(T){
    Postorder(T->lchild); //后序遍历左子树 L
    Postorder(T->rchild); //后序遍历右子树 R
    printf("%c",T->data); //访问结点 D
    }
    }
    //采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
    int TreeDepth(BinTree T){
    int hl,hr,max;
    if(T){
    hl=TreeDepth(T->lchild); //求左深度
    hr=TreeDepth(T->rchild); //求右深度
    max=hl>hr?hl:hr; //取最大深度
    NodeNum=NodeNum 1; //求结点数
    if(hl==0&&hr==0) //若左右深度都为0 则为叶子
    leaf=leaf 1;
    return(max 1);
    }else{
    return(0);
    }
    }
    //利用“先进先出”(FIFO)队列,按层次遍历二叉树
    void Levelorder(BinTree T){
    int front=0,rear=1;
    BinTNode *cq[Max],*p; //定义结点的指针数组cq
    cq[1]=T; //根入队
    while(front!=rear){
    front=(front 1)%NodeNum;
    p=cq[front]; //出队
    printf("%c",p->data); //输出结点的值
    if(p->lchild!=NULL){
    rear=(rear 1)%NodeNum;
    cq[rear]=p->lchild; //左子树入队
    }
    if(p->rchild!=NULL){
    rear=(rear 1)%NodeNum;
    cq[rear]=p->rchild; //右子树入队
    }
    }
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    BinTree root;
    int i,depth; //最大深度
    printf(" 创建二叉树;输入完全二叉树先序序列:");
    //用#代表虚结点 如ABD###CE##F##
    root=CreatBinTree(); //创建二叉树 返回根结点
    printf(" 创建成功! ");
    do{ //从菜单中选择遍历方式,输入序号。
      
    printf(" ********** select ************ ");
    printf(" 1: 先序遍历 ");
    printf(" 2: 中序遍历 ");
    printf(" 3: 后序遍历 ");
    printf(" 4: 求树的深度及叶子数 ");
    printf(" 5: 按层次遍历 "); //按层次遍历之前,先选择4,求出该树的结点数。
      
    printf(" 0: 退出 ");
    printf(" ******************************* 请选择:");
    scanf("%d",&i); //输入菜单选项 0-5
    switch(i){
    case 1:
    //1: 先序遍历 Preorde
    printf("先序遍历的结果是");
    Preorde(root); //
    printf(" ");
    break;
    case 2:
    //2: 中序遍历 Inorder
    printf("中序遍历的结果是");
    Inorder(root); //
    printf(" ");
    break;
    case 3:
    //3: 后序遍历 Postorder
    printf("后序遍历的结果是");
    Postorder(root); //
    printf(" ");
    break;
    case 4:
    //4: 求树的深度及叶子数 TreeDepth
    depth=TreeDepth(root); //
    printf("数的深度=%d 结点数=%d",depth,NodeNum);
    printf(" 叶子数=%d",leaf);
    printf(" ");
    break;
    case 5:
    //5: 按层次遍历 Preorde
    printf("按层次遍历的结果是");
    Levelorder(root); //
    printf(" ");
    break;
    default:
    printf("输入错误 ");
    break;
    }

    }while(i!=0);
    return 0;
    }
    是vs做的 有些地方需要改下 是C语言做的。
      

    笑***

    2018-05-15 04:39:29

类似问题

换一换
  • 电脑/网络 相关知识

  • 电脑网络技术
  • 电脑网络

相关推荐

正在加载...
最新资料 推荐信息 热门专题 热点推荐
  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200
  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200
  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200
  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200

热点检索

  • 1-20
  • 21-40
  • 41-60
  • 61-80
  • 81-100
  • 101-120
  • 121-140
  • 141-160
  • 161-180
  • 181-200
返回
顶部
帮助 意见
反馈
关注
爱问

关注爱问微信公众号,开启知识之旅,随时随地了解最新资讯。

确定举报此问题

举报原因(必选):