首页 > 其他分享 >数据结构—树(自学笔记)(郝斌)

数据结构—树(自学笔记)(郝斌)

时间:2023-05-21 23:00:49浏览次数:55  
标签:遍历 孩子 中序 双亲 二叉树 郝斌 自学 数据结构 节点


文章目录

  • 树的定义
  • 专业定义
  • 通俗的定义
  • 相关术语
  • 树的分类
  • 一般树
  • 二叉树
  • 二叉树的分类
  • 二叉树的性质
  • 对于第一条来说是显然的,i = 1时就是根节点。 i > 1时,比如节点7,它的双亲就是
•            
            
             
              
               ⌊
              
              
               7
              
              
               /
              
              
               2
              
              
               ⌋
              
             
             
              \lfloor 7/2 \rfloor
             
            
           ⌊7/2⌋=3,节点9,它的双亲就是
           
            
             
              
               ⌊
              
              
               9
              
              
               /
              
              
               2
              
              
               ⌋
              
             
             
              \lfloor 9/2 \rfloor
             
            
           ⌊9/2⌋=4。• 第二条,比如节点6,因为2
           
            
             
              
               ×
              
             
             
              \times
             
            
           × 6 =12超过了节点总数10,所以节点6无左孩子,它是叶子节点。同样,而节点5,因为2
           
            
             
              
               ×
              
             
             
              \times
             
            
           ו 第三条,比如节点5,因为2
           
            
             
              
               ×
              
             
             
              \times
             
            
           × 5+1 =11,大于节点总数10,所以它无右孩子。而节点3,因为2
           
            
             
              
               ×
              
             
             
              \times
             
            
           ×
  • 森林
  • 树的存储
  • 链式存储
  • 二叉树的操作
  • 应用

树的定义

专业定义

  • 有且只有一个称为根的节点
  • 有若干个互不相交的子树,这些子树本身也是一颗树

通俗的定义

  • 树是由节点和边组成
  • 每个节点只有一个父节点但可以有多个子节点
  • 但有一个节点例外,该节点没有父节点,此节点称为根节点

相关术语

  • 节点
  • 双亲节点
  • 子节点
  • 子孙
  • 兄弟(同一个双亲节点)
  • 堂兄弟(它们的双亲节点在同一层)
  • 层次
  • 从根节点到最底层节点的层数称为深度或者高度
  • 根节点是第一层
  • 叶子节点
  • 没有子节点的节点
  • 非终端节点
  • 实际非叶子节点
  • 子节点的个数
  • 树的度
  • 树中节点最大的度

树的分类

一般树

  • 任意一个节点的子节点的个数都不受限制

二叉树

  • 任意一个节点的子节点个数最多两个,且子节点的位置不可更改

二叉树的分类

  • 一般二叉树
  • 满二叉树
  • 在不增加树层数的前提下,无法再添加一个节点的二叉树就是满二叉树
  • 高度为h,且有数据结构—树(自学笔记)(郝斌)_子树
  • 完全二叉树
  • 如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树
  • 扩充二叉树(2-树)
  • 仅存在度为2和0的节点
  • 不存在度为1的节点

二叉树的性质

