二叉搜索树中节点的路径作为二叉搜索树
path to node in binary search tree as binary search tree
我正在编写一个二叉搜索树实现，我想要一个函数来查找一个节点和 returns 一个双向链表，其中包含到达该节点所用路径中的所有节点。我知道双向链表可以转换为二叉搜索树，所以能够使用相同的 class.
真的很好（也很酷）
但是，如果我沿途制作所有节点的浅表副本并开始更改它们的指针以构建我想要的二叉搜索树 return，我显然会破坏原始树。我不能只对所有节点进行深拷贝，因为我需要对原始节点的引用，我将使用它来更改原始树（可能是删除、平衡……）。
例如，我可能有一个调用 find 的添加函数，它 return 是新节点所在路径中的最后一个节点，我可以简单地将它作为子节点之一放置那里。如果我正在写一个自平衡二叉树 class（Red/Black 树，AVL 树，Splay 树），我可以从这个 class 中分离出来，拥有它会很好至少访问我刚刚添加的节点的父节点和祖父节点（我可以用额外的指针跟踪它们，但是 find 方法不是那么通用）。
当然，一个解决方案是再写一个class。另一种解决方案是采用单向链表，并使用另一个指针指向相应的原始节点。但是，在这一点上，它不仅仅是拥有一个有效的解决方案。我使用的语言是 Java，但我绝对有兴趣知道是否有任何其他语言也具有此功能。这对我来说似乎不太可能，但我可能完全遗漏了一些东西。
有谁知道是否有办法做到这一点，或者对我可以做什么有任何建议？
所以你想用二叉树用的节点class来构建双链表。我假设这个节点 class 有四个字段：leffChild、rightChild、parent、data，其中 data 保存存储在节点。现在您可以滥用这些字段来创建双向链表，例如将 leftChild 用作 prev 和 rightChild 作为双向链表中节点的 next 字段列表。如果这样做，那么您仍然可以使用该节点的 parent 和 data 字段。因此，您可以为双向链表创建新节点，但让这些节点的 parent 字段指向二叉树中的相应节点。
话虽如此，您的方法听起来有点奇怪。双向链表中的节点将有一个未使用的字段。此外，Java 提供了实现双向链表的 java.util.LinkedList。所以没有必要通过混淆使用二叉树节点来滚动你自己的节点。
我正在编写一个二叉搜索树实现，我想要一个函数来查找一个节点和 returns 一个双向链表，其中包含到达该节点所用路径中的所有节点。我知道双向链表可以转换为二叉搜索树，所以能够使用相同的 class.
真的很好（也很酷）但是，如果我沿途制作所有节点的浅表副本并开始更改它们的指针以构建我想要的二叉搜索树 return，我显然会破坏原始树。我不能只对所有节点进行深拷贝，因为我需要对原始节点的引用，我将使用它来更改原始树（可能是删除、平衡……）。
例如，我可能有一个调用 find 的添加函数，它 return 是新节点所在路径中的最后一个节点，我可以简单地将它作为子节点之一放置那里。如果我正在写一个自平衡二叉树 class（Red/Black 树，AVL 树，Splay 树），我可以从这个 class 中分离出来，拥有它会很好至少访问我刚刚添加的节点的父节点和祖父节点（我可以用额外的指针跟踪它们，但是 find 方法不是那么通用）。
当然，一个解决方案是再写一个class。另一种解决方案是采用单向链表，并使用另一个指针指向相应的原始节点。但是，在这一点上，它不仅仅是拥有一个有效的解决方案。我使用的语言是 Java，但我绝对有兴趣知道是否有任何其他语言也具有此功能。这对我来说似乎不太可能，但我可能完全遗漏了一些东西。
有谁知道是否有办法做到这一点，或者对我可以做什么有任何建议？
所以你想用二叉树用的节点class来构建双链表。我假设这个节点 class 有四个字段：leffChild、rightChild、parent、data，其中 data 保存存储在节点。现在您可以滥用这些字段来创建双向链表，例如将 leftChild 用作 prev 和 rightChild 作为双向链表中节点的 next 字段列表。如果这样做，那么您仍然可以使用该节点的 parent 和 data 字段。因此，您可以为双向链表创建新节点，但让这些节点的 parent 字段指向二叉树中的相应节点。
话虽如此，您的方法听起来有点奇怪。双向链表中的节点将有一个未使用的字段。此外，Java 提供了实现双向链表的 java.util.LinkedList。所以没有必要通过混淆使用二叉树节点来滚动你自己的节点。