chapter_tree/array_representation_of_tree/ #472
Replies: 33 comments 47 replies
-
讲得这么好为什么没有评论 |
Beta Was this translation helpful? Give feedback.
-
"完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义,(\text{None}) 只出现在最底层且靠右的位置",是靠左吧,大佬是不是误笔了 |
Beta Was this translation helpful? Give feedback.
-
不仅图画的好,讲的也很好。作为回顾和复习真的太棒啦!如果能附上代码就更美了!!! |
Beta Was this translation helpful? Give feedback.
-
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)吗 |
Beta Was this translation helpful? Give feedback.
-
妙!妙不可言!前中后序遍历实现只是res.add()位置不同,递归实在是太牛了。 |
Beta Was this translation helpful? Give feedback.
-
7.3.2 小节中 C语言实现的代码有点奇怪,请问 C语言中有 |
Beta Was this translation helpful? Give feedback.
-
大佬,有个小小的建议,要是代码里附上一些测试例子对小白就更友好了 |
Beta Was this translation helpful? Give feedback.
-
这一节太有用了,之前刷leetcode,看到二叉树的数组表示就感觉有点懵,看完讲解感觉舒服多了 |
Beta Was this translation helpful? Give feedback.
-
class ArrayBinaryTree 的 __dfs方法写的太美味了!! |
Beta Was this translation helpful? Give feedback.
-
作者你好,关于 __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) 为什么数组的二叉树遍历里有部分代码不用写呢?希望作者能帮我解答这个问题。 |
Beta Was this translation helpful? Give feedback.
-
请问上例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
|
Beta Was this translation helpful? Give feedback.
-
/* 深度优先遍历 */
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语句内 笨死自己 |
Beta Was this translation helpful? Give feedback.
-
作者你好,获取 左/右 子节点索引的方法,获取到的索引可能是超出范围的,比如索引 8 ,左、右子节点索引分别为 17、18,已超出最大 14 了~ |
Beta Was this translation helpful? Give feedback.
-
动态图在哪里 只有像PPT一样的静态图? |
Beta Was this translation helpful? Give feedback.
-
/* 获取索引为 i 节点的父节点的索引 */ |
Beta Was this translation helpful? Give feedback.
-
def dfs(self, i: int, order: str) |
Beta Was this translation helpful? Give feedback.
-
你好,这段代码 |
Beta Was this translation helpful? Give feedback.
-
这三种遍历,能够完全遍历吗?比如前序遍历,一直找左子树,当索引超量程后return,右边的数也遍历了吗? |
Beta Was this translation helpful? Give feedback.
-
图7-13, 树上的灰色数组索引是不是标错了? |
Beta Was this translation helpful? Give feedback.
-
你好,作者看完这章有个问题想问一下,用以下代码进行 前,中,后序遍历,应该没有特殊情况而发生无法预料的意外吧 |
Beta Was this translation helpful? Give feedback.
-
作为新手,dfs函数的写法感觉真的很巧妙,复用性很高啊 |
Beta Was this translation helpful? Give feedback.
-
我觉得 “映射公式的角色相当于节点中的引用” 会更好一点 |
Beta Was this translation helpful? Give feedback.
-
作者你好~请问7.3.3的二叉树局限性中,“增删节点需要通过数组插入与删除操作实现,效率较低。”这一点我不是非常可以理解,是说时间复杂度会到达O(n)的效率低吗? |
Beta Was this translation helpful? Give feedback.
-
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 |
Beta Was this translation helpful? Give feedback.
-
代码有问题吧, 修改后如下代码 // 深度优先遍历
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));
}
} |
Beta Was this translation helpful? Give feedback.
-
C# 中 DFS() 好巧妙,原来还能这样把深度遍历写成一个函数,学到了 |
Beta Was this translation helpful? Give feedback.
-
感觉二叉树的专业概念好多,看的时候需要截一个图放在旁白- - |
Beta Was this translation helpful? Give feedback.
-
可以更详细说明一下为什么“增删节点需要通过数组插入与删除操作实现,效率较低。”吗? |
Beta Was this translation helpful? Give feedback.
-
def dfs(self, i: int, order: str): |
Beta Was this translation helpful? Give feedback.
-
chapter_tree/array_representation_of_tree/
一本动画图解、能运行、可提问的数据结构与算法入门书
https://www.hello-algo.com/chapter_tree/array_representation_of_tree/
Beta Was this translation helpful? Give feedback.
All reactions