【数据结构】树的基础知识及三种存储结构

这篇具有很好参考价值的文章主要介绍了【数据结构】树的基础知识及三种存储结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

一、树的概念与定义

把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 树是一种非线性的数据结构,它表现的关系是一对多

它是由n(n>=0)个结点组成的有限集,当n = 0时,称为空树
在任意一棵非空树中应满足:

🔸1.有且仅有一个特殊的根节点,根节点没有前驱结点

🔸2.每一个非根结点有且只有一个父结点;
🔸3.除了根结点外,每个子结点可以分为多个不相交的子树,并且子树是不相交的

🔸4.树是递归定义的

🔸 5.一颗N个结点的树有N-1条边

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

二、树的有关名词

就拿下面这颗树来举例:
【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6

叶节点终端节点度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点

非终端节点分支节点度不为0的节点; 如上图:D、E、F、G…等节点为分支节点

双亲节点父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点.

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

兄弟节点具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度深度树中节点的最大层次; 如上图:树的高度为4

堂兄弟节点双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林;

注意:节点和双亲结点为社么这样叫?就是因为引起对性别的歧视。既要尊重男性,也要尊重女性。

三、树的存储结构

(1)双亲表示法(2)孩子表示法(3)孩子兄弟表示法

1.双亲表示法

链式存储中在每个节点中,有一个指示器指示其双亲结点到链表中的位置,
使其每个结点,不但知道自己是谁,而且知道双亲位置

不能查找子节点,只能查找双亲结点。

1)链式存储
【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构
【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构
2)数组存储
采用数组中存放结构体。

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

2.孩子表示法

将每个结点的孩子结点排序,以单链表存储,则n个结点有n个孩子链表 并且如果是叶子结点,这个单链表为空然后将每个单链表的头指针组成一个线性表,顺序存储放入数组中

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

3.孩子兄弟表示法(又叫二叉树法)

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构

对于树来说,他的最好的存储方式是兄弟节点表示法

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

四、树的应用

【数据结构】树的基础知识及三种存储结构,数据结构与算法,数据结构文章来源地址https://www.toymoban.com/news/detail-708739.html

到了这里,关于【数据结构】树的基础知识及三种存储结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构--基础知识

    数据结构是计算机科学中研究数据组织、存储和管理的方法和原则。它涉及存储和操作数据的方式,以便能够高效地使用和访问数据。 数组(Array):数组是一种线性数据结构,由相同类型的元素按顺序排列而成。数组具有固定长度,在内存中占据连续的位置。可以通过索引

    2024年02月14日
    浏览(40)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(42)
  • 数据结构~二叉树(基础知识)

    上一篇博客我们对树有了初步了解与学习,这篇我将初步学习二叉树!!(新年快乐!) 目录 二叉树   1、定义: 2、特点: 3、基本形态: 4、二叉树的种类: (1)满二叉树 (2)完全二叉树 (效率高) (3)斜树 5、二叉树的性质:  6、二叉树的存储: 1、定义: 二叉树

    2024年02月19日
    浏览(48)
  • 数据结构基础知识、名词概述

    整体知识框架 1.1.1 数据、 数据元素、 数据项和数据对象 数据 (Data) 是客观事物的符号表示,是所有 能输入到计算机中并被计算机程序处理的符号 的总称 。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、 图像、声音及动画等通过特殊编

    2024年02月15日
    浏览(49)
  • 数据结构—基础知识:哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月21日
    浏览(43)
  • 数据结构—基础知识(15):哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月19日
    浏览(45)
  • 【数据结构】C--单链表(小白入门基础知识)

    前段时间写了一篇关于顺序表的博客,http://t.csdn.cn/0gCRp 顺序表在某些时候存在着一些不可避免的缺点: 问题: 1. 中间 / 头部的插入删除,时间复杂度为 O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈 2 倍的增长,势必会有一定的空间

    2024年02月16日
    浏览(48)
  • 数据结构—基础知识(12):二叉树算法补充

    复制二叉树 【算法步骤】 如果是空树,递归结束,否则进行以下操作: 申请一个新结点空间,复制根结点; 递归复制左子树; 递归复制右子树。 计算二叉树的深度 【算法步骤】 如果是空树,递归结束,深度为0,否则进行以下操作: 递归计算左子树的深度记为m; 递归计

    2024年01月25日
    浏览(48)
  • 【数据结构】栈和队列(栈的基本操作和基础知识)

    🌈个人主页: 秦jh__ https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》 https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 目录  前言 栈 栈的概念和结构 栈的实现 ​编辑 数组栈的实现 总的声明 初始化  插入 删除 取栈顶元素 销毁 判断是否为空

    2024年02月03日
    浏览(51)
  • 【数据结构】—— 队列基础知识以及数组模拟队列的分析、演示及优化

    ❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️ 🧑个人主页:@周小末天天开心 各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力 感谢! 📕该篇文章收录专栏—数据结构 目录 什么是队列? 数组模拟队列 分析 存入队列的步骤 使用数组模拟队列—

    2024年01月19日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包