chapter_tree/binary_tree/

[giscus[bot]]

chapter_tree/binary_tree/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_tree/binary_tree/

[ZZhenF]

/* 插入与删除结点 */
TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入结点 P
n1.left = P;
P.left = n2;
// 删除结点 P
n1.left = n2;
插入P这里，先令n1的左值针指向p结点，会将n2以后的结点丢失吧，虽然这里创建二叉树的时候就已经将每个结点的地址都保存下来了，但是先令p的左指针先指向n2，在让n1的左值针指向p会不会更严谨一点

[krahets]

应该都行哈，已经暂存在 n2 了，顺序不太重要，感觉这里不用太纠结～
如果想要避免暂存，尽量缩短代码，可以这样写

P.left = n1.left
n1.left = P

[wbzyo]

确实会丢失，这里能直接用n2，是因为上文初始化的时候已经定义了n2，先令p的左指针先指向n2（P.left=n1.left),再让n1的左值针指向p会更严谨一点(n1.left=P)

[r-shine]

”二叉树中的插入与删除一般都是由一套操作配合完成的“，这里的”一套操作“指什么呢？可以理解为资源的子节点的资源释放吗？

[krahets]

哈喽，这里的“一套操作”指的是多个步骤的操作，并且一种操作可能分为多种情况来处理。比如在「二叉搜索树」中，删除结点操作要分为三种情况处理，每种情况需要不同的多个步骤的操作。看完二叉搜索树你应该就理解了～

[xillianpeng]

我对高度的定义有点疑问，如果高度的定义是走过边的数量，那么只有根节点的二叉树，高度是否就是0，完美二叉树总结点数量=2^0-1=0

[xillianpeng]

不好意思，忽略吧，公式看错了，总结点数量应该是2^(0+1) - 1 = 1

[Swordknife]

那么有一个结点的二叉树，高度和深度都是0，对吗

[krahets]

是的，树的高度为 0 ，该结点的高度、深度都为 0

[xusujun33]

7.1.3 tips：
在中文社区中，完美二叉树常被称为「满二叉树」，请注意与完满二叉树区分。这里最后一句话是不是写错了，是否是请注意与完全二叉树区分。

[xusujun33]

是我看错了，冒失了冒失了。一个是完美，一个是完满。。我的天呐，太容易看错了。

[tianjx98]

请问一下画图是用的什么工具啊, 很好看!

[gvenusleo]

应该是 Keynote 🤔

[mhkz]

类比楼的高度，和水的深度，从下往上看和从上往下看

[krahets]

确实，从根节点到看叶节点（从顶看底）是深度，从叶节点看根节点（从底看顶）是高度

[youngledo]

感觉二叉树的内容有点少，案例缺失，能补充点实际场景吗？

[krahets]

本书主要介绍数据结构的概念与用法，看完建议可以开始去刷二叉树的题啦

[Jaynxe]

在完美二叉树的定义中，这里写的是(除了最底层外，其余所有层的节点都被完全填满)
最底层的节点数应该也是满的吧

[krahets]

emmm 这里的表述确实有歧义，本来想表达的是子节点被填满，即除了最底层外，其余层的所有节点的度都为 2 。我优化一下表述

[Sail38]

删除节点通常意味着删除该节点及其所有子树 这句话看不懂， 以图7-3第一幅图（原图， 在插入P node之前）为例，如果 Node 2 含有左（和/或）右子树，那么整个子树在Node2删除操作中都没了吗？ 请帮忙解答， 谢谢。

[krahets]

Hi ，如果我们仅删除 node2 （断开它和父节点之间的连接），那么 node2 及其以下形成的子树就都被删除了。我们无法再从树的根节点访问到这个子树上的任意一个节点。

[ChinaYong]

完美二叉树中，说了“若树高度为h，则节点总数为2^(h+1)”，这里不应该用“高度”，而应该用“深度”吧？包括后面的陈述都是用的“高度”这个词。

[krahets]

我们通常习惯说“二叉树的高度”。我感觉这是因为自然界中的树是从地面往天上长的，所以人类对于“树”的描述都是“好高啊”。

[ChinaYong]

就是说上面用的并非定义，而是一种常见的表述方式是吧？

[zoujia]

作者你好，根据文章里“7.1.1二叉树常见术语”中的定义，以及使用“边”来衡量“高度”与“深度”，有一个疑惑：叶子节点的“高度”是 0 吗？类似的，只有一个根节点的二叉树，该树的“高度”是 0 吗？

我问的这个问题，直接关系到我对于“图7-7平衡二叉树”里的“变量 d ”的计算的理解，因为这个地方我没看懂，我自己根据上文的定义来计算每个节点的 d 的值，发现跟文中对不上~~

[krahets]

你说的没错。这个在本章小结里也有讲。

[lavaicer]

节点的「高度 height」：从最远叶节点到该节点所经过的边的数量。

[lavaicer]

