chapter_tree/array_representation_of_tree/

[giscus[bot]]

chapter_tree/array_representation_of_tree/

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

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

[fallenleavesguy]

讲得这么好为什么没有评论

[krahets]

哈哈，可能是因为这一节是最近单独分出来的

[Focu230104]

"完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，(\text{None}) 只出现在最底层且靠右的位置"，是靠左吧，大佬是不是误笔了

[krahets]

原文没问题，在完全二叉树的最底层中，节点靠左、None 靠右

[Focu230104]

不好意思，看错了，以为是节点，谢谢大佬

[xiaoyeaichif]

不仅图画的好，讲的也很好。作为回顾和复习真的太棒啦！如果能附上代码就更美了！！！

[krahets]

感谢建议，这一节的代码稍后加上～

[xiaoyeaichif]

感谢回复，希望越做越好！对于新手太友好了这网站！

[LongLiveY96]

if (order == "pre")
    res.add(val(i));
dfs(left(i), order, res);
// 中序遍历
if (order == "in")
    res.add(val(i));
dfs(right(i), order, res);
// 后序遍历
if (order == "post")

这里的字符串对比是不是有问题啊，不应该用"xxx".equals(order)吗

[krahets]

在 Java 中，对于基本数据类型，== 用于对比两个变量的值是否相等。

对于引用类型，两种符号的工作原理不同：

• == ：用来比较两个变量是否指向同一个对象，即它们在内存中的位置是否相同。
• equals()：用来对比两个对象的值是否相等。

因此如果要对比值，我们一般会用 equals() 。然而这里的 "pre" , "in" , "post" 都存储在字符串常量池中，等式左右两个 "pre" 指向同一个对象，因此可以用 == 来比较。

[zhuasdfg]

妙！妙不可言！前中后序遍历实现只是res.add()位置不同，递归实在是太牛了。

[hazukieq]

7.3.2 小节中 C语言实现的代码有点奇怪，请问 C语言中有 vector 向量这个关键字吗？我仔细瞧了瞧，代码中也没有用宏定义 vector。我在 cppreference 网站中的 C keywords 中也没有找到 vector。

[ahnovice]

我也没看懂😭

[AY-Front]

大佬，有个小小的建议，要是代码里附上一些测试例子对小白就更友好了

[krahets]

源码里都有测试样例呀，例如 Python 代码 。

[topul]

这一节太有用了，之前刷leetcode，看到二叉树的数组表示就感觉有点懵，看完讲解感觉舒服多了

[i-Remus]

class ArrayBinaryTree 的 __dfs方法写的太美味了！！

[wpf19950321]

但是迷惑性很强哈哈

[carrot-butcher]

作者你好，关于 __dfs 这段代码我有点没看懂。

def __dfs(self, i: int, order: str):
        """深度优先遍历"""
        if self.val(i) is None:
            return
        # 前序遍历
        if order == "pre":
            self.res.append(self.val(i))
        self.__dfs(self.left(i), order)
        # 中序遍历
        if order == "in":
            self.res.append(self.val(i))
        self.__dfs(self.right(i), order)
        # 后序遍历
        if order == "post":
            self.res.append(self.val(i))

就比如说：如果是前序遍历，那self.__dfs(self.left(i), order)往二叉树最深处递完后，就只是遍历了二叉树最左侧的一支，那相应的这一分支的右节点和根节点怎么遍历的呢？好像这个函数里面也没有关于parent函数的应用。
链表前序遍历二叉树，我记得是“根->左->右”，就是如下（上节内容）：

def pre_order(root: TreeNode | None):
""" 前序遍历"""
    if root is None:
       return
    res.append(root.val)
    pre_order(root=root.left)
    pre_order(root=root.right)

为什么数组的二叉树遍历里有部分代码不用写呢？希望作者能帮我解答这个问题。

[krahets]

Hi ，如果我们只看前序遍历，就可以将中序、后序遍历代码删除掉，函数变为：

