二叉树的链式存储

这篇具有很好参考价值的文章主要介绍了二叉树的链式存储。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树的链式存储

//
//  main.c
//  LinkBiTree
//
//  Created by Eason on 2020/8/10.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <string.h>
#include <stdlib.h>
#include "math.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100   //二叉树的最大长度
typedef char ElemType;  //二叉树的数据元素类型
typedef int Status;   //用int作为状态类型,对应预定义的OK ERROR TRUE FALSE
int i=1;   //创建二叉树时的字符串定位器
typedef char String[MAXSIZE];   //定义一个字符数组作为字符串来创建二叉树
String S;   //数组对象
typedef struct BTNode   //二叉树的链式存储结构
{
   ElemType data;
   struct BTNode *leftChild,*rightChild;
}BTNode,*BTree;   //BTree = *BTNode

//字符串初始化(将ch长度地址范围里的字符依次读入字符串中)
Status initString(String S, char *ch){
    if(strlen(ch)>=MAXSIZE){   //判断用来初始化的字符长度是否超出预定义的字符串长度
        return ERROR;
    }
    S[0] = strlen(ch);   //S[0]用来存储字符串长度
    int loc=0;   //ch定位器
    for(int i=1;i<=S[0];i++){   //依次循环读入字符串中
        S[i] = *(ch+loc);   //当前ch下一个地址的ch
        loc++;   //加到第几个位置的ch
    }
    printf("字符串初始化完成\n");
    return OK;
}

//打印字符串
Status printString(String S){   //没啥好说的就是个循环遍历打印初始化过的字符串
    for(int i=0;i<=strlen(S);i++){
        printf("%c ", S[i]);
    }
    printf("\n");
    return OK;
}
//初始化链二叉树
Status initTree(BTree *T){   //将二叉树的根结点置为空则初始化成功
    *T=NULL;
    printf("初始化成功!\n");
    return OK;
}

//判断链二叉树是否为空
Status isEmpty(BTree T){  //若二叉树的根结点为空,则此树为空
    if(T==NULL){
        return TRUE;
    }else{
        return FALSE;
    }
}

//创建链二叉树(利用初始化的字符串向二叉树中读入来创建二叉树)
void createBTree(BTree *T){
    ElemType ch;   //临时字符存储器
    ch = S[i++];   //将当前数组的位置的字符读入ch中后位置++
    if(ch=='#'){   //若字符为‘#’则说明此位置为空
        *T=NULL;   //则将此位置置为空
    }else{
        *T=(BTree)malloc(sizeof(BTNode));  //若此处的字符不为空,则为其分配一个结点大小的内存
        if(!*T){   //判断能否为新结点申请内存
            printf("内存分配失败\n");
            exit(OVERFLOW);
        }else{   //分配内存成功
            (*T)->data = ch;   //将此位置的数据置为对应的字符值
            createBTree(&(*T)->leftChild);   //递归继续寻找是否左孩子结点存在若存在则按照步骤分配内存成立对应的结点,若无则返回向下
            createBTree(&(*T)->rightChild);   //此时是若结点无左孩子则递归寻找是否是有右孩子若有则按照步骤分配内存成立对应的结点,若无则返回上一级的结点判断右孩子继续递归
        }
    }
}

//销毁二叉树(清空二叉树clearBTree()相同)
Status destroyBTree(BTree *T){
    if(*T){   //若当前结点存在
        if((*T)->leftChild){   //则判断是否有左孩子,若有则先销毁左孩子
            destroyBTree(&(*T)->leftChild);   //递归销毁左孩子
        }
        if((*T)->rightChild){   //无左孩子则判断是否有右孩子,若有则销毁右孩子
            destroyBTree(&(*T)->rightChild);   //递归销毁右孩子
        }
        free(*T);   //若都没有则释放当前结点
        *T=NULL;   //将结点置空
    }
    return OK;
}

//获得二叉树的深度
int getDepth(BTree *T){
    int deep = 0;   //深度计数
    if(*T!=NULL){   //如果当前结点不为空
        int leftdeep = getDepth(&(*T)->leftChild);   //则先判断其左子树的深度
        int rightdeep = getDepth(&(*T)->rightChild);  //然后判断右子树的深度
        deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1;   //二叉树的深度对应左右子树中最大的一个 再加上当前的深度1
    }
    return deep;   //将深度值返回
}

//获取根结点的数据
char getRoot(BTree T){
    if(isEmpty(T)){   //判断二叉树是否为空
        printf("根结点不存在,无法获取\n");
        return ERROR;
    }
    return T->data;   //若二叉树不为空,则返回当前结点的数据域
}