您好，这里6的高度从8算还是从12算。一个普通节点的高度应该是从该节点的最远叶子节点算起还是从整个树最远的叶子节点算起。谢谢

[krahets]

Hi，节点高度的准确定义是：从距离该节点最远的叶节点到该节点所经过的边的数量。

[EririIcytail]

我大学教材和百度的大部分答案说， 树的高度是从根节点到最远节点的节点个数而不是边的个数，因此树的高度 = 树的深度 = 树中节点的最大高度 + 1 ，！= 节点的最大高度。本文定义是否有误？最后的表格中，是否“高度为 h 的树的节点总数”应为“ 2 ^ h - 1” ? 不知道是不是有多种定义， 供作者参考喵

[krahets]

Hi，我们以 Wiki 为准：“树的高度是从根节点到最远节点的边的个数” ，请参考
Tree (data structure)

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). Thus the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

这个概念的不一致性主要是由于对”path“这个概念定义不同导致的，细节请参考这里

[3238068224]

6，我是说怎么按照大神写的去做学校的题，完全不对。

[3238068224]

我还到处搜，晕了。大神可以特别标注一下这个地方。大学的教材好像默认二叉树根节点的高度和深度都是1.至少我现在学的教材就是这样说的，这还是学校专门选的考研数据结构。服了

[krahets]

@3238068224 看来这不一致还挺广泛的……考试的话还是以课本为准～

[tanhaow]

才知道原来汉语里面parent node是父节点...😅

[jcluo1994]

self.left: TreeNode | None = None # 左子节点引用
这个不应该是self.left=None吗？还是说规范就是这样？

[krahets]

冒号后面的部分是 Python 的类型注解（type hints），详情请见 typing — Support for type hints 。
为了提升规范性和可读性，这本书的 Python 代码全部添加了 type hints 。

[chenghui-ch]

图7-5 完全二叉树 第三层 第三个节点是最底层节点吗？为啥没被填满

[krahets]

Hi～在最底层，填满需要 8 个节点，图中只有 5 个节点；右边还有三个位置没有填满。

第三层已经被填满了，第三层的第三个节点的“子节点”没有被填满，请注意区分～

[weidongweidong]

最底层不是第四层么？

[luoflyxidian]

想请问下，如果在嵌入式系统中使用高度为20的满二叉树，由于内存有限，无法存储所有节点，该如何操作和遍历这样规模的二叉树，采用什么方法可以减少内存的占用

[krahets]

满二叉树可以用数组存储，相比链表更加节省空间。可以看下后面的“二叉树的数组表示”

[ganxingrui]

前提是内存有限，就得考虑懒加载；例如先加载左子树，砍掉右子树，直接节省一半内存；然后左子树，还是用同样的方法处理；左子树处理完，移除内存，再去加载又子树；思想就是懒加载；局限性就是空间节省了，相对而言浪费时间；此时就需要考虑二者直接寻找一个平衡。

[xiewanqin]

你好，想问下子树的高度该怎么定义呢，这里有点迷惑，子树是根节点的左（右）节点及其以下节点形成的树的话，那高度是不是应该是左（右）节点到最远叶节点所经过的边的数量。但是以平衡二叉树的定义来看好像不是这样

[krahets]

树的高度是“它的根节点”到最远叶节点所经过边的数量。子树也有自己的根节点

[ganxingrui]

大神，二叉树插入代码，这样写更好点吧
// 1.先让P n1同时指向n2,防止n2丢失
P.left = n1.left
// 2.让n1指向P
n1.left = P

[CodeGeis]

你将评论时间顺序显示,最早一条评论就是你这个问题

[qw124341789]

你好，作者，如果能把每章评论里的问题集做到每章的结尾，这样Hello算法就更完善了。

[krahets]

Hi，谢谢建议！现在每章的小结里已经有精选的 Q&A 了哈，我们会定期更新

[ggplz]

貌似 除了根节点的其他节点都叫叶节点，而度为 0 的节点应该叫叶子节点？

[krahets]

Hi，在本书中，叶节点和叶子节点等价（是同一个名词）

[bearoops]

二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。
错误修正：“根节点”改成“该节点”。

[bearoops]

可以删除评论不？

[ferryboy001]

很高兴可以发现这个宝藏网站。
我看不见，只能借助屏幕阅读器，以及键盘来浏览网站。
网站使用的公式渲染方式非常无障碍，是我在其他 PDF、epub 或者纯文本上极少见到的。
这里因为无法看到图，所以有一些对于二叉树概念上的疑问想请各位大佬解惑：

1. 完美二叉树和完满二叉树具体的区别是什么？或者说，他们之间的包含关系是什么？是什么样的条件让某个树成为完满二叉树而不是完美二叉树（反之亦然）？

2. 完全二叉树中，

只有最底层的节点未被填满，且最底层节点尽量靠左填充

具体是什么样的结构？尽量靠左填充是如何操作的？怎样才算不尽量？如何的不尽量靠左填充会让这个结构不是一个完全二叉树？

