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

二叉树(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 条评论
登录 后参与评论

相关文章

来自专栏微信公众号【Java技术江湖】

这几道Java集合框架面试题在面试中几乎必问

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结...

7830
来自专栏bigsai

数据结构与算法—深度、宽度优先(dfs,bfs)搜索

在有向图和无向图中,如果节点之间无权值或者权值相等,那么dfs和bfs时常出现在日常算法中。不仅如此,dfs,bfs不仅仅能够解决图论的问题,在其他问题的搜索上...

10510
来自专栏Java那些事

460道Java后端面试高频题

转自公众号:码农求职小助手

17920
来自专栏开发笔记

B+Tree索引原理

如果要查“mysql”这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql。如果没有索引,那么你可能需要把所有单词看一遍才能找到你想要...

9830
来自专栏大学生计算机视觉学习DeepLearning

c++ LeetCode (网易面试题和链表以及树篇) 五道算法例题代码详解(三)

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

9730
来自专栏光城(guangcity)

如何提高编程能力?(下)

同时也说明了一个问题对于z=(x++,y++,++y);中,y++执行完后,再去执行++y,即y++后,y变为2,++y变为3.而不是先y++,只按照赋值,后面...

12420
来自专栏bigsai

哈夫曼树(最优二叉树)详解与构造

其中WPL表示计算出的权值。至于为什么按照哈夫曼树方法构造得到的权重最小。这里不进行证明。对于哈夫曼树,他的每个非叶子节点都有两个孩子因为哈夫曼树的构造就是自底...

23520
来自专栏光城(guangcity)

n种解法破DFS与BFS

0.说在前面1.二叉树的层次遍历I1.1 BFS非递归思路11.2 BFS非递归思路21.3 BFS双端队列1.4 BFS递归思路1.5 DFS递归思路2.二...

9420
来自专栏bigsai

数据结构与算法—我来带你征服恐惧已久的AVL树(二叉平衡树)

前面学习二叉查找树和二叉树的各种遍历,但是其查找效率不稳定(斜树),而二叉平衡树的用途更多。查找相比稳定很多。(欢迎关注数据结构专栏)

11030
来自专栏思考是一种快乐

机器学习-异常检测算法(一):Isolation Forest

转自: https://zhuanlan.zhihu.com/p/27777266

7710

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励