C语言_数据结构总结9:树的基础知识介绍

 1. 树的基本术语

    - 祖先:考虑结点K,从根A到结点K的唯一路径上的所有其它结点,称为结点K的祖先。
    - 子孙:结点B是结点K的祖先,结点K是B的子孙。结点B的子孙包括:E,F,K,L。
    - 双亲:路径上最接近结点K的结点称为结点K的双亲。根A是树中唯一没有双亲的结点。
    - 孩子:k为E的孩子。
    - 兄弟:有相同双亲的称为兄弟。如K和L。
    - 堂兄弟:双亲在同一层的结点称为堂兄弟。

结点的度:树中一个结点的孩子个数,称为该节点的度
    - 树的度:树中结点的最大度数为树的度


    - 分支结点/非终端结点:度大于0的结点
        在分支结点/非终端结点中,每个结点的分支数就是该结点的度 
    - 叶结点:度为0的结点


    - 结点的层次:从树根开始定义,根结点为第一层,它的孩子为第二层,如何以此类推
    - 树的深度/高度:树中结点的最大层数
    - 结点的高度:以该结点为根的`子树的高度`


    - 有序树:树中结点的各子树从左到右都是有次序的,不能互换
    - 无序树:有序树以外的树

   
    - 路径:树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的
    - 路径长度:路径上所经过的边的个数
      根到每个结点的路径长度的最大值应是树的高度减1 

    - 森林:是 m (m>=0) 棵互不相交的树的集合。
     只要把一棵树的根结点删去就成了森林,反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林变成了树。

2. 树的性质

    1. 树的结点数n等于所有结点的度数之和+1  
        类推:n = 树中所有的边数之和 + 1
    2. m叉树中第i层上至多有 m^(i-1) 个结点(i>=1)
    3. 高度为h的m叉树至多有 (m^h-1)/(m-1) 个结点
        当各层结点数达到最大时,树中至多有1+m+m^2+……+m^h-1=(m^h-1)/(m-1)个结点
    4. 度为m,结点为n的树,最小高度 h = logm(m(n-1)+1)。即让每层的结点数都达到最大时
    5. 度为m,结点为n的树,最小高度 h = n - m + 1。即除了最底层,前h-1层都只有一个结点