最后，很高兴可以有这样一个评论区，可以在啃书的时候提出疑问。
谢谢！

[ferryboy001]

谢谢，我好像理解了。
如果给定一个三层的完美二叉树，每层节点用 a、b、c 表示：

1. 如果移除 b 右的子节点，这个结构就是完满二叉树，也是完全二叉树；

2. 在此基础上，移除 b 左的右子节点，这个结构依然是完全二叉树，但不是完满二叉树；

3. 还是在第一步的基础上，如果移除的是 b 左的左子节点，这个结构既不是完全二叉树，也不是完满二叉树；

特殊的，一个链表应该也是一个完全二叉树吧~。

[suzumiy]

是的,您的描述很有条理比我的要清晰,以我的拙见您的描述是对的,但是一个链表可能不是完全二叉树,完全二叉树的定义为「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。所以如果这个链表只有2个元素的话是完全二叉树,如果大于两个元素会出现非底层节点未被填满的情况。

[ferryboy001]

好的，忘了有这个条件了……

[krahets]

谢谢鼓励！@suzumiy 的回答很详细了，我再简短回答一下：

1. 在完美二叉树中，只有最底层的节点的度为 0 ，或者说完美二叉树每一层的节点都是被填满的。相对地，完满二叉树只要求节点的度为 0 或 2 ，因此每一层的节点都可能存在度为 0 的情况。
2. 我用一个例子来描述完全二叉树“底层节点尽量靠左”的情况：给定一个共 3 层节点的二叉树，那么最底层最多可以容纳 4 个节点，将它们从左到右编号为 0, 1, 2, 3 。此时假设最底层有 2 个节点，那么这两个节点必须在 0, 1 位置时才是完全二叉树；其他所有的位置组合都不满足“尽量靠左”。尽量靠左就是从左到右无空位的填满。

新年快乐！给你点赞！我在设计内容的呈现时，可能考虑的并不周到，欢迎随时提建议意见

[ferryboy001]

谢谢回复！
因为这是一本开源的书，是随时可以修改的，很多在其他书本里对于像我这样的读者形成阅读障碍的部分，也许我们一直没办法搞懂，就很遗憾。
虽然一图胜千言，但这千言对于我们来说非常重要，当然，也可以不用千言那么多，只要能把图片中的信息完整的用文字传达出来，就足够了。
希望这本书能越来越好！

[deusyu]

k神这个可以添加导出为PDF的功能吗，我想把某个章节喂到ChatGPT进行对话式学习。

[krahets]

Hi，浏览器打印页面（Ctrl + P）应该可以导出 PDF ，或者可以直接下载 PDF 版 https://github.com/krahets/hello-algo/releases

[deusyu]

打印页面，包含了评论。
刚刚忘记补充了，导出为不带评论的页面。
我的想法是学一节自己对话式学习，并且让ChatGPT 出题巩固一节。
从下载的PDF版喂给他链路可能过长也可能上下文过多。
以上仅仅是自己的需求和建议😇

[krahets]

好的～在 Chrome 浏览器中，可以选中正文，鼠标右键 + 打印，这样就不会有评论的页面了。或者在打印时，仅打印前几页

[wxamlzm]

我把二叉树当成倒着的树来看是不是就可以了TAT

[krahets]

没问题哈哈：

• 二叉树最顶部的节点被称为“根节点”，对应的就是现实中的“树根” ；
• 二叉树最底部的节点被称为“叶节点”，对应现实树上的“叶子”；

[WalkerInAI]

是的，对着图看概念的时候，发现很奇怪。在这里把图片里的树反着画，效果应该会更好的。（个人理解）

[krahets]

@WalkerInAI 在计算机学科中，树通常就是文中这样画的，需要习惯它

[YMMdrq]

是倒过来的树，因为根最高的。

[mrCR100]

请问在二叉树常用术语中最远叶节点是指什么含义呢？有严格的定义吗？

[krahets]

在二叉树中，根节点到叶节点之间的边的数量可以看作是根节点到叶节点的“距离”。每个叶节点到根节点之间的边的数量可能不同，而边数量最多的叶节点，就是“最远叶节点”。

[mrCR100]

理解了。

[l1n9d]

请问插入一个节点的时候，不用比较相邻节点的大小吗？

[Autumn00air]

看树的要求，比如二叉搜索树，就需要比左子树大，比右子树小，所以插入的时候需要进行下沉算法。当然，树本身就是宏观的，所以在没有要求之前，你想怎么操作都可以（个人理解，欢迎指正~）

[shaoxinH]

主要根据需求设计呀，不同的二叉树插入顺序适合不同的需求

[redandblueqwer]

K神，判断节点高度中，"从距离该节点最远的叶节点到该节点所经过的边的数量"，其中的叶节点是默认对应子树下的情况吗？

[beidimanman]

谢谢，您的邮件我已收到。