数据结构—树(自学笔记)(郝斌)_子树_02

  1. 在二叉树的第i层上至多有数据结构—树(自学笔记)(郝斌)_算法_03个节点
  2. 深度为k的二叉树至多有数据结构—树(自学笔记)(郝斌)_子节点_04个节点
  3. 对如何一棵二叉树T,如果其终端节点数为数据结构—树(自学笔记)(郝斌)_子节点_05,度为2的节点数为数据结构—树(自学笔记)(郝斌)_二叉树_06,则数据结构—树(自学笔记)(郝斌)_子节点_05 = 数据结构—树(自学笔记)(郝斌)_二叉树_06
  4. 具有n个节点的完全二叉树的深度为数据结构—树(自学笔记)(郝斌)_算法_09+1(数据结构—树(自学笔记)(郝斌)_子节点_10表示不大于x的最大整数)
  5. 如果对一棵有n个节点的完全二叉树,(其深度为数据结构—树(自学笔记)(郝斌)_算法_09+1)的节点按层序编号(从第1层到第数据结构—树(自学笔记)(郝斌)_算法_09+1层,每层从左到右),对任一节点i(1 数据结构—树(自学笔记)(郝斌)_算法_13 i 数据结构—树(自学笔记)(郝斌)_算法_13 n)有:
  1. 如果i = 1,则节点i是二叉树的根,无双亲;如果i >1,则其双亲是节点数据结构—树(自学笔记)(郝斌)_子树_15.
  2. 如果2i > n,则节点i无左孩子,(节点i为叶子节点);否则其左孩子是节点2i。
  3. 如果 2i+1 > n,则节点i无右孩子,否则其右孩子节点是2i+1.
对于第一条来说是显然的,i = 1时就是根节点。 i > 1时,比如节点7,它的双亲就是数据结构—树(自学笔记)(郝斌)_算法_16=3,节点9,它的双亲就是数据结构—树(自学笔记)(郝斌)_二叉树_17=4。
第二条,比如节点6,因为2数据结构—树(自学笔记)(郝斌)_二叉树_18 6 =12超过了节点总数10,所以节点6无左孩子,它是叶子节点。同样,而节点5,因为2数据结构—树(自学笔记)(郝斌)_二叉树_18
第三条,比如节点5,因为2数据结构—树(自学笔记)(郝斌)_二叉树_18 5+1 =11,大于节点总数10,所以它无右孩子。而节点3,因为2数据结构—树(自学笔记)(郝斌)_二叉树_18

森林

  • n个互不相交的树的集合

树的存储

数据结构—树(自学笔记)(郝斌)_子树_22

  • 二叉树的存储
  • 连续存储【完全二叉树】
  • 优点
  • 查找某个节点的父节点和子节点(包括判断有没有子节点)速度很快
  • 缺点:
  • 耗用内存空间过大

链式存储

  • 一般树的存储
  • 双亲表示法
  • 求父节点方便
  • 孩子表示法
  • 求子节点方便
  • 双亲孩子表示法
  • 求父节点和子节点都很方便
  • 二叉树表示法
  • 把一个普通树转化成二叉树存储
  • —>大概思路
  • 设法保证任意一个节点的
  • 左指针域指向他的第一个孩子
  • 右指针域指向它的第一个兄弟
  • 只要能满足此条件,就可以把一个普通树转化为二叉树
  • 一个普通树转化成的二叉树一定没有右子树
  • 具体方法:
  1. 加线。在所有兄弟节点之间加一条连线。
  2. 去线。对树中每个节点,只保留它与第一个孩子节点的连线,删除它与其他孩子节点之间的连线。
  3. 层次调整。以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使其看起来像个二叉树。注意⚠️第一个孩子是二叉树节点的有孩子,兄弟转换过来的孩子是节点的右孩子。
  • 把森林转化为二叉树
  • 大概思路:
  • 森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以安装兄弟的处理办法来操作。
  • 森林的存储
  • 先把森林转化为二叉树,再存储二叉树

二叉树的操作

  • 遍历
  • 先序遍历【先访问根节点
  • 先访问根节点
  • 再先序访问左子树
  • 再先序访问右子树
  • 例子:
  • 中序遍历【中间访问根节点
  • 中序遍历左子树
  • 再访问根节点
  • 再中序遍历右子树
  • 例子:
  • 后序遍历【最后访问根节点
  • 后序遍历左子树
  • 后序遍历右子树
  • 再访问根节点
  • 例子:
  • 已知两种遍历序列求原始序列
  • 通过先序和中序 或者 中序和后序我们可以还原出原始的二叉树
  • 但是通过先序和后序是无法还原出原始的二叉树的
  • 换种说法:
  • 只有通过先序和中序,或通过中序和后序才可以唯一确定一个二叉树
  • 例子(1):
  • 例子(2):

