我正在编写一个二进制搜索树实现，我想拥有一个函数，该函数可以找到一个节点并返回到达那里的路径中所有节点的双链表。我知道可以将双向链表转换为二进制搜索树，因此能够使用相同的类确实非常好（而且很酷）。
但是，如果我沿途制作所有节点的浅表副本，并开始更改它们的指针以构建要返回的二进制搜索树，则显然会破坏原始树。我不能只是对所有节点进行深度复制，因为我需要引用原始节点，这将用于更改原始树（可以删除，平衡...）。
例如，我可能有一个调用find的add函数，该函数返回新节点将要到达的路径中的最后一个节点，我可以将其作为其中的一个子节点放置。如果我正在编写一个自平衡的二叉树类（红色/黑色树，AVL树，Splay树），我可以将其子类化，那么至少可以访问该节点的父级和祖父母级将是很好的选择我刚刚添加了（我可以使用额外的指针进行跟踪，但是find方法并不那么通用）。
当然，一种解决方案是只编写另一个类。另一个解决方案是解决一个单链列表，并使用另一个指针引用回相应的原始节点。但是，在这一点上，它不仅仅是拥有一个可行的解决方案。我使用的语言是Java，但是我肯定会对了解其他语言是否也具有某些功能感兴趣。对我来说，这似乎不太可能，但我完全可能会缺少一些东西。
有人知道是否有办法做到这一点，或者对我可能做什么有任何建议？
因此，您想使用用于二叉树的节点类来构建双链表。我假设此节点类具有四个字段：leffChild，rightChild，parent，data，其中data保留存储在节点上的数据。现在，您可以滥用这些字段来创建双向链接列表，例如通过使用双向链接列表中节点的leftChild作为prev和rightChild作为next字段。如果这样做，您仍然可以使用该节点的parent和data字段。因此，您可以为双向链表创建新节点，但是这些节点的parent字段指向二叉树中的相应节点。
话虽如此，您的方法听起来有些奇怪。双链列表中的节点将有一个未使用的字段。而且，Java提供了java.util.LinkedList，它实现了双向链表。因此，无需通过混淆使用二叉树节点来自己动手。