专栏首页编程理解数据结构(一):二叉树

数据结构(一):二叉树

定义

二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

  • 三个不相交的节点集合构成,一个作为根节点,一个节点集构成的二叉树作为根节点的左子树,另一个节点集构成的二叉树作为根节点的右子树
  • 当节点数为零时,表示二叉树为空

所以节点个数为零的空树也是二叉树,二叉树根节点的左、右子树也是二叉树,其结构同样符合以上定义,当左子树为空树时,表示根节点没有左子节点。且二叉树区分左、右子树,以下两个二叉树为不同的二叉树。

one

another one

结构特性

首先说明下几个概念:

  • 根节点: 没有父节点的节点;
  • 叶子节点: 没有子节点的节点;
  • 节点的度 :节点的分支个数,二叉树每个节点的分支个数为 0~2;
  • 路径:连接节点和后代子节点之间的不重复边;
  • 节点的深度:从根节点到该节点的路径长;
  • 节点的高度:从该节点到叶子节点的最大路径长;
  • 节点的层数:父节点的层数加一;
  • 树的高度:根节点高度。
  • 树的深度:叶子节点深度的最大值。

关于高度和深度的起始值 0 或 1 的个人看法:

对于深度、高度和层数的起点值,可能有些地方基数是从1开始计算的。对于这个起点值的设置,个人觉得如果你高兴,从10086开始也无妨,因为在应用中,这些数据量只是为了方便计算,起作用的只是相对值而已。

为了方便理解,这里设置基数为0,深度可以认为是从水平面,也就是0深度,往下有几层,深度就是几;高度类似理解,地平面是0,往上有几层,高度就是几。

参考下图:

图片来源:What is the difference between tree depth and height?


满二叉树、完全二叉树、完美(理想)二叉树

关于完全二叉树和满二叉树的定义,因为最初翻译的不同,已经混淆很久了,所以已经属于一个历史问题了。这里尽量不去分辨哪一种定义是正确的,只按照个人的理解去描述。

  • 满二叉树( Full Binary Tree ): 每个节点的度为 0 或 2,即除了叶子节点,每个节点都有两个子节点。

示例:

Full Binary Tree

  • 完全二叉树( Complete Binary Tree ): 除深度最大的一层外,其他每层上的节点都是填充满的,且深度最大的一层节点分布从左向右是连续无间隔的。

示例:

Complete Binary Tree

  • 完美/理想二叉树( Perfect Binary Tree ): 除叶子节点外,每个节点度都为 2,且叶子节点在同一层。

示例:

Perfect Binary Tree

以上概念参考:


二叉树数据量

下面介绍二叉树几个数据量之间的关系,变量声明如下:

:树的高度

:节点总数

:度为 0 的节点个数,即叶子节点个数

:度为 1 的节点个数

:度为 2 的节点个数

:第

层上节点个数

  • 完美二叉树中,第

层上节点个数为:

proof: 1.第 0 层上,只有根节点,所以 0 层节点个数为:

; 2.每层节点度都为 2 ,所以下一层的节点个数为:

; 3.所以第

层节点个数为:

  • 深度为

的完美二叉树,节点总数为:

proof: 1.每层的节点个数

构成等比数列,公比为:

; 2.第 0 层节点个数

,所以总节点个数为:

  • 深度为

的完美二叉树,非叶子节点和叶子节点的个数有:

,节点总数与叶子节点个数有:

proof: 深度为

的完美二叉树,则

层节点即为叶子节点,即:

,由以上结论可知,深度为

的完美二叉树,叶子节点个数为

,总节点个数为

,所以非叶子节点个数为:

,即:

  • 对于普通的非空二叉树,叶子节点个数

与度为 2 的节点个数

关系为:

proof: 1.设度为 1 的节点个数为

,则节点总数

2.设二叉树中边的个数为

,有如下关系: 【1】树中除根节点外,每个节点都存在该节点到其父节点的一条边,即除根节点外,每个节点都对应着一条边,则有关系:

【2】树中每个节点度,表示该节点的子节点个数,也表示着该节点对应的边的个数,则有关系:

根据【1】【2】可知,有关系:

,根据 1 中

,则有:

,即:

,二叉树中叶子节点个数为度为 2 的节点个数加 1。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序算法(五):堆排序

    的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节...

    zhipingChen
  • Leetcode 993. 二叉树的堂兄弟节点

    在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

    zhipingChen
  • 数据结构(六):红黑树

    级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断,红黑树给节点赋予了颜色属性,并通过对树中节点的颜色进行限制,来保持整棵...

    zhipingChen
  • [LeetCode] Symmetric Tree

    1、题目名称 Symmetric Tree https://leetcode.com/problems/symmetric-tree/ 2、题目内容 Give...

    程序员小王
  • 纸上谈兵: 树, 二叉树, 二叉搜索树

    树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

    Vamei
  • 重温数据结构:深入理解红黑树

    读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红...

    张拭心 shixinzhang
  • 二叉树-堆

    完全二叉树:叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大;

    搬砖俱乐部
  • CDH离线安装文档

    准备工作 1, 配置hostname vi /etc/sysconfig/network 修改hostname: NETWORKING=yes ...

    shengjk1
  • Druid实时OLAP数据分析存储系统极简入门

    Druid 是一个开源的,分布式的,列存储的,适用于实时数据分析的存储系统,能够快速聚合、灵活过滤、毫秒级查询、和低延迟数据导入。

    王知无
  • 图表示学习起源: 从Word2vec到DeepWalk

    本文发表在知乎专栏<435算法研究所>,介绍的是2014年的一篇文章《DeepWalk: Online Learning of Social Represent...

    Houye

扫码关注云+社区

领取腾讯云代金券