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]

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

[wyang0824]

我是这么理解的：计算总节点个数，用树高度来描述更合理。深度说的是某个节点在整个树中所属的位置

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

[wyang0824]

能否将 树的高度 定义放到 7.1.1节 常见术语里？我看后面用到了这个定义，但是常见术语中 没找到

[tanhaow]

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

[sqhsysu17]

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

[LittleCabbage-liu]

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

[jiuerya7]

原来如此👍

[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数

[dibe1202]

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

[qwerty123-debug]

@DaHuaJia @HarrryHe 平衡二叉树的定义是任意节点的左子树与右子树的高度差的绝对值不超过1，一个二叉树的高度的定义是从根节点到最远叶节点所经过的边的数量。根据这两个定义，d1的左子树的根节点和最远叶节点是同一个，所以从根节点到最远叶节点没有经过任何边，那么高度就是0，也就是d1的左子树高度为0。而之所以你们算成了1，是因为你们弄错了定义，这个左子结点高度确实为1，但它的左子树高度为0，要区分树的高度和节点的高度的定义是不同的。你们这样做是相当于把d1的左子树的高度当作了d1的左子结点在起初那个大二叉树中的高度。
然后继续说d1的右子树，右子树没有根节点和最远叶节点，如果依然按照定义的话，那么经过的边数仍为0，那么d1的右子树的高度也为0。原来那位@dibe1202说的是对的。
但是后来我注意到了这样一句话（在图7-2下面那条Tip里）：请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下，高度和深度都需要加 1 。
用教材里的定义可以解决这个问题。根据教材里的定义，d1的左子树从根节点到最远叶结点经过了一个节点，也就是根节点，所以高度是1，而右子树因为没有节点，所以没有经过节点，那么高度就是0，这样的话就既满足了定义，也解释了为什么d1的左子树与右子树的高度差为1。

[Mike-7777777]

@qwerty123-debug 在这个情况下，空树的高度应该定义为-1，而不是0。见 链接。这个问题在stackflow上被讨论过，一部分教材将空树的高度定义为undefined，见链接，但我认为应该定义为-1。

[HarrryHe]

今天复习 回来看了看，感觉当时还是看的太快了 （哭 确实是搞错了 当时理所当然就说出他本身的高度了

[HarrryHe]

在7.5中有提到叶节点高度为0，空节点高度为-1，适用于这里平衡二叉树的情况

[xiaoyaozizaiwoweidu]

让我先回顾一下什么是高度。树的高度是指从根节点到最远叶子节点的最长路径上的边数。因此，一个节点的高度就是从该节点到其最远叶子节点的最长路径上的边数。
在图中，每个节点都有一个 d 值，表示其左子树高度减去右子树高度。例如，根节点的 d=−1，这意味着它的右子树比左子树高1。根节点的左子树高度2，右子树高度3，所以2-3=-1，这符合平衡条件，因为 ∣−1∣=1。

[swcjmy666]

打开

[superZchen0701]

'''完全二叉树（complete binary tree）只有最底层的节点未被填满，且最底层节点尽量靠左填充。'''
如果按照上面的说法，完美二叉树并不是一棵完全二叉树。因为完美二叉树的叶子节点也是填满的。
但是如果按照'''最底层节点靠左填充，其他层节点全被填满'''说法来，完美二叉树就是一棵完全二叉树。

[laohugit]

完全二叉树"仅允许"最底层的节点不完全填满，"仅允许"不是你说的"只有"哦。显然完美二叉树及是完全二叉树也是完满二叉树更是平衡二叉树哦，要不说是完美呢。

[xiaozhuge123]

day06

[WangYun0918]

请问：是否节点所在的层（level） = 节点的深度（depth）+ 1，该公式是否成立？

[WangYun0918]

请问“在完美二叉树中，叶节点的度为 0，其余所有节点的度都为 2；” 不是所有的二叉树的叶节点的度都为0吗，如果节点的度不为0，肯定不是二叉树啊

[laohugit]

节点的度表示子节点的个数，取值0，1，2。

[WangYun0918]

谢谢回复。但我的意思是叶节点，如果度不是0，那就不是叶节点了，所以叶节点的度为0感觉是一句“废话”

[WangYun0918]

最后一个表格“ 二叉树的最佳结构与最差结构”，第二行“高度为 h 的树的叶节点数量”，链表为何是 1 ，不应该是 h 吗？

[WangYun0918]

而且完美二叉树也不应该是 2h 应该是 2h - 1 才对吧

[WangYun0918]

抱歉 我理解错了，懂了

[LukeLuke-Y]

二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
这里是不是写成：从最远叶节点到根结点所经过的边的数量。会好一点，本质上数量一样，但是这样更能统一计算方向，高度是从叶节点向目标节点算，深度是从根结点向目标节点算。

[fug-0117]

是的 深度从上往下 高度从下往上 这样好记忆

[beidimanman]

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

[nanmingjushi]

删除节点时，应彻底断开被删除节点与前后节点的所有关联，避免残留引用。

// 删除节点 P
n1.left = n2;
P.left = null;

[beidimanman]

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