将常规树转换为二叉树之后，如何使用二叉树找到给定一般树的节点“v”的父节点？

Question

我已经尝试了两种实现，他们不太工作。

这是我完全坚持的一个实现。

/** Returns the parent of a given node or the node itself if it is the root */ 
public Position<E> parent(Position<E> v) throws IllegalArgumentException { 
     if(bTree.isRoot(v)) { return v; } // returns the node v itself if v is the root. 
     Position<E> parent = bTree.root(); 
     // execute this recursive method and return the parent. 
     return preorderTraversal(parent, v, null); 
    } 

/* This is the helper method that will traverse the binary tree in PreOrder. It updates 
* the parent until the node v has been found. 
*/ 
private Position<E> preorderTraversal(Position<E> focusNode, Position<E> v, Position<E> parent) { 

    System.out.print(focusNode.getElement() + "\t"); 

     if (focusNode != null && v != focusNode && hasLeft(focusNode)) { 
      parent = focusNode; 
      System.out.print("setting parent to: " + parent.getElement() + "\t"); 
      preorderTraversal(bTree.left(focusNode), v, parent); 
     } 
     else if (focusNode != null && v != focusNode && hasRight(focusNode)){ 
      preorderTraversal(bTree.right(focusNode), v, parent); 
     } 
     return parent; 
    } 

// -------------- EXTRA HELPER METHODS --------------- 
private boolean hasLeft(Position<E> temp) { 
     if (bTree.left(temp) != null) return true; 
     else return false; 
    } 

    private boolean hasRight(Position<E> temp) { 
     if (bTree.right(temp) != null) return true; 
     else return false; 
    } 

这里的问题似乎是，它遍历左子树，并更新正确的父母，但在返回的值，它总是返回根节点。我似乎不明白为什么会这样。另一个是当遍历右边的子树时，我的父节点总是错误的。请帮忙！

Answer 1

你在对待左右方向时没有给出任何动机。你没有指定一个通用树是什么（一个猜测是每个节点可以有两个以上的后代，但是，由于转换后的节点似乎具有可比性：原始节点有多少个值？以及它如何转换到二叉树（左引用已经是后代引用，适用于兄弟姐妹？）给一个URL可能是合适的）。
结合检查：if (null == focusNode || v == focusNode) return parent;。
不要将值赋予与其有意义的名称相反的变量，而应该在parent之前重复左移，而是传递适当的值：preorderTraversal(bTree.left(focusNode), v, focusNode);。
如果你在条件陈述的不同部分进行不同的处理没有无可置疑和明显的原因，请发表评论：为什么你在正确的循环中通过父母？
（一个用于引用方法注释，考虑将它们升级到javadoc。）