应用

  • 树是数据库中数据组织一种重要形式
  • 操作系统子父进程的关系本身就是一棵树
  • 面向对象语言中类的继承关系本身就是一棵树
  • 赫夫曼数


标签:遍历,孩子,中序,双亲,二叉树,郝斌,自学,数据结构,节点
From: https://blog.51cto.com/u_14090113/6320555

相关文章

  • 2.6 异质的数据结构
    结构C语言的struct声明创建一个数据类型,将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现,结构的所有组成部分都存放在内存中一段连续的区域内,而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息,指示每个字段(......
  • 《数据结构与算法》之数据的顺存储
    导言:数据结构中,对一些数据序列我们使用的是顺序的方式存储,比较常见的有数组,链表,这些都是最基本的顺序存储的结构,我们会用几个简单的例子来描述顺序存储的方式和演变我们知道顺序存储中有链表,有链表我们就必须知道指针,所以我们先复习一下指针,再来看顺序存储一.指针在C语言中,我......
  • 自AI火了之后又一个自学方法
      上图是狐猴浏览器默认提供的chatTPG的ai的使用,我发送不完整代码,也可以准确的猜测出代码的含义。效果十分强大 ......
  • 《数据结构与算法》之十大基础排序算法
    一.冒泡排序什么是冒泡排序?冒泡排序是一种交换排序,它的思路就是在待排序的数据中,两两比较相邻元素的大小,看是否满足大小顺序的要求,如果满足则不动,如果不满足则让它们互换。然后继续与下一个相邻元素的比较,一直到一次遍历完成。一次遍历的过程就被成为一次冒泡,一次冒泡的结束至......
  • Python潮流周刊#1:如何系统地自学Python?
    这里记录每周值得分享的Python及通用技术内容,部分内容为英文,已在小标题注明。(本期标题取自其中一则分享,不代表全部内容都是该主题,特此声明。)文章&教程1、编程语言的错误处理模式文章讨论了编程中处理错误的四种常见方法:返回错误代码(C、Go)、异常(Java、C#、Python、C++)、回调函数(Jav......
  • 数据结构!
    AT_joisc2014_c 歴史の研究该起床了。该起床了。该起床了。该起床了。该起床了。本题删除会改变最大值,十分麻烦,所以使用回滚莫队即可。该起床了。该起床了。该起床了。该起床了。该起床了。P3245 [HNOI2016]大数考虑如何提取区间\([l,r]\)组成的数。设\(SA_i\)......
  • 数据结构基础一
    数据结构基础一1.单链表(数组模拟)常用的是邻接表(其实就是单链表,邻接表就是用多个单链表存储了多条线?!),一般用来存储图和树,使用结构体和指针来表示数组的时候,是使用的动态开辟空间,速度太慢,所以一般使用数组来静态模拟单链表。数组模拟单链表的思路:首先开辟两个足够大的数组,一个是存......
  • 数据结构-基本算法复习
    数据结构-基本算法复习第八章排序插入排序直接插入排序:\(O(n^2)\)稳定排序将一条记录插入到已经排序好的有序表中:voidinsertSort(intr[],intlen){for(inti=2;i<=len;i++){if(r[i]<r[i-1]){ intx=r[i];for(in......
  • 八大常见的数据结构(一)数组、链表、栈、队列
    1、数组数组是用于储存有限个相同类型数据的集合。数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。可通过数组名和下标进行数据的访问和更新。下标从0开始。2、链表链表是一种物理存储单元上非连续、非顺序的存储结构。链表相较于数组,......
  • 数据结构
    数据结构1线性表1.1顺序表1.1.1比较数组大小题目:设A=(a1,a2,am)和B=(b1,b2,...,bn)均为顺序表,A'和B'分别是除去最大公共前缀后的子表。例如,A=(b,e,i,j,i,n,g),B=(b,e,i,f,a,n,g),则两者的最大公共前缀为b、e、i,在两个顺序表中除去最大公共前缀后的......