专栏首页为学二叉树及其四种遍历

二叉树及其四种遍历

二叉树及其四种遍历

本次主要是针对二叉树的基本操作,另外还有二叉树相似的判断和叶子结点的计数,这些方法中都用到了递归。关于结构体的预定义还是会放在之前的博客(数据结构常用于定义总结)中

二叉树的数据结构

/*-------二叉树的二叉链结点结构定义------*/
#define TElemType char

typedef struct BiTNode{         // 结点结构
    TElemType data;             // 结点数据
    struct BiTNode *lchild, *rchild;    // 左右 孩子指针
} BiTNode, *BiTree;

/*-----------基本操作的函数-------------*/

基本操作

//按照二叉树的定义初始化一个空树
Status InitBiTree(BiTree *bt){

    *bt = (BiTree )malloc(sizeof(BiTNode));
    if (!bt)return OVERFLOW;

    *bt = NULL;

    return OK;
}

//构造二叉链表表示的二叉树T
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
Status CreateBiTree(BiTree *T){
    TElemType ch;

    printf_s("请输入数据:");
    scanf_s("%c", &ch);
    getchar();                      //getchar()用于处理回车占字符的问题
    if (ch == '#')
        *T = NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));

        if (!T)return OVERFLOW; // 若内存分配失败,则返回OVERFLOW

        (*T)->data = ch;            // 生成根结点
        CreateBiTree(&((*T)->lchild));  //构建左子树
        CreateBiTree(&((*T)->rchild));  //构建右子树
    }

    return OK;
}

四种遍历

//先序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void PreOrderTraverse(BiTree T){
    if (!T)return;              // 若为一个空树,则直接结束

    printf_s("%c", T->data);    // 显示结点数据,可以更改为其它对结点操作
    PreOrderTraverse(T->lchild);// 先遍历左孩子
    PreOrderTraverse(T->rchild);// 再遍历右孩子
}

//中序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void InOrderTraverse(BiTree T){
    if (!T)return;              // 若为一个空树,则直接结束

    InOrderTraverse(T->lchild);// 先遍历左孩子
    printf_s("%c", T->data);    // 显示结点数据,可以更改为其它对结点操作
    InOrderTraverse(T->rchild);// 再遍历右孩子
}

//后序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void PostOrderTraverse(BiTree T){
    if (!T)return;              // 若为一个空树,则直接结束

    PostOrderTraverse(T->lchild);// 先遍历左孩子
    PostOrderTraverse(T->rchild);// 再遍历右孩子
    printf_s("%c", T->data);    // 显示结点数据,可以更改为其它对结点操作
}

//层序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void LevelOrderTraverse(BiTree T){
    if (!T)return;              // 若为一个空树,则直接结束

    SqQueue Q;
    BiTree* e;
    e = (BiTree *)malloc(sizeof(BiTree));

    InitQueue(&Q);
    EnQueue(&Q, T);             //将根结点入队列

    while (!IsQueueEmpty(Q)){   //当队列不空时
        DeQueue(&Q, e);         //取出队首元素

        printf_s("%c", (*e)->data);
        if ((*e)->lchild)EnQueue(&Q, (*e)->lchild);//当队首元素左子树存在时让其入队列
        if ((*e)->rchild)EnQueue(&Q, (*e)->rchild);//当队首元素右子树存在时让其入队列
    }

    printf_s("\n"); 
}

其它函数

Status SimilarBiTree(BiTree B, BiTree T){
    if (!B && !T)return TRUE;   // 若两棵二叉树都为空树,则相似

    if (!B && T || B && !T)return FALSE;        //若其中一棵为空树,而另一棵不为,则不相似

    if (SimilarBiTree(B->lchild, T->lchild) && SimilarBiTree(B->rchild, T->rchild)){
        return TRUE;
    }

    return FALSE;
}

int Count(BiTree T){
    if (!T)return 0;        //空树有0个叶子结点

    if (!T->lchild && !T->rchild)return 1;
    else {
        return Count(T->lchild) + Count(T->rchild);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 判断是否为完全二叉树

    李志伟
  • 队列的基本操作(简单版)

    李志伟
  • Java基础笔记整理---【05】switch分支语句、for循环语句

    1.顺序结构:按前后顺序执行的语句体 代码块内的程序都是顺序执行的 2.分支结构:选择执行一部分语句体 if(表达式){ } if(表达式){ ... ...

    李志伟
  • 剑指offer代码解析——面试题19二叉树的镜像

       分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

    大闲人柴毛毛
  • Extjs grid 组件

    表格面板类Ext.grid.Panel 重要的配置参数 columns : Array 列模式(Ext.grid.column.Columnxtype: gr...

    用户1197315
  • 软件必备模块-全栈工程师

    有时候想想为什么写程序?写程序的初心是什么?这个代码写时间长了有时候就忘记了。为生计?为房贷?都不是。我想做自己喜欢的东西。就想一个一个画家画出了自己想表达的东...

    于欣轩
  • day02_品优购电商项目_02_前端框架AngularJS入门 + 品牌列表的实现 + 品牌列表分页的实现 + 增加/修改/删除品牌的实现 + 品牌分页条件查询的实现_用心笔记

    我们的数据一般都是从后端获取的,那么如何获取数据呢?我们一般使用内置服务$http来实现。注意:以下代码需要在tomcat中运行。

    黑泽君
  • iOS审核拒绝苹果官方原因详解

    GuangdongQi
  • 撕逼大会之需求评审

    用户2025931
  • Extjs 项目中常用的小技巧,也许你用得着(5)--设置 Ext.data.Store 传参的请求方式

    1.extjs 给怎么给panel设背景色 设置bodyStyle:'background:#ffc;padding:10px;', var resultsPa...

    hbbliyong

扫码关注云+社区

领取腾讯云代金券