专栏首页老沙课堂数据结构与算法(六) 二叉树

数据结构与算法(六) 二叉树

二叉树(Binary Tree)

二叉树(Binary Tree)

•每个节点的最大为2。•左子树和右子树是有序的。•即使某个节点只有一颗子树,也要区分是左右子树。

性质

非空二叉树的第i层,最多有2^(i - 1)个节点。

对于任何一颗非空二叉树,如果叶子节点的个数为n0,度为2的节点个数为n2,则有n0 = n2 + 1。

•假设度为1的节点数为n1 那二叉树的节点总数为n = n0 + n2。•二叉树的边数T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 -1 。

真二叉树(Proper Binary Tree)

所有节点的度为0或者为2。

满二叉树(Full Binary Tree)

所有节点的度为0或者为2(真二叉树)&& 所有的叶子节点都在最后一层。

n (节点总数量) = 2^0 + 2^1 +2^2 +...+2^(h-1) = 2^h - 1

h = log2^(n + 1)

完全二叉树(Complete Binary Tree)

叶子节点只会出现最后2层,而且最后1层的节点都向左对齐

•度为1的节点只有左子树•度为1的节点个数<=1•同样节点个数的二叉树,完全二叉树的高度最小•假设完全二叉树的高度为h(h>=1)那么•至少有2^(h - 1)个节点•至多有2^h - 1个节点(满二叉树)•总结点数量为n•2^(h-1) <= n < 2^h•h - 1 <= log2^n < h •h = floor(log2^n) + 1 •floor()向下取整•ceiling向上取整

练习

如果有一颗完全二叉树有589个节点 求叶子节点个数

假设:

叶子节点个数为n_0

度为1的节点个数为n_1

度为2的节点个数为n_2

总节点个数为T

就有

T = n_0 + n_1 + n_2

已知 n_0 = n_2 + 1

所以

T = n_0 + n_1 + (n_0 - 1) = 2n_0 + n_1 - 1

因为T = 589 完全二叉树度为1的节点个数<= 1

假设n1 = 1

589 = 2n_0 + 1 - 1

n_0 = 494.5

不成立

假设n1 = 0

589 = 2n_0 + 0 - 1

n_0 = 495

成立

所以叶子节点的个数为495

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-09

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(十一)B树

    •1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索树的一些特质(小的子节点在左面 大的子节点在右面)•平衡,每个节点的所有子树高度一致•比较矮

    老沙
  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • 数据结构与算法(六) 二叉树遍历

    •任意一个节点的值都大于其左子树的值•任意一个节点的值都小于其右子树的值•他的左右子树也是一颗二叉搜索树•二叉搜索树可以大大提高效率(搜索和添加删除时间复杂度都...

    老沙
  • 重温数据结构系列随笔:单链表(c#模拟实现)

    上一节我们讲述了数据结构的基本概念,这一节让我们来讨论下单链表的概念和实现 我从书中简单摘录下单链表概念 ? 简单而言单链表的是通过许多节点构成,每个节点...

    逸鹏
  • Java集合,TreeMap底层实现和原理

    文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会...

    用户6182664
  • 深入理解什么是B+树

    上一篇已经详细的介绍了什么是B树,但B树这种结构仍有不足之处,比如对范围检索就比较费劲,所以科学大佬们就继续改造扩展,在B树的基础上发明了B+树,上篇文章中也简...

    我是攻城师
  • 数据结构图文解析之:树的简介及二叉排序树C++模板实现.

    Tencent JCoder
  • 人工智能搜索策略(上)

       广度优先搜索: 从初始节点S0开始逐层向下扩展,在第n层节点还没有全部搜索完之前,不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序,先进...

    racaljk
  • zookeeper知识结构3-分布式锁

    zk相关文章已经有了三篇《zookeeper-paxos》、《zookeeper知识结构》、《zookeeper知识结构2-zab协议》

    码农戏码
  • 在Selenium Webdriver中使用XPath Contains、Sibling函数定位

    前言 在一般情况下,我们通过简单的xpath即可定位到目标元素,但对于一些既没id又没name,而且其他属性都是动态的情况就很难通过简单的方式进行定位了。 在这...

    苦叶子

扫码关注云+社区

领取腾讯云代金券