专栏首页hui树和二叉树

树和二叉树

树和二叉树
  • 树的定义和基本术语
  • 二叉树的定义
  • 二叉树的性质
  • 线索二叉树
  • 森林与二叉树的转换
  • 哈夫曼树的基本概念
    • 构造哈夫曼树口诀

树的定义和基本术语

树(Tree) 是 n (n >= 0)个结点的有限集。

在任意一颗非空树中:

​ 1. 有且仅有一个 根(root) 结点

​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(SubTree)

树的 结点 包含一个数据元素及或干个指向子树的分支。

根结点:非空树中无前驱结点的结点。

结点的度:结点拥有的子树数。

度为 0 的结点称为 叶子(Leaf)或 终端结点

结点的子树的根称为该结点的 孩子,该结点称为孩子的 双亲

树的度:树内各结点的度的最大值。

树的深度:树中结点的最大层次。

有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。

无序树:树中结点的各子树无次序。

森林:是 m(m >= 0)棵互不相交的树的集合。

  • 把根结点删除,树就变成了森林。
  • 一棵树可以看成是一个特殊的森林。
  • 给森林中的各子树加上一个双亲结点,森林就变成了树。

树 一定是 森林

森林 不一定是 树

二叉树的定义

二叉树(Binary Tree)是 n (n >= 0)个结点的有限集,它或者是空集 (n= 0),或者由一个根结点两棵互不相交 的分别称作这个根的 左子树右子树 的二叉树组成。

特点

  1. 每个结点最多有俩孩子(二叉树中不存在度大于 2 的结点)。
  2. 子树有左右之分,其次序不能颠倒。
  3. 二叉树可以是空集合,根可以有空的左子树或空的右子树。

注:虽然二叉树与树概念不同,但有关树的基本术语对二叉树都适用。

二叉树的性质

完全二叉树:深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的 满二叉树中编号 为1 ~ n的结点一一对应时, 称之为完全二叉树。

满二叉树 一定是 完全二叉树

完全二叉树 不一定是 满二叉树

注:在满二叉树中,从最后一个结点开始,连续 去掉 任意 个结点,即是一棵完全二叉树。(一定是连续的去掉!!!

性质4: 具有 n 个结点的完全二叉树的深度为

\lfloor{log2^n}\rfloor + 1

性质5:如果对一棵有 n 个结点的 完全二叉树(深度为

\lfloor{log2^n}\rfloor + 1

的结点按层序编号(从第1层到第

\lfloor{log2^n}\rfloor + 1

层,每层从左到右),则对任一结点 i(1 <= i <= n),有:

  1. 如果 i = 1,则结点 i 是二叉树的根,无双亲;如果 i >1,则其 双亲是结点
\lfloor{i/2}\rfloor

  1. 如果 2i > n,则结点 i 为叶子结点,无左孩子;否则,其 左孩子是结点 2i
  2. 如果 2i + 1 > n,则结点 i 无右孩子;否则,其右孩子是结点 2i + 1

性质4:表明了完全二叉树 结点数n 与完全二叉树 深度k 之间的关系 。

性质5:表明了完全二叉树中 双亲结点编号孩子结点编号 之间的关系。

线索二叉树

利用二叉链表中的空指针域:

  • 如果某个结点的 左孩子为空,则将空的左孩子指针域改为 指向其前驱
  • 如果某结点的 右孩子为空,则将空的右孩子指针域改为 指向其后继
  • 这种改变指向的指针称为 "线索”
  • 加上了线索的二叉树称为 线索二叉树(Threaded Binary Tree)
  • 对二叉树按某种遍历次序使其变为线索二叉树的过程叫 线索化

森林与二叉树的转换

树变二叉树:兄弟相连留长子

二叉树变树:左孩右右连双亲,去掉原来右孩线

森林变二叉树:树变二叉跟相连

二叉树变森林:去掉全部右孩线,孤立二叉再还原

哈夫曼树的基本概念

路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度:两个结点间路径上的 分支数

树的路径长度:从 树根 到每个结点的 路径长度之和。记住:TL

结点数目相同的二叉树中,完全二叉树是路径长度最短的二叉树。

权(weight):将树中结点赋给一个有着某种含义的数值,则这个数值称为该 结点的权

结点的带权路径长度:从 根结点 到该结点之间的 路径长度 与该结点的 乘积

树的带权路径长度:树中所有 叶子 结点的 带权路径长度之和

哈夫曼树:最优树(带权路径长度(WPL)最短的树)。

“带权路径长度最短”是在“度相同” 的树中比较而得的结果,因此有最优二叉树、最优三叉树之称等等

哈夫曼树:最优二叉树(带权路径长度(WPL)最短的二叉树)。

构造哈夫曼树口诀

​ 1. 构造森林全是根

​ 2. 选用两小造新树

​ 3. 删除两小添新人

​ 4. 重复 2、3 剩单根

包含 n 棵树的森林要经过 n - 1次合并才能形成哈夫曼树,共产生 n - 1 个新结点。

包含 n 个叶子结点的哈夫曼树中共有 2n - 1 个结点。

哈夫曼树的结点的度为 0 或 2,没有度为 1 的结点。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 顺序表与链表的比较

    结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

    忆想不到的晖
  • 单链表的头尾插法详解

    head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL;

    忆想不到的晖
  • C语言实现单链表

    单链表是由多个结点链接组成,它的每个结点包含两个域,一个数据域和一个链接域(地址域)。

    忆想不到的晖
  • 数据结构简单要点总结(转)

    栈是只能在一端进行插入和删除的线性表。 (别看只是个定义,非常重要,已经道出了运算方法:只能在一端插入和删除。)

    Locker
  • 数据结构和算法浅读

    程序=数据结构+算法 最近看数据结构方面的知识,整合记录下来,部分文章是转载的,链接贴后面

    深雾
  • 前端学习数据结构与算法系列(四):哈希、堆和二叉查找树

    当元素进行 mod 运算后,可能会与其他元素的 mod 值一样,此时数组中已经有其他元素占了这个下标位置,这种存储位置重复了的情况便叫做 冲突,我们来看个例子:

    一只图雀
  • 图解红黑树

    红黑树(Red Black Tree)是一种含有红黑结点并能自平衡二叉查找树,典型的用途是实现 map。

    Dabelv
  • 面试被问“红黑树”,我一脸懵逼......

    红黑树(Red Black Tree)是一种自平衡的二叉搜索树(Self-balancing Binary Search Tree)。以前也叫做平衡二叉 B 树...

    五分钟学算法
  • 红黑树

    每个结点不是红色就是黑色 不可能有连在一起的红色结点 根结点都是黑色 每个红色结点的两个子结点都是黑色 任一结点到其子树中每个叶子节点的路径都有相同数量...

    瑞新
  • 漫画:什么是AVL树?(修订版)

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰

扫码关注云+社区

领取腾讯云代金券