def __dfs(self, i: int, order: str):
        """深度优先遍历"""
        if self.val(i) is None:
            return
        self.res.append(self.val(i))
        self.__dfs(self.left(i), order)
        self.__dfs(self.right(i), order)

这样看是否就和上节的前序遍历代码一致了？不同点仅在于获取值、左子节点、右子节点的方式不同。

[lihuxiao1]

是我没看明白嘛，我看那个代码里的pre 部分，只有self.__dfs(self.left(i), order)，而作者你回答的是有两行self.__dfs(self.left(i), order)
self.__dfs(self.right(i), order)

[Hadias94]

看了半天看出来的，那个递归的动作不在if语句中

[krahets]

展开这样看，更清楚一些：

def __dfs(self, i: int, order: str):
    """深度优先遍历"""
    if self.val(i) is None:
        return
    if order == "pre": self.res.append(self.val(i)) # 前序遍历
    self.__dfs(self.left(i), order) # 递归左子树
    if order == "in": self.res.append(self.val(i)) # 中序遍历
    self.__dfs(self.right(i), order) # 递归右子树
    if order == "post": self.res.append(self.val(i)) # 后序遍历

[Verlog123]

注意看缩进，眼睛都给我看花了，原来是缩进没注意看，self.dfs(self.left(i), order)和self.dfs(self.right(i), order)这2行代码并不在if循环语句里面，而是在外面

[Leezgion]

请问上例JS代码中

  /* 获取索引为 i 节点的父节点的索引 */
    parent(i) {
        return (i - 1) / 2;
    }

问题描述 举例
let tree = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];
parant(3) //------>return 1
parant(4) //------>return 1.5

请问数组的索引值不应该为整数吗，如果为整数那么上述parent()中 return 返回的值不应该进行向下取整吗？

[github15238484509]

我想明白了，

1. 一个节点分为两个孩子，比如 节点为1 的时候，左孩子：1 * 2 +1 =3；右孩子 1 * 2 + 2 = 4
2. 用左推父的时候需要 -1 ； 右推父的时候 -2 ，但是作者只用了 左推父，没有想到 右推父的情况；向下取整就好了

[kaka59]

我也有同样的疑问，个人认为应该为
return Math.floor( (i - 1) / 2 );

[superFlyMoose]

右推父也成立，因为这是整数除以整数，本就可以向下取整

[showlibia]

DAY6

[blxzer77]

/* 深度优先遍历 */
void dfs(int i, string order, vector<int> &res) {
    // 若为空位，则返回
    if (val(i) == INT_MAX)
        return;
    // 前序遍历
    if (order == "pre")
        res.push_back(val(i));
    dfs(left(i), order, res);
    // 中序遍历
    if (order == "in")
        res.push_back(val(i));
    dfs(right(i), order, res);
    // 后序遍历
    if (order == "post")
        res.push_back(val(i));
}

研究了好久才发现递归不在if语句内 笨死自己

[amoyonglee]

谢谢你的留言! 我一直没有看明白这段代码, 经过你的提醒, 我终于明白啦!

[Lyrilon]

我也和你犯了一样的错误www，感谢你的指出。

[dongpingwang]

尼玛，这代码太不规范了

[1037861070]

因为if方法体只有一行是不用中括号的，省略了{}，但是编码规范是只要出现if的地方，方法体最好都加上{}，这里又是三种遍历都复用了部分代码，所以有些难理解

[zoujia]

作者你好，获取 左/右 子节点索引的方法，获取到的索引可能是超出范围的，比如索引 8 ，左、右子节点索引分别为 17、18，已超出最大 14 了~
能不能这么理解：实际应用中，单纯获取索引没有太大意义，必须配合 val(i) 来获取相应位置的数据，因为 val(i) 已经校验索引边界了~

[krahets]

Hi，是的～当然也可以在获取子节点索引的方法中加上校验，具体看实际需求

[1515292252]

动态图在哪里 只有像PPT一样的静态图？

[krahets]

是的～

[selear]

 /* 深度优先遍历 */
