作者: 牛油果大虾 | 来源:发表于2021-04-15 16:23 被阅读0次

数据结构中的树,是对现实世界中的树的一层简化: 把树根抽象为根节点,述职抽象为边,树枝的两个端点抽象为节点, 树叶抽象为叶字节点。抽象后的树结构如下:


image.png

把这棵树抽象颠倒一下就得到了计算机中的树结构:


image.png
结合这张图,我们来讲解树的关键特性和重点概念。
  • 树的层次计算规则: 跟节点所在的层为第一层,其自己点所在的为第二层,以此类推
  • 结点和树的“高度”计算规则:叶子结点高度记为1,每向上一层高度就加1,逐层向上累加至目标结点时,所得到的的值就是目标结点的高度。树中结点的最大高度,称为“树的高度”。
  • 度的概念: 一个节点开叉出去多少子树,即为度
  • 叶子节点就是度为0的结点

二叉树

二叉树是指满足一下要求的树

  • 它可以没有根节点作为一棵空树存在
  • 如果他不是空树,那么他必须有根节点,左子树和右子树组成,且左右子树都是二叉树

image.png

二叉树的编码实现

在js中定二叉树,他的结构分为3块

  • 数据域
  • 左侧子节点的引用
  • 右侧子节点的引用
//二叉树节点的构造函数
function TreeNode(val){
  this.val = val
  this.left = this.right = null
}

当需要新建一个二叉树时,直接调用构造函数传入数据域的值就行了:

const node = new TreeNode(1)

如此便能得到一个值为1的二叉树节点,从结构上来说,他张这样:


image.png

以这个节点为根节点,我们可以通过给left、right赋值拓展其子树信息,延展出一棵二叉树。因此从更加细化的角度来看,一棵二叉树的形态实际是


image.png

相关文章

  • 水彩过程 | 树树树树

    练习了一下树的画法,用毛笔勾树干,扇形笔画树叶还是又快又方便的。因为不是写实风格,只要把树的意象画出来就可以,所以...

  • 树·树

    ​如果有来生,要做一棵树,站成永恒,没有悲欢姿势,一半在尘土里安详。一半在风里飞扬,一半洒落阴凉,一半沐浴阳光。 ...

  • 树,树……

    树,树…… ——洛尔迦 树,树, 枯了又绿。 脸蛋美丽的姑娘 在那里摘橄榄。 风,塔楼上的求爱者, 拦腰把她...

  • 橄榄树树树

    在建班级群的时候,我顺手打了三个树——橄榄树树树。是的,这是橄榄树第三次起航。 第一次,在北京,我说,我愿意在无人...

  • 树,与树

    (第一次学着简书里文友看图写诗,2020的图,各位讲究着看吧) 文/三少爷的糖 一颗树站在山头 遥望着远方,朦胧中...

  • 树,与树

    我不是一个很喜欢女生哭闹的人。 哭闹,意味着理智被情感摧毁。 理智没了,沟通渠道也就关闭了。 没有了沟通,剩下的就...

  • 树和树

    我的家门前有一棵柏树,不是什么稀罕的树,但它却挺直腰杆儿,坚定的伫立在我家门前,望着远方,似乎在等什么人又不像在等...

  • 树树秋声

    余秋雨说:生命,是一树花开,或安静或热烈,或寂寞或璀璨。日子,就在岁月的年轮中渐次厚重,那些天真的、跃动的、抑或沉...

  • 短篇‖树树

    这是一条幽静的古道,两旁尽是残垣断壁,竟也有一些台阶通向几栋还算有顶篷的石质的建筑物。我和我的伙伴着级上了一段...

  • 树树夜夜

    长夜唧唧夏虫前 长街相对两树闲 冠盖接云皆无语 此缘如可问苍天

网友评论

      本文标题:

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