二叉搜索树中节点的路径作为二叉搜索树
我正在编写一个二进制搜索树实现，我希望有一个函数来查找节点，并返回路径中所有节点的双向链表。我知道双向链表可以转换成二叉树，所以能够使用相同的类将会很好(也很酷)。
但是，如果我对沿途的所有节点进行浅层复制，并开始更改它们的指针来构建我想要返回的二进制搜索树，那么我显然会破坏原始的树。我不能只制作所有节点的深度副本，因为我需要对原始节点的引用，我将使用它来更改原始树(可以是删除、平衡等)。
例如，我可能有一个调用find的add函数，它将路径中的最后一个节点返回到新节点要去的位置，我可以简单地将它作为其中的一个子节点。如果我正在编写一个自平衡的二叉树类(Red/Black Tree，AVL Tree，Splay Tree)，我可以从这个类继承它，那么至少可以访问我刚刚添加的节点的父节点和祖节点将是很好的(我可以用额外的指针来跟踪它们，但这样find方法就不那么通用了)。
当然，一种解决方案是只编写另一个类。另一种解决方案是采用单链表，并使用另一个指针引用相应的原始节点。但是，在这一点上，这不仅仅是关于拥有一个有效的解决方案。我使用的语言是Java，但我肯定有兴趣知道是否有其他语言也有这方面的功能。这对我来说似乎不太可能，但我可能完全遗漏了一些东西。
有没有人知道有什么方法可以做到这一点，或者有什么建议可以代替我呢？
回答 1
Stack Overflow用户
发布于 2020-03-20 14:14:34
因此，您希望使用用于二叉树的节点类来构建双向链表。我假设这个节点类有四个字段：leffChild、rightChild、parent、data，其中data保存节点上存储的数据。现在，您可以滥用这些字段来创建双向链表，例如，使用leftChild作为双向链表中节点的prev字段，使用rightChild作为节点的next字段。如果这样做了，那么您仍然可以使用该节点的parent和data字段。因此，您可以为双向链表创建新节点，但使这些节点的parent字段指向二叉树中的相应节点。
话虽如此，你的方法听起来有点奇怪。双向链表中的节点将有一个未使用的字段。此外，Java还提供了实现双向链表的java.util.LinkedList。因此，没有必要通过模糊使用二叉树节点来滚动您自己的节点。
https://stackoverflow.com/questions/60767793
复制相似问题
腾讯云开发者