private void dfs(Integer i, String order, List<Integer> res) {
    // 若为空位，则返回
    if (val(i) == null)
        return;
    // 前序遍历
    if (order == "pre")
        res.add(val(i));
    dfs(left(i), order, res);
    // 中序遍历
    if (order == "in")
        res.add(val(i));
    dfs(right(i), order, res);
    // 后序遍历
    if (order == "post")
        res.add(val(i));
    }

以上截取自array_binary_tree.java，Java代码两个字符串内容的比较应当使用equals而非==，==比较的是两个对象所指向的地址是否相同的。

换句话说，这里的代码应当为：

 /* 深度优先遍历 */
private void dfs(Integer i, String order, List<Integer> res) {
    // 若为空位，则返回
    if (val(i) == null)
        return;
    // 前序遍历
    if ("pre".equals(order))
        res.add(val(i));
    dfs(left(i), order, res);
    // 中序遍历
    if ("in".equals(order))
        res.add(val(i));
    dfs(right(i), order, res);
    // 后序遍历
    if ("post".equals(order))
        res.add(val(i));
    }

[krahets]

谢谢指正！这里虽然不影响结果的正确性（由于字符串常量池机制，它们的地址也是相通的），但用 equals 更加规范

[unicorn-option]

数组表示的Swift代码里面获取左右子节点索引是不是没有return

[nuomi1]

单行表达式可以省略 return。

[Derry-celly]

作者你好，关于这段代码，我有点没看懂。

def __dfs(self, i: int, order: str):
        """深度优先遍历"""
        if self.val(i) is None:
            return
        # 前序遍历
        if order == "pre":
            self.res.append(self.val(i))
        self.__dfs(self.left(i), order)
        # 中序遍历
        if order == "in":
            self.res.append(self.val(i))
        self.__dfs(self.right(i), order)
        # 后序遍历
        if order == "post":
            self.res.append(self.val(i))

为什么中序遍历是self.__dfs(self.right(i), order)呢？为什么是右？

[hpstory]

Hi @Derry-celly ，因为中序遍历的顺序是左中右，dfs函数可执行的部分变成

def dfs(self, i: int, order: str):
    """深度优先遍历"""
    if self.val(i) is None:
        return
    self.dfs(self.left(i), order)
    self.res.append(self.val(i))
    self.dfs(self.right(i), order)

所以当前节点访问后应该访问右子节点

[Derry-celly]

理解了！感谢你的及时回复！

[HangSeven]

/* 获取索引为 i 节点的父节点的索引 */
public Integer parent(int i) {
return (i - 1) / 2;
}怎么确定这个节点不是右子节点，不是（i - 2）/ 2

[HangSeven]

明白了，整数除以整数还是整数刚好包括了，－永远是对的

[bnufw]

def dfs(self, i: int, order: str)
这个方法是不是不能直接调用啊，因为self.res在这个方法里没有定义？

[krahets]

Hi，我们不会直接调用它，它是前序、中序、后序遍历的工具方法

[2lin123]

你好，这段代码
/* 节点数量 */
int size() {
return tree.size();
}
不应该是返回数组的大小吗，如果有空位的话，就不应该是节点的数量吧

[krahets]

谢谢指正，这里应为“数组容量”

[llhznb]

这三种遍历，能够完全遍历吗？比如前序遍历，一直找左子树，当索引超量程后return，右边的数也遍历了吗？

[llhznb]

擦，看错了，后面递归不在if里面

[KeeVor]

哈哈哈，感谢你提醒，我本来也有这个疑问呢，回头一看确实dfs递归调用都不在if里面。

[Clarkszw]

图7-13, 树上的灰色数组索引是不是标错了?

[curly210102]

应该是故意标错的，来表达非完全二叉树中的节点索引和数组索引不对应，非完全二叉树无法用不带 None 的数组来表示

[krahets]

@curly210102 补充：该数组对应的二叉树结构不唯一

[qw124341789]

你好，作者看完这章有个问题想问一下，用以下代码进行 前，中，后序遍历，应该没有特殊情况而发生无法预料的意外吧

[qw124341789]

