ㅤcoderitl

V1

2022/02/07阅读:47主题:萌绿

树、二叉树、森林

树和二叉树

  • 树是一种新的逻辑结构

集合: 数据元素间除了"同属于一个集合"外,无其他关系
线性结构: "一对一的关系",如线性表,栈、队列、串
树形结构: "一对多的关系",如: 树
图形结构: "多对多"的关系,如: 图

  • 常见的树形结构

目录
家庭关系
文件目录
...

  • 树的定义

    • 树是n个节点的有限集
    • 节点个数为的树成为空树
    • 任意一个非空树中n>0
    • 有且仅有一个特定的称为的节点
    • 非根的节点可以分为互不相交的有限集,每个集合本身又是一棵树,这些树称为子树
    • : 节点最多分叉数量
  • 节点的层次: 到该节点层数

 树的度:
      根的度:
      关系树的度:

    树的深度:
      从根节点垂直向下数
  • 树的家谱图

    双亲 上层的节点(直接前驱)
    孩子 下层节点的子树的根(直接后驱)
    祖先 从根到该节点所经分支的所有节点
    子孙 该节点下层子树中的任一节点
    兄弟 同一双亲的同层节点
    堂兄弟 双亲位于同一层的节点(但并非同一双亲)
  • 森林

    森林: 删除根节点后不相交的树的集合
    有序树: 节点各子树从左至右有序,不能互换(左为第一)
    无序树: 节点各子树可互换位置

二叉树(Binary Tree):

  • 二叉树是n >= 0个节点所构成的集合,它或为空树n = 0;或非空树,对于非空树T

    • 有且仅有一个称之为的节点
    • 除根以外的其余节点分为两个互不相交的子集T_1T_2,分别称为T的左子树和右子树,且T_1T_2本身又都是二叉树
  • 二叉树的特点及与树的异同

    二叉树
    具有递归性 具有递归性
    至多只有两颗子树(节点的度不超过 2) 没有限制子树个数的上限
    子树有左右之分,其次序不能任意颠倒(有序树) 子树可能有有序,也可能无序
  • 叉树的几种形态

    image.png
    image.png
  • 三节点二叉树的五种形态

    image.png
    image.png
  • 为什么研究二叉树

    普通树(多叉树)不转化为二叉树,运算很难实现
    为何要重点研究每个节点最多只有两个二"叉"的树
    可以证明,所有树都能转化为唯一对应的二叉树,不失一般性。

二叉树的性质

  • 性质一

    在二叉树的第 i 层上至多有2^(i-1)个节点

  • 性质二

    深度为k的二叉树至多有(2^k)-1个节点
    深度为 1: 1=(2^1)-1个节点
    ...

  • 性质三

    对于任何一个二叉树,若 2 度的节点数有n_2个,则叶子数n_0必定为n_2+1,即 n_0 = n_2 + 1

完全二叉树与满二叉树

满二叉树 完全二叉树
满二叉树 完全二叉树
深度为k且含有(2^k)-1个节点的二叉树 深度为k,有n个节点的二叉树,当且仅当其每个节点都与深度为k的满二叉树中(自上而下从左往右)编号从1n的节点一 一对应
  • 满二叉树的特点
    1. 每一层上的节点树都是最大节点数
    2. 每一层 i 的节点树都具有最大值 2^(i-1)

树和二叉树的转换及其应用

树转换为二叉树

  • 转换的实现步骤

    1. 加线: 在兄弟之间加一条连线
    2. 抹线: 在每个节点,除了其左孩子外,去除其余孩子之间的关系
    3. 以树的节点为轴心,将整树顺时针旋转45°
    树转换为二叉树(01)
    树转换为二叉树(01)
    树转换为二叉树(02)
    树转换为二叉树(02)

二叉树转换为树

  1. 加线: 若p节点是双亲节点的左孩子,则将p的右孩子,右孩子的右孩子...沿分支找到的所有右孩子,都与p的双亲用线连起来
  2. 抹线: 抹掉原二叉树中双亲与右孩子之间的连线
  3. 将节点按层次排列,形成树结构
二叉树转换为树
二叉树转换为树

森林

森林转换为二叉树(二叉树与多颗树之间的关系)

  1. 将各棵树分别转换成二叉树
  2. 将每棵树的根节点用线相连
  3. 以第一颗树根节点为二叉树的根,再以根节点为轴心,顺时针旋转,构成二叉树型结构
森林转换为二叉树
森林转换为二叉树

二叉树转换为森林

  1. 抹线: 将二叉树中根节点与其右孩子连线,沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树
  2. 还原: 将孤立的二叉树还原成树
二叉树转换为森林
二叉树转换为森林

分类:

后端

标签:

C++

作者介绍

ㅤcoderitl
V1