美文网首页【打基础】算法集
【数据结构】关于树,你需要知道的几件事

【数据结构】关于树,你需要知道的几件事

作者: 拜仁的月饼 | 来源:发表于2019-11-21 16:53 被阅读0次

0. 前言

本文不是从入门到精通式的文章。写该文的目的是理清树结构及其解题思路,所以讲解不多而概念性的东西比较多,请见谅。

本文结构:

  1. 概念铺垫
  2. 二叉树
  3. 各种相关算法
  4. 例题相关

1. 概念铺垫

  1. 树等价于连通无环图,由一组顶点(vertex)边(edge)构成。其中,如图所示,A点为根顶点(root)。一般情况下,我们多称顶点为节点(node)
图中,ABCDEFG为顶点,T1、T2等为边。(图片来自网络,侵删)
  1. 祖先(ancestor)、后代(descendant)、父亲(parent)、孩子(child)、子树(subtree)、叶子节点(leaf)、度(degree):在节点v寻根过程中经过的每一个节点都是其祖先,节点v是其后代。依旧以上图为例,节点E的祖先是BAEBA的后代,而B又是A的后代。
    父亲<-->孩子是特殊的祖先<-->后代关系。若节点uv的祖先且恰好比v高一层,则称uv的父亲,vu的孩子。例如:BE即为一对父子关系。
    节点u所有的后代及其之间的连接边称为子树,记作subtree(v)。例如图中的B D F就构成一棵子树。当一个节点没有后代(没有孩子)时,我们称之为叶子节点。例如,图中的D E F G都是叶子节点。
    节点u的孩子总数称为u。例如,节点c的度为2,因为 c有两个孩子F G。叶子节点的度为0。

  2. 深度(depth)、高度(height):沿节点vr唯一通路所经过边的数目,称为节点v深度,记作depth(v)。例如上图中,从节点E走到根节点A的边数是2,所以depth(E) = 2。设节点v深度为v_d,那么我们可以认为节点v处于在第v_d层。特别地,约定根顶点root的深度为0,即depth(root) = 0
    T中所有节点深度最大值称作该树的高度,记作height(T)。通常约定,仅有一个节点的树高度为0,空树高度为-1。例如,图中所未二叉树高度为2。有些博客文章、教材、讲义中认为该树高度为3,也正确。因为从直观角度来说是3层树,而本文约定高度为2是为方便编程。

2. 二叉树(binary tree)

二叉树图例

定义:如上图所示,二叉树是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

性质

  • 在二叉树中,每个节点的度\leq 2
  • 同一节点的孩子可以左右区分,即具有左右次序(有序),故二叉树又可称为二叉有序树(ordered binary tree)

2.1 二叉搜索树(Binary Search Tree, BST)

首先要明确一点的是,二叉搜索树满足所有普通二叉树的特征。但相比普通二叉树而言,二叉搜索树又有如下特征:
假定节点为k:

  • 左子树存储着值小于k的节点
  • 右子树存储着值大于k的节点
  • 每棵子树都满足如上两条特征

References

  1. 邓俊辉. 数据结构: C++ 语言版[M]. 清华大学出版社, 2012.
  2. 二叉树--维基百科
  3. GeeksforGeeks二叉搜索树专题(英文版)

相关文章

  • 【数据结构】关于树,你需要知道的几件事

    0. 前言 本文不是从入门到精通式的文章。写该文的目的是理清树结构及其解题思路,所以讲解不多而概念性的东西比较多,...

  • 关于目标,你需要知道的几件事

    要成为首富应先定一个能达到的小目标,比方说我先挣它一个亿。 最近大家是不是被小目标这个词刷爆朋友圈?这个梗是被网友...

  • 关于大学你需要知道的几件事

    我所理解的大学,是思想自由开放的圣地。是真正的知识殿堂。你需要一直学习,无论以哪种方式。关于大学中,你有很多的选择...

  • golang实现二叉搜索树

    关于什么是二叉搜索树,不清楚的同学可以去看我写的这个数据结构与算法的网站 数据结构 首先我们定义需要的数据结构。注...

  • 213 关于“孤独”,你需要知道的几件事

    我们生活的四个既定事实与心理治疗息息相关: 我们每一个人和我们所爱的人都会面临死亡; 我们必须按自己的意愿营生的自...

  • 关于学车你需要知道的几件事

    文/沐夏 学车就像一次朝圣,涅槃,或者说是质疑自我智商之旅,有时弄得人身心俱疲,狼狈不堪。 写写关于学车的那些故事...

  • 关于美白你需要知道的几件事

    1、什么样的皮肤需要美白 不用美白的人:脸部皮肤跟胳膊内侧或者胸部,大腿内侧(这个部位不好对比)相对比,肤色一样。...

  • 关于投资基金你需要知道的几件事?

    1-任何时间进场都不算晚 不管你现在是未毕业的大学生,还是已经毕业几年的上班族,还是养家糊口的奶爸,即使你已...

  • mysql索引

    从数据结构角度 1、B+树索引(O(log(n))):关于B+树索引,可以参考MySQL索引背后的数据结构及算法原...

  • Genos EI:关于情绪,你需要知道的几件事

    Genos EI是一门关于应用情绪在工作中创造绩效的学问,想要真正掌握其精髓,你必须知道关于情绪的几件事。 一、情...

网友评论

    本文标题:【数据结构】关于树,你需要知道的几件事

    本文链接:https://www.haomeiwen.com/subject/fsdnictx.html