void pre(Titree *tree){
	if (tree == NULL){ return; }
	printf("%d", tree->data);
	pre(tree->lchild);
	pre(tree->rchild);
}//前序遍历
void mid(Titree *tree){
	if (tree == NULL){return;}
	mid(tree->lchild);
	printf("%d", tree->data);
	mid(tree->rchild);
}//中序遍历
void post(Titree *tree){
	if (tree == NULL){ return; }
	post(tree->lchild);
	post(tree->rchild);
	printf("%d", tree->data);
}//后序遍历

[qw124341789]

完全二叉树用这段代码走了一遍，可以完美实现功能。

[KITSUNE234]

作为新手，dfs函数的写法感觉真的很巧妙，复用性很高啊

[chaojiwudidashuaige492]

我觉得 “映射公式的角色相当于节点中的引用” 会更好一点

[krahets]

谢谢建议！

[Magicperformer]

作者你好~请问7.3.3的二叉树局限性中，“增删节点需要通过数组插入与删除操作实现，效率较低。”这一点我不是非常可以理解，是说时间复杂度会到达O(n)的效率低吗？

[Magicperformer]

因为如果想通过数组来唯一表达一棵二叉树，那么这棵二叉树应该是一棵满二叉树，又或者是在数组中填充None代表空节点的常规二叉树，对于这样的数组的插入和删除应该不会导致数组中插入和删除带来的整体元素挪移（O(n)复杂度），因为只需要将数组对应的元素置换为None或者赋值就可以，这样子二叉树的插入和删除应该是O(1)的复杂度呀？请问我的理解对吗

[wbzyo]

如果直接将元素设为None，那理论上这个结点没有任何子节点了，就会出现没有父节点的两个子节点，那这也不能称为一棵二叉树了

[1435646097]

但是就算是链表表示的二叉树，父节点灰删除了，子节点应该也都要一并删除吧。

[CJSen]

def parent(self, i: int) -> int | None:
        """获取索引为 i 节点的父节点的索引"""
        return (i - 1) // 2

这边是不是应该考虑一下，如果i==0的情况，加个判断语句比较好。

def parent(self, i: int) -> int | None:
        """获取索引为 i 节点的父节点的索引"""
        if i == 0:
            return None
        return (i - 1) // 2

[krahets]

在这个类的设计中，边界判断是在 val() 方法中实现的。因此我们没有在 parent(), left(), right() 中做边界判断

[nzb15555196162]

代码有问题吧,

修改后如下代码

//    深度优先遍历
    public void dfs(int i, String order, List<Integer> res) {
//        若为空位，则返回
        if(val(i) == -1) {
            return;
        }
//        前序遍历
        if("pre".equals(order)) {
            res.add(val(i));
//            根节点 -> 左子树 -> 右子树
            dfs(left(i), order, res);
            dfs(right(i), order, res);
        }
//        中序遍历
        if("in".equals(order)) {
//            访问优先级：左子树 -> 根节点 -> 右子树
            dfs(left(i), order, res);
            res.add(val(i));
            dfs(right(i), order, res);
        }
//        后序遍历
        if("post".equals(order)) {
//            访问优先级：左子树 -> 右子树 -> 根节点
            dfs(left(i), order, res);
            dfs(right(i), order, res);
            res.add(val(i));
        }
    }

[KLYkl]

我认为原代码没问题。就是你后面那一段if的精简版而已，每个if都是根据输入的order判断运不运行，我把if判断为假的去掉，如果order是pre，原代码就是：
res.add(val(i));
dfs(left(i), order, res);
dfs(right(i), order, res);
order等于in就是
dfs(left(i), order, res);
res.add(val(i));
dfs(right(i), order, res);
后序也一样，就是跟之前的递归一模一样。还有就是你把if(val(i) == null) 改成if(val(i) == -1) ，原本数组里面可以存null的。

[nzb15555196162]

了解了，这里有个建议是if/else加上括号,不然很容易让人迷惑，另外这里if(val(i) == -1)这里我自己val(int x)返回int