二叉树（Binary Tree）类型特点

在上一篇《树（Tree）的基本概念》中我们了解了树中常用的一些概念名词。这一篇呢注重说一下二叉树的特点和一些概念。

二叉树的类型

附图1

binary_tree.jpg

真二叉树

真二叉树的每个节点的度要么是0，要么是2 。

以 「附图1」 为例：图中第一行的：空树、只有一个节点的树、最右侧的二叉树；第三行的二叉树都是真二叉树

满二叉树

满二叉树的每个节点的度要么是0，要么是2 ，并且所有的叶子节点都在最后一层。

以 「附图1」 为例：图中第三行的二叉树即是真二叉树，又是满二叉树

完全二叉树

所有的叶子节点都在最后两层，并且叶子节点都靠左对齐。（如下：「附图A」）

附图A

tree_four.jpg

二叉树的特点

每个节点的度只有三中情况：0、1、2
每个节点的度最大为2（即最多有2颗子树）
每个节点的左子树和右子树是有顺序的
即使某一个节点只有一棵树，也要区分左子树和右子树的
二叉树是有序树
同样高度的二叉树中满二叉树的总节点数量是最多的，叶子节点数量是最多的
满二叉树一定是真二叉树，真二叉树不一定是满二叉树
完全二叉树从根节点到倒数第二层是一颗满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

附图2

tree_two.jpg

非空二叉树的第`n`层(`n ≥ 1`)，最多有 $\color{red}{2^n}\color{red}{^-}\color{red}{^1}$ 个节点

以 「附图2」 中右侧的满二叉树为例, 推导非空二叉树的第n层最多有多少个节点：
规律为：
第一层（ n = 1 ）： $\color{red}{2^1}\color{red}{^-}\color{red}{^1}$ = 1 个节点；
第二层（ n = 2 ）： $\color{red}{2^2}\color{red}{^-}\color{red}{^1}$ = 2 个节点；
第三层（ n = 3 ）： $\color{red}{2^3}\color{red}{^-}\color{red}{^1}$ = 4 个节点；
第四层（ n = 4 ）： $\color{red}{2^4}\color{red}{^-}\color{red}{^1}$ = 8 个节点；
…………

高度为`h`的非空二叉树，最多有 $\color{red}{2^h}\color{red}{-}\color{red}{1}$ 个节点(`h ≥ 1`)

推导：当 h= 4, 即非空二叉树有4层，这时的二叉树就是 「附图2」 中右侧的满二叉树；
这时二叉树的总节点数为：
第一层1个 + 第二层2个 + 第三层4个 + 第四层8个 = 15个；
即：1+ 2 + 4 + 8 = $\color{red}{2^0}$ + $\color{red}{2^1}$ + $\color{red}{2^2}$ + $\color{red}{2^3}$ = $\color{red}{2^4}\color{red}{-}\color{red}{1}$ = 15

附图3

tree_three.jpg

对于任何一个非空二叉树，如果叶子节点数量为 $\color{red}{N_0}$ , 度为 2 的节点数量为 $\color{red}{N_2}$ ，则有： $\color{red}{N_0}$ = $\color{red}{N_2}$ + $\color{red}{1}$

假设度为1 的节点数量为 $\color{red}{N_1}$ ，二叉树的节点总数为： $\color{red}{N}$ = $\color{red}{N_0}$ + $\color{red}{N_1}$ + $\color{red}{N_2}$

二叉树的边数 T = （度为1 的节点数量 $\color{red}{N_1}$ + 度为 2 的节点数量 $\color{red}{N_2}$ 的 2 倍） = （二叉树的节点总数 $\color{red}{N}$ - 1） = （叶子节点数量 $\color{red}{N_0}$ + 度为1 的节点数量 $\color{red}{N_1}$ +度为2的节点数量 $\color{red}{N_2}$ ）即：T = （ $\color{red}{N_1}$ + $\color{red}{N_2}$ * 2 ） = （ $\color{red}{N}$ - 1） = （ $\color{red}{N_0}$ + $\color{red}{N_1}$ + $\color{red}{N_2}$ ）

