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)

[ruqingxu001]

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

[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 看来这不一致还挺广泛的……考试的话还是以课本为准～

[rachel-tanhao]

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

[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神，判断节点高度中，"从距离该节点最远的叶节点到该节点所经过的边的数量"，其中的叶节点是默认对应子树下的情况吗？

[DBook111]

我认为不是子树中最远的叶节点，而是所有叶节点中距离最远的

[whereishero]

叶节点就是默认对应子树下的，因为树结构是单向的，只能从一个结点到它的子节点

[genskyff]

把节点度数改成出度和入度比较好，出度和入度之和为该节点的度数，二叉树就是一个根节点入度为0，叶节点出度为0的无回路连通图。这样还可以利用握手定理，进一步推出二叉树的边数=节点数-1

[jack1415926]

你好，我想问一下在二叉树节点结构体中，本页展示的代码只有left和right两个节点但在文件中那个的代码却有parent共3个节点，有和书中一样的示例代码吗

[sqhsysu17]

大佬您好！初学算法，有个疑问。图7-3中，插入树节点时，代码顺序是n1.left = p 然后p.left = n2，可是这样不会导致n2找不到吗？就和链表的插入操作一样，不应该先让p.next连接上n2，再让n1.next链接p吗？不知道我的理解是否有误

[LittleCabbage-liu]

这是因为他这段代码里面每个节点都是单独定义出来了的，而不是只提供了一个根节点

[OrangeAlien]

我不明白，C的代码里面有节点高度height这一成员，后面插入和删除节点时，为什么不对它进行赋值

[Mike-7777777]

新增内容:

节点所在的层（level）：从顶至底递增，根节点所在层为 1 。

此处的1应注明该定义不统一, 一说为0.

https://stackoverflow.com/questions/59151282/what-is-level-of-root-node-in-a-tree

[xuaidongx]

h树高的perfect binary tree的节点计算是等比公式求和{1,2,4,8...}
2ⁿ+1 = 2^h+1+1
n:项数 h:根节点到叶子结点的edge数

[ruqingxu001]

你的邮件我已经收到！

[dibe1202]

有人能帮忙解释一下，图 7-7平衡二叉树，第二层左边的节点的d=1是怎么算的， 它只有一个左子节点，没有右子节点。 那它的左子树高度为0？ 没有右子树？

[DaHuaJia]

？你看错了吧，很好理解啊，它有一个左叶子节点，高度是1，没有右节点。d=1-0=1

[dibe1202]

不对啊，按上面的定义，从距离该节点最远的叶节点到该节点所经过的边的数量。 左子树只有一个节点，它没有边，它的高度就是0，然后没有右子树。 这是我的点。