chapter_tree/binary_search_tree/ #27
Replies: 39 comments 79 replies
-
删除结点的C++代码部分,TreeNode* child = cur->left != nullptr ? cur->left : cur->right;怎么理解鸭,有点看不懂,欢迎解答 |
Beta Was this translation helpful? Give feedback.
-
您好,未来会添加get_inorder_next这个函数的具体实现吗? |
Beta Was this translation helpful? Give feedback.
-
K神,想问下删除节点那里的代码 为什么需要手动释放呢 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
大佬您好,关于删除节点的部分,子节点数量等于2的图片中的例子,如果叶节点5改为3,那个这个情况下该怎么进行删除呢? |
Beta Was this translation helpful? Give feedback.
-
二叉搜索树插入节点都是在叶子节点上插入的吗 |
Beta Was this translation helpful? Give feedback.
-
插入节点值也可用递归实现,语言:Java,请指正 public void insert(Integer value){
root = insertRecursive(root, value);
}
public TreeNode insertRecursive(TreeNode current, int value) {
if (current == null) {
return new TreeNode(value);
}
if (value > current.value){
current.right = insertRecursive(current.right,value);
}
if (value < current.value) {
current.left = insertRecursive(current.left,value);
}
return current;
} |
Beta Was this translation helpful? Give feedback.
-
小小地提一个问题,当二叉搜索树要删除的节点有两个子节点的时候,执行步骤是这样:
我的疑问是,tmp 结点都被删除了,为什么它的 tmp.val 还有值呢? // 子节点数量 = 2
else {
// 获取中序遍历中 cur 的下一个节点
TreeNode tmp = cur.right;
while (tmp.left != null) {
tmp = tmp.left;
}
// 递归删除节点 tmp
remove(tmp.val);
// 用 tmp 覆盖 cur
cur.val = tmp.val;
} |
Beta Was this translation helpful? Give feedback.
-
大佬,看的时候思考了一下,“二叉搜索树的中序遍历序列是升序的”是否也是二叉搜索树应该满足的条件呢?如果现在将本页最上方的“3”换成“999”,也满足条件1和2,但中序遍历就无序了 |
Beta Was this translation helpful? Give feedback.
-
我明白二叉搜索树的优点了,它就像一个脚手架,搭起来以后方便以后动态的操作,所以值得花时间先把它构建起来。如果数据是需要经常维护的,那么它的优势就大大发挥起来了,另外中序遍历的有序性是在它搭建的过程中实现的,算是一个隐含的条件 |
Beta Was this translation helpful? Give feedback.
-
你好,想问下,删除部分的代码,有两个子节点的时候,换成下面的代码,会有什么问题吗 TreeNode tmp = targetNode.left;
while (tmp.right != null) {
tmp = tmp.right;
} |
Beta Was this translation helpful? Give feedback.
-
请问 一下最后的递归删除这个,不是又从树顶部搜索到最底部再删除了吗?这是不是性能很不好,能不能直接删除,记录父节点的引用,直接prev.left = null。 // 递归删除节点 tmp
remove(tmp!.val);
` |
Beta Was this translation helpful? Give feedback.
-
我发现这些评论是宝藏 |
Beta Was this translation helpful? Give feedback.
-
请问如何构建一棵搜索树呢?选择根节点岂不是很重要。 |
Beta Was this translation helpful? Give feedback.
-
删除操作好难啊,看了40多分钟才看明白,特别是子节点数量 = 0 / 1 时,我画图一个一个比对的。是不是分开写会清晰一点。 |
Beta Was this translation helpful? Give feedback.
-
else: |
Beta Was this translation helpful? Give feedback.
-
递归删除的部分理解了好久才勉强想通...
一看到递归就犯晕,就觉得它要往下递很多层,难以在脑海中展开. |
Beta Was this translation helpful? Give feedback.
-
“然而,如果我们在二叉搜索树中不断地插入和删除节点,可能导致二叉树退化为图 7-23 所示的链表,” 感觉不用不断地插入和删除,在初始化二叉树的过程中,如果数据是有序的比如 "1,2,3,4,5,6,7", 这样构造的单链表直接就是链表 不知道这样想对不 |
Beta Was this translation helpful? Give feedback.
-
各位大佬,我在学的时候写了一个交互式读节点的,大家实现的是时候可以拿来查看,方便一点
|
Beta Was this translation helpful? Give feedback.
-
勘误: 原文: if cur.borrow().left.is_none() || cur.borrow().right.is_none() {
// 当子节点数量 = 0 / 1 时, child = nullptr / 该子节点
let child = cur.borrow().left.clone().or_else(|| cur.borrow().right.clone());
let pre = pre.unwrap();
**let left = pre.borrow().left.clone().unwrap();** // ######### 该行有可能`panic`,因为pre可能没有左子树,需要先进行is_some()判断后再unwrap() ######
// 删除节点 cur
if !Rc::ptr_eq(&cur, self.root.as_ref().unwrap()) {
if Rc::ptr_eq(&left, &cur) {
pre.borrow_mut().left = child;
} else {
pre.borrow_mut().right = child;
}
} else {
// 若删除节点为根节点,则重新指定根节点
self.root = child;
}
} 另外有个小建议:Rust支持模式匹配,在进行多分支判断的时候使用match很容易理解,也更易读,可以考虑使用,例如: if let Some(to_remove) = cur {
let (left_child, right_child) = (
to_remove.borrow().left.clone(),
to_remove.borrow().right.clone(),
);
match (left_child.clone(), right_child.clone()) {
(None, None) | (None, Some(_)) | (Some(_), None) => {
// only has 0/1 child, to remove the node...
(Some(_), Some(_)) => {
// has 2 child, so recursion remove...
}
}
} // else cur is none and nothing to remove 本章节之前的数据结构我学习的时候都用Rust实现了一遍,如有需要,可以参考: |
Beta Was this translation helpful? Give feedback.
-
你好,请问在C语言实现removeItem中, 没有释放cur指针的内存,而是改变pre的left或者right的指向。是不需要释放吗?还是哪里操作了我没有看到。谢谢 |
Beta Was this translation helpful? Give feedback.
-
老师好,C语言代码,在第3点,删掉节点那,递归删除,只需要遍历cur->right就可以吧?为何填了bst? |
Beta Was this translation helpful? Give feedback.
-
作者,你好,看完我有个疑问,二叉排序树删除节点后,是向左找最大,还是向右找最小。 |
Beta Was this translation helpful? Give feedback.
-
建议在二叉搜索树章节中增加查找,插入,删除的递归操作版本,作为下一节 AVL 树中插入,删除操作的先导,也能进一步增强对递归操作的理解。 |
Beta Was this translation helpful? Give feedback.
-
我7-4-3看了几个小时正常吗 |
Beta Was this translation helpful? Give feedback.
-
老师你好,为什么表7-2数组与搜索树的效率对比图中的无序数组的时间复杂度查找元素是O(n),插入元素是O(1),我理解数组的查找是根据索引操作的,时间复杂度应该是O(1),插入元素,后面元素都会向后移动一位,时间复杂度是O(n),麻烦老师帮忙解答下 |
Beta Was this translation helpful? Give feedback.
-
老师您好,7.4.1二叉搜索树的操作中3.删除节点部分的示例(度为2)如果修改成nex节点还有个右孩子,并且代码中
注释”//递归删除节点tmp“如果修改为“//单层递归删除节点tmp,处理tmp节点度为1” |
Beta Was this translation helpful? Give feedback.
-
k神,强烈希望红黑树上架啊 |
Beta Was this translation helpful? Give feedback.
-
有个问题哇,查找节点部分的Python可视化运行显示的是插入节点的可视化 |
Beta Was this translation helpful? Give feedback.
-
老师,在删除那里我有一点不明白。 |
Beta Was this translation helpful? Give feedback.
-
chapter_tree/binary_search_tree/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_tree/binary_search_tree/
Beta Was this translation helpful? Give feedback.
All reactions