问题标签 [binary-search-tree]

我如何在python中表示二叉搜索树？

我想知道在计算机科学背景下对“祖先”定义的共识是什么。

我只问是因为在《算法导论》，第二版，p。259 有一个算法的描述Tree-Successor(x)看起来很奇怪。在寻找节点x的后继者时，

[...] 如果节点x的右子树为空且x有后继y，则y是x的最低祖先，其左孩子也是x的祖先。

在一个根有 key2和 children的二叉搜索树1中3， 的后继1是它的 parent 2。在这种情况下，x是x的继任者y的左孩子。那么，根据本书的定义，x必须是它自己的祖先，除非我遗漏了什么。

我在勘误表中没有找到任何关于此的内容。

我编写了上面的代码来实现二叉搜索树，但是插入方法没有按预期工作，它甚至无法添加根元素。我无法理解原因。

我正在阅读《数据结构和算法：带示例的注释参考》一书中使用的二叉树删除节点算法

在第 34 页，案例 4（删除具有左右子树的节点），书中描述的以下算法看起来不起作用，可能我可能错了，有人可以帮我解决我所缺少的。

以下行如何从子树中删除最大值FindParent(largestValue).Right <- 0

对于给定的二叉树，找到也是二叉搜索树的最大子树？

例子：

输入：

输出：

今天，我的教授在课堂上说有一个我以前从未听说过的平衡二叉搜索树。我想知道是否有没有旋转的平衡二叉搜索树？据我了解，Balance Binary Search Tree 是 AVL 树。除此之外，我认为不可能建立一个“平衡二叉搜索树”。但是，如果有这样的数据结构，我怎么能从一系列随机数中构建一个“平衡二叉搜索树”呢？

谢谢，

这是在维基百科上找到的关于 BST 的一些代码：

现在这是一棵二叉树：

如果我正在搜索 11，并且我按照上面的算法，我从 10 开始，我向右走到 12，然后向左走到 9。我到达树的末端却没有找到 11。但是 11 存在于我的树中，它只是在另一边。

您能否解释一下二叉树中该算法​​在我的树上工作的限制是什么？

谢谢。

我一直在使用驱动程序来测试我的一个数据结构（二叉搜索树），我遇到了这个问题。- 当我在 bst 中插入超过 2 个对象时会发生这种情况 - 我正在尝试做的事情：我将 4 个对象插入到树中，然后我正在删除 2 个对象，然后打印出我的 find 方法，以便它显示是否没有找到我要求的对象。例如：

我运行它时收到此错误：

线程“主”java.lang.ClassCastException 中的异常：TreeNode 无法在 Driver5.main(Driver5.java:36) 的 BinarySearchTree2.delete(BinarySearchTree2.java:83) 处转换​​为 java.lang.Comparable

然后指向我的 bst 类中的删除方法，即：

错误直接指向我的删除方法中的这一行：

我一直在使用驱动程序来测试我的一个数据结构（二叉搜索树），我遇到了这个问题。- 当我在 bst 中插入超过 2 个对象时会发生这种情况 - 我正在尝试做的事情：我将 4 个对象插入到树中，然后我正在删除 2 个对象，然后打印出我的 find 方法，以便它显示是否没有找到我要求的对象。例如：

我在 bst 中收到错误：

整个删除是：

BST 中元素的后继是该元素在由中序遍历确定的排序顺序中的后继。CLRS 的算法教科书（麻省理工学院出版社的算法简介）中介绍了当每个节点都有指向其父节点的指针时查找后继节点。

这里寻找后继的想法是——如果节点的右子树x非空，则后继x是右子树中的最小元素。否则，后继者是x其左孩子也是其祖先的最低祖先x（假设节点是其自身的祖先）。

我们可以不使用指向父节点的指针找到后继节点吗？

有时我们的树节点没有这个指针。我挣扎了几个小时，但无法编写正确的代码。