以「附图3」 中的二叉树为例推导：
A二叉树：度为1的节点数量 $\color{red}{N_1}$ = 0，度为2的节点数量 $\color{red}{N_2}$ = 0，叶子节点数量 $\color{red}{N_0}$ = 1 = 0 + 1 ；二叉树的节点总数为 1 = 1 + 0 + 0
B二叉树：度为1的节点数量 $\color{red}{N_1}$ = 0，度为2的节点数量 $\color{red}{N_2}$ = 1，叶子节点数量 $\color{red}{N_0}$ = 2 = 1 + 1 ；二叉树的节点总数为 3 = 2 + 0 + 1
C二叉树：度为1的节点数量 $\color{red}{N_1}$ = 0，度为2的节点数量 $\color{red}{N_2}$ = 3 ，叶子节点数量 $\color{red}{N_0}$ = 4 = 3 + 1 ；二叉树的节点总数为 7 = 4 + 0 + 3
D二叉树：度为1的节点数量 $\color{red}{N_1}$ = 2，度为2的节点数量 $\color{red}{N_2}$ = 5 ，叶子节点数量 $\color{red}{N_0}$ = 6 = 7 + 1；二叉树的节点总数为 13 = 6 + 2 + 5
E二叉树：度为1的节点数量 $\color{red}{N_1}$ = 0，度为2的节点数量 $\color{red}{N_2}$ = 7 ，叶子节点数量 $\color{red}{N_0}$ = 8 = 7 + 1 ；二叉树的节点总数为 15 = 8 + 0 + 7
……

假设一个满二叉树的高度为`h (h ≥1 )` , 那么第n层的节点数量为 $\color{red}{2^n}\color{red}{^-}\color{red}{^1}$ ；叶子节点数量为 $\color{red}{2^h}\color{red}{^-}\color{red}{^1}$ ；总节点数量为 n = $\color{red}{2^h}\color{red}{-}\color{red}{1}$ = $\color{red}{2^0}$ + $\color{red}{2^1}$ + $\color{red}{2^2}$ + ..... + $\color{red}{2^h}\color{red}{^-}\color{red}{^1}$ ;高度 h = $\color{red}\log_\color{red}{2}\color{red}{(n+1)}$

最后编辑于：2022.01.04 11:35:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335

二叉树（Binary Tree）类型特点

二叉树的类型

附图1

真二叉树

满二叉树

完全二叉树

附图A

二叉树的特点

附图2

非空二叉树的第n层(n ≥ 1)，最多有 个节点

高度为h的非空二叉树，最多有 个节点(h ≥ 1)

附图3

对于任何一个非空二叉树，如果叶子节点数量为 , 度为 2 的节点数量为 ，则有： = +

假设度为1 的节点数量为 ，二叉树的节点总数为： = + +

二叉树的边数 T = （度为1 的节点数量 + 度为 2 的节点数量的 2 倍） = （二叉树的节点总数 - 1） = （叶子节点数量 + 度为1 的节点数量 +度为2的节点数量 ）即：T = （ + * 2 ） = （ - 1） = （ + + ）

假设一个满二叉树的高度为h (h ≥1 ) , 那么第n层的节点数量为 ； 叶子节点数量为 ；总节点数量为 n = = + + + ..... + ;高度 h =

推荐阅读更多精彩内容

非空二叉树的第`n`层(`n ≥ 1`)，最多有 $\color{red}{2^n}\color{red}{^-}\color{red}{^1}$ 个节点

高度为`h`的非空二叉树，最多有 $\color{red}{2^h}\color{red}{-}\color{red}{1}$ 个节点(`h ≥ 1`)

对于任何一个非空二叉树，如果叶子节点数量为 $\color{red}{N_0}$ , 度为 2 的节点数量为 $\color{red}{N_2}$ ，则有： $\color{red}{N_0}$ = $\color{red}{N_2}$ + $\color{red}{1}$

假设度为1 的节点数量为 $\color{red}{N_1}$ ，二叉树的节点总数为： $\color{red}{N}$ = $\color{red}{N_0}$ + $\color{red}{N_1}$ + $\color{red}{N_2}$