//获取指定结点的数据
char getValue(BTree T){
    if(isEmpty(T)){   //判断当前结点是否存在
        printf("当前结点不存在,无法获取\n");
        return ERROR;
    }
    return T->data;   //返回当前结点的数据
}

//为指定结点的数据更换数值(将结点T的数据域更换为指定的value值)
Status replaceValue(BTree *T, char *value){
    (*T)->data = *value;   //将制定的value值替换入指定结点的数据域中
    return OK;
}

//前序遍历
void preOrederTraverse(BTree T){
    if(T==NULL){    //判断当前结点是否存在,不存在则推出当前方法返回上一级,若无上一级则退出
        return;
    }
    printf("%c ", T->data);   //先访问根结点
    preOrederTraverse(T->leftChild);   //后遍历左子树
    preOrederTraverse(T->rightChild);   //最后遍历右子树
}

//中序遍历
void inOrderTraverse(BTree T){
    if(T==NULL){   //判断当前结点是否存在,不存在则推出当前方法返回上一级,若无上一级则退出
        return;
    }
    inOrderTraverse(T->leftChild);   //先遍历左子树
    printf("%c ", T->data);   //后访问根结点
    inOrderTraverse(T->rightChild);   //最后遍历右子树
}

//后序遍历
void postOrderTraverse(BTree T){
    if(T==NULL){   //判断当前结点是否存在,不存在则推出当前方法返回上一级,若无上一级则退出
        return;
    }
    postOrderTraverse(T->leftChild);    //先遍历左子树
    postOrderTraverse(T->rightChild);   //再遍历右子树
    printf("%c ", T->data);   //最后访问根结点
}


//测试
int main()
{
    BTree T;
    initTree(&T);
    initString(S, "EASO#N###H##EGO###G#O##");
    printf("字符串初始为:\n");
    printString(S);
    printf("创建二叉树T\n");
    createBTree(&T);
    printf("完成创建二叉树T\n");
    printf("二叉树的深度为:%d\n", getDepth(&T));
    printf("前序遍历二叉树T:\n");
    preOrederTraverse(T);
    printf("\n中序遍历二叉树T:\n");
    inOrderTraverse(T);
    printf("\n后序遍历二叉树T:\n");
    postOrderTraverse(T);
    printf("\n此时的根结点为:%c\n", getRoot(T));
    printf("将二叉树销毁后遍历可得:\n");
    destroyBTree(&T);
    preOrederTraverse(T);
    printf("此时的根结点为:%c\n", getRoot(T));
    return 0;
}

文章来源地址https://www.toymoban.com/news/detail-622513.html

到了这里,关于二叉树的链式存储的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【链式二叉树】数据结构链式二叉树的(万字详解)

    前言: 在上一篇博客中,我们已经详解学习了堆的基本知识,今天带大家进入的是二叉树的另外一种存储方式----“链式二叉树”的学习,主要用到的就是“递归思想”!! 前情回顾: 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点

    2024年01月20日
    浏览(49)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(52)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(56)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(43)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)
  • 【数据结构】二叉树的链式结构及实现

    目录 1. 前置说明 2. 二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 3. 节点个数及高度等 4. 二叉树的创建和销毁 在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成

    2024年02月08日
    浏览(41)
  • 数据结构初阶--二叉树的链式结构

    目录 一.二叉树链式结构的概念 二.二叉树链式结构的功能实现 2.1.链式二叉树的定义 2.2.链式二叉树的构建 2.3.链式二叉树的遍历 2.3.1.先序遍历 2.3.2.中序遍历 2.3.3.后序遍历 2.3.4.层序遍历 2.4.链式二叉树的求二叉树的结点数量 法一:计数法 法二:分治法 2.5.链式二叉树的求二

    2024年02月12日
    浏览(43)
  • 数据结构:二叉树的链式结构的实现

      目录  1.通过前序遍历构建二叉树 2. 二叉树的销毁  3.二叉树的遍历 4. 二叉树的节点个位和二叉树的叶子节点个位数 5. 二叉树的的k层节点数和查找值为x的节点 6. 判断二叉树是否为完全二叉树和求二叉树的高度h 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历

    2024年02月12日
    浏览(44)
  • 【数据结构】二叉树的链式实现及遍历

    后文所有代码中的二叉树结点: 前,中,后序遍历都可以采用分治递归的思想解决,将根节点和它的孩子结点分别处理。 此处仅利用递归展开图分析前序遍历,中序和后序也是相同的思想: 层序遍历需要利用队列来进行,如果二叉树跟结点不为空,则让 指向它的一个指针入

    2024年02月07日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包