3. 二叉树

    - 与树相似,二叉树也以递归的形式定义,二叉树是n(n>=0)个结点的有限集合:
        1. 可以为空二叉树,即n=0
        2. 可以由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树
         
    - 注意,二叉树是一种特殊的树形结构,其特点是每个结点至多有两棵子树(即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒,若将次序颠倒了,则成为了另一棵不同的二叉树,另外即使树中结点只有一棵子树,也要区分它是左子树还是右子树。
        
    - 二叉树 不等于 度为2的有序树
        1. 度为2的有序树至少要有3个结点,但二叉树可以为空。
        2. 度为2的有序树的左右结点是相对而言的,若某个结点只有一个孩子,则无需区分左右次序,但二叉树在这种情况下就要进行区分。即二叉树的结点次序不是相对于另一个结点而言的,而是确定的。
     
    二叉树的性质
        1. 非空二叉树上的叶结点树等于度为2的结点数+1
        2. 非空二叉树的第i层最多有 2^(i-1) 个结点(i>=1)
        3. 高度为h的二叉树,最多有 2^h-1 个结点

4. 满二叉树

    - 一棵高度为h,且有 2^(h-1) 个结点的二叉树称为满二叉树,即二叉树的每层都含有最多的结点。
    - 特点
        1. 叶结点都集中在二叉树的最下面一层
        2. 除叶结点外,每个结点度数均为2
    - 按层序编号:约定编号从根结点开始(根结点编号为1)起,自上而下,自左向右。
         每个结点对应一个编号,对应编号为i的结点,若有双亲,则其双亲 |i/2| ,若有左孩子,则左孩子为2i,若有右孩子,右孩子编号为2i+1

5. 完全二叉树

    - 高度为h,有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中的编号为1~n的结点一一对应时,称为完全二叉树
    - 特点
        1. 若i<=|n/2|,则结点i为分支结点,否则为叶结点
        树中除了分叉节点就是叶结点,这句话对吗?
        这句话不完全对。
        在树结构中,节点通常分为内部节点(也称为分支节点)和叶节点。分支节点是有子节点的节点,叶节点是没有子节点的节点。然而,还有一种特殊情况,即树中只有一个根节点,它既不是分支节点(因为没有父节点),也不是叶节点(因为在一般定义下,叶节点是根节点的后代,且没有子节点)。所以树中除了分叉节点和叶结点外,在特殊情况下还可能存在单独的根节点。因此,“树中除了分叉节点就是叶结点” 这句话是不对的。

        2. 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点,都依次排列在该层的最左边的位置上。
        3. 若有度为1的结点,则最多只可能有1个,且该结点只有左孩子无右孩子
        4. 按层序编号后,一旦出现某结点的编号i为叶结点或只有左孩子,则编号大于i的结点均为叶结点
        5. 若n为奇数,则每个分支结点都有左右孩子;若为偶数,则除了编号最大的分支结点只有左孩子无右孩子,其余结点都有左右孩子
        6. 当i>1时,结点i的双亲结点的编号为|i/2|,如果有左右孩子,则左孩子编号为2i,右孩子编号为2i+1
        7. 结点i所在的层次(深度)为 |log2(i)| + 1
        8. 具有n个结点的完全二叉树的高度为log2(n+1) log2(n) + 1;

6. 二叉排序树

    - 左子树上所有结点的关键字均小于根结点的关键字;右子树上所有结点的关键字均大于根结点的关键字;左右子树又各是一棵二叉排序树

7.平衡二叉树

    - 树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1

8.正则二叉树

    - 树中每个分支结点都有2个孩子,即树中只有度为0或2的结点

文章如有出错不足处,欢迎评论区指出,如果觉得文章不错,就给我点个赞吧,谢谢!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34604.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android 14 Telephony 网络选择功能介绍

一、总体介绍 (一)功能 手动搜网的流程:用户通过UI触发,调用TelephonyManager的API,比如startNetworkScan,然后这个请求会传递到RIL层,通过AT命令与基带通信,进行网络扫描。结果返回后,经过TelephonyRegistry通知应用层。中间可能涉及IPC,比如Binder通信,因为应用和…

系统思考全球化落地

感谢加密货币公司Bybit的再次邀请&#xff0c;为全球团队分享系统思考课程&#xff01;虽然大家来自不同国家&#xff0c;线上学习的形式依然让大家充满热情与互动&#xff0c;思维的碰撞不断激发新的灵感。 尽管时间存在挑战&#xff0c;但我看到大家的讨论异常积极&#xff…

位运算(基础算法)

按位与AND&#xff08; & &#xff09; 只有当两个位都为1时&#xff0c;结果才为1,否则为0。结果不会变大 按位或 OR&#xff08; | &#xff09; 只有当两个位中有一个为1时&#xff0c;结果才为1,否则为0。结果不会变小 按位异或 XOR &#xff08; ^ &#xff09; 只…

规模效应的三重边界:大白话解读-deepseek为例

前言&#xff1a;当Scaling Laws遇见边际递减效应 在人工智能的狂飙突进中&#xff0c;大语言模型如同不断膨胀的星体&#xff0c;吞噬着海量算力与数据。OpenAI于2020年揭开的Scaling Laws&#xff0c;曾为这场盛宴指明方向&#xff1a;模型性能随参数规模&#xff08;N&…

力扣143重排链表

143. 重排链表 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#xff1a; L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的…

wow-rag:task3-初步体验问答引擎

做RAG需要自己准备一个txt文档&#xff0c;新建一个docs文件夹&#xff0c;放进去。例如&#xff0c;这里放了一个./docs/问答手册.txt # 从指定文件读取&#xff0c;输入为List from llama_index.core import SimpleDirectoryReader,Document documents SimpleDirectoryRead…

bgp服务器是什么意思

一、基础概念 ‌BGP服务器‌&#xff08;Border Gateway Protocol Server&#xff09;指通过 ‌边界网关协议&#xff08;BGP&#xff09;‌ 实现 ‌多运营商线路智能调度‌ 的服务器&#xff0c;能够自动选择最优路径连接不同网络&#xff08;如电信、联通、移动&#xff09;…

AtCoder Beginner Contest 397(ABCDE)

目录 A - Thermometer 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; B - Ticket Gate Log 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; C - Variety Split Easy 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; D - Cubes 翻译&#xff1a…

unserialize3 [有难度,序列化反序列化知识点]

详情: 地址:https://adworld.xctf.org.cn/challenges/list (unserialize3) 看到题目名称是反序列化 代码审计 <?php class xctf{// 定义一个公有属性$flag&#xff0c;通常CTF题目中需要获取该属性值public $flag 111; // 此处为示例值&#xff0c;实际可能为真实flag/*…

【Linux-传输层协议TCP】TCP协议段格式+确认应答+超时重传+连接管理机制(三次握手、四次挥手、理解TIME_WAIT + CLOSE_WAIT)

TCP协议 TCP全称为“传输控制协议&#xff08;Transmission Control Protocol&#xff09;”人如其名&#xff0c;要对数据的传输进行一个详细的控制。 1.TCP协议段格式 下面是TCP报头各个字段的表格形式&#xff1a; 字段名称字段大小描述源端口16位发送端TCP端口号。目的端…

《AI大模型趣味实战》No2 : 快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中)

快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中) 摘要 在上一篇文章中&#xff0c;我们介绍了如何搭建一个基础的家庭网站&#xff08;V1.0版本&#xff09;&#xff0c;包含了用户管理、相册管理、时间线和日历等功能。本文将继续深入&#xff0c;详细…

React(二):JSX语法解析+综合案例

事件绑定 this绑定方式 问题&#xff1a;在事件执行后&#xff0c;需获取当前类的对象中相关属性&#xff0c;此时需要this——当打印时&#xff0c;发现this为undefined,这又是为啥&#xff1f; 假设有一个btnClick函数&#xff0c;但它并不是我们主动调用的&#xff0c;而是…

One of the configured repositories failed (未知), and yum doesn‘t have enough cached data to continue

centos操作系统运行yum命令是出现如下报错&#xff1a; 解决办法&#xff1a; 由于CentOS的源地址内容已移除&#xff0c;CentOS 操作系统结束了生命周期&#xff0c;源地址内容已移除。 只需要将它的base源换成其他可用源&#xff0c;我这里将它换成了阿里的base源 备份原来…

【蓝图使用】绘制mesh顶点的法线

文章目录 绘制法线Normal准备工作UE5资源制作蓝图制作 参考 绘制法线Normal 参考[1]打算用蓝图走一遍渲染管线&#xff0c;还是可以的 准备工作 Blender制作一个三个顶点的模型 要不要材质无所谓&#xff0c;就一个三个顶点的mesh即可&#xff0c;参考[2] 找到一个法线贴…

202503执行jmeter压测数据库(ScyllaDB,redis,lindorm,Mysql)

一、Mysql 1 、 准备MySQL 连接内容 2 、 下载连接jar包 准备 mysql-connector-java-5.1.49.jar 放到 D:\apache-jmeter-5.6.3\lib\ext 目录下面; 3 、 启动jmeter ,配置脚本 添加线程组---》JDBC Connection Configuration---》JDBC Request---》查看结果树。 1)测…

f-string高级字符串格式化与string Template()

f-string 高级字符串格式化 f-string无法替换带有${name}的字符串&#xff0c;会保留\$ def test_fstring():"""f-string&#xff0c;高级字符串格式化的方式"""s "my name is {name}".format(name李白)print(s)# 无法替换$s &quo…

【Java 优选算法】分治-归并排序

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历 912. 排序数组 解法 使用归并算法 根据中间点划分区间, mid (right left ) / 2将左右区间排序合并两个有…

docker入门篇

使用docker可以很快部署相同的环境,这也是最快的环境构建,接下来就主要对docker中的基础内容进行讲解.Docker 是一个用于开发、交付和运行应用程序的开源平台&#xff0c;它可以让开发者将应用程序及其依赖打包到一个容器中&#xff0c;然后在任何环境中运行这个容器&#xff0…

Learning vtkjs之ContourLoopExtraction

过滤器 等高线轮廓提取 介绍 这个过滤器可以获取一个cut的相交的循环的线&#xff0c;目前这个案例cut是一个平面&#xff0c;应该是可以支持更多隐式公式 效果 可以设置这个平面的原点Origin 法线方向Normal&#xff0c;然后就可以求交了 核心代码 需要实现这个代码主要…

如何高效解决 Java 内存泄漏问题方法论

目录 一、系统化的诊断与优化方法论 二、获取内存快照&#xff1a;内存泄漏的第一步 &#xff08;一&#xff09;自动生成 Heap Dump &#xff08;二&#xff09;手动生成 Heap Dump 三、导入分析工具&#xff1a;MAT 和 JProfiler &#xff08;一&#xff09;MAT (Memor…