java Inorder BST的前身：遵循层次结构的最短通信路径

Question

我花了时间在网站上查看类似的问题和答案，并实施了一些，但我仍然被卡住了，似乎我的问题有点不同和棘手。我面临着这样一个场景，在这个场景中，我必须根据节点的层次结构确定通信的最短路径，并将该节点作为输入。假设我有一棵这样的树：
首席执行官
|
--------------------------------------
| |
主管行政主管财务主管
| |
|-------------------
| | |
经理1经理2经理3
|
---------
| |
主管1主管2

这是我的JAVA代码

public class StaffChartTraversal {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    Node<String> one = new Node<String>("1","CEO", "");
    Node<String> two = new Node<String>("2","Director Admin", "1");
    Node<String> three = new Node<String>("3","Director Finance", "1");
    Node<String> four = new Node<String>("6","Manager 1", "2");
    Node<String> five = new Node<String>("12","Manager 2", "3");
    Node<String> six = new Node<String>("15","Manger 3", "3");
    Node<String> seven = new Node<String>("16","Supervisor 1", "6");
    Node<String> eight = new Node<String>("17","Supervisor 2", "6");
    one.setLeft(two);
    one.setRight(three);
    two.setLeft(four);
    three.setLeft(five);
    three.setLeft(six);
    four.setLeft(seven);
    four.setRight(eight);
    inorder(seven);
}

private static class Node<T> {

    public Node<T> left;
    public Node<T> right;
    public T data1;
    public T data2;
    public T data3;

    public Node(T data1, T data2, T data3) {
        this.data1 = data1;
        this.data2 = data2;
        this.data3 = data3;
    }

    public Node<T> getLeft() {
        return this.left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return this.right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

public static void inorder(Node<?> n) {
    if (n != null) {
        inorder(n.getLeft());
        System.out.print(n.data2 + "(" + n.data1 + ")" + " ");
        inorder(n.getRight());
    }
}

}

现在，当在inorder()方法中指定一个节点作为输入时，它应该打印遵循层次结构的最短通信路径。因此，如果我要输入表示Supervisor 1的seven，比如inorder(seven)，程序应该输出：

Supervisor 1 (16) Manager 1 (6) Director Admin (2) CEO(1)

但从我的实现中，我得到的结果是：

Supervisor 1(16)

请我需要帮助来修复我的代码。。。谢谢
编辑：
由于@nash_ag，我已经修复了上面指出的初始问题，但是我想扩展inoorder（）方法以接受父对象的两个参数左、右子对象，因此如果给定inorder(five, six)，它应该返回Manager 2 (12) Director Finance (3) Manager 3 (15)。同样，如果给定inorder(seven, six)，它应该返回Supervisor 1 (16) Manager 1 (6) Director Admin (2) CEO(1) Director Finance (3) Manager 3 (15)
我编辑的Java代码是：

public class StaffChartTraversal {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    Node<String> zero = null;
    Node<String> one = new Node<String>(zero, "1", "CEO", "");
    Node<String> two = new Node<String>(one, "2", "Director Admin", "1");
    Node<String> three = new Node<String>(one, "3", "Director Finance", "1");
    Node<String> four = new Node<String>(two, "6", "Manager 1", "2");
    Node<String> five = new Node<String>(three, "12", "Manager 2", "3");
    Node<String> six = new Node<String>(three, "15", "Manager 3", "3");
    Node<String> seven = new Node<String>(four, "16", "Supervisor 1", "6");
    Node<String> eight = new Node<String>(four, "17", "Supervisor 2", "6");
    one.setLeft(two);
    one.setRight(three);
    two.setLeft(four);
    three.setLeft(five);
    three.setLeft(six);
    four.setLeft(seven);
    four.setRight(eight);
    inorder(four, five);

}

private static class Node<T> {

    public Node<T> parent;
    public Node<T> left;
    public Node<T> right;
    public T data1;
    public T data2;
    public T data3;

    public Node(Node<T> parent, T data1, T data2, T data3) {
        this.parent = parent;
        this.data1 = data1;
        this.data2 = data2;
        this.data3 = data3;
    }

    public Node<T> getParent() {
        return this.parent;
    }

    public Node<T> getLeft() {
        return this.left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return this.right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

public static void inorder(Node<?> n, Node<?> m) {
    if ((n != null) && (m != null)) {
        System.out.print(n.data2 + "(" + n.data1 + ") ");
        if (n.getParent().equals(m.getParent())) {
            inorder(n.getParent(), null);
        } else {
            inorder(n.getParent(), m.getParent());
        }
        System.out.print(" " +m.data2 + "(" + m.data1 + ")");
    }
}

}

它对inorder(seven, six)很有效，但是对于inorder(five, six)它返回的是Manager 2 (12) <With no common ancestor> Manager 3 (15)而不是Manager 2 (12) Director Finance (3) Manager 3 (15)请大家帮帮我

Answer 1

现在，您的代码没有为每个节点的parent保留指针，当您第一次运行inorder(seven)时，您得到运行良好的n = seven，但是作为叶节点（sevenakaSupervisor 1）没有任何子节点，因此对inorder(right)和inorder(left)的调用都返回null。因此，您将看到输出

对于解决方案，如果希望以这种方式遍历树，则需要为每个Node保留一个父级指针，或者保留一个指向root的指针，然后在该树上使用inorder

private static class Node<T> {

    public Node<T> parent;
    public Node<T> left;
    public Node<T> right;
    public T data1;
    public T data2;
    public T data3;

    public Node(Node<T> parent, T data1, T data2, T data3) { 
      this.parent = parent;
    ...

    public Node<T> getParent() {
      return this.parent;
    }

类似地，在实例化时：

Node<String> six = new Node<String>(two, "15","Manger 3", "3");
Node<String> seven = new Node<String>(four, "16","Supervisor 1", "6");
Node<String> eight = new Node<String>(four, "17","Supervisor 2", "6");

该功能现在变得更加简单：

public static void inorder(Node<?> n) {
  if (n != null) {
    System.out.print(n.data2 + "(" + n.data1 + ")" + " ");
    inorder(n.getParent());
  }
}

Answer 2

我遇到了这些教程LOWEST COMMON ANCESTOR IN A BINARY TREE和PRINT A PATH FROM ROOT TO NODE IN BINARY TREE，它们帮助我最终解决了这个问题。我首先得到了两个节点的LCA，我正在检查使用LCA来创建通信代码的最短路径。见以下方法：

//get and stores path of first child node to root
public Boolean getNodePath1(Node root, Node dest) {
    //checks return false if root is empty
    if (root == null) {
        return false;
    }
    //Checks if root is the same as destination child node before printing on both left and right
    if (root == dest || getNodePath1(root.left, dest) || getNodePath1(root.right, dest)) {
        //adds the obtained path to an ArrayList
        path1.add(root.empName + " (" + root.empID + ")");
        return true;
    }
    return false;
}

//get and stores path of second child node to root
public Boolean getNodePath2(Node root, Node dest) {
    //checks return false if root is empty
    if (root == null) {
        return false;
    }
    //Checks if root is the same as destination child node before printing on both left and right applying recursion
    if (root == dest || getNodePath2(root.left, dest) || getNodePath2(root.right, dest)) {
        path2.add(root.empName + " (" + root.empID + ")");
        return true;
    }
    return false;
}

//get the Lowest Common Ancestor of two nodes
public Node getLCA(Node root, Node n1, Node n2) {
    //checks return false if root is empty
    if (root == null) {
        return null;
    } else {
        //compares if a child node entered is the LCA
        if (root.empName.equals(n1.empName) || root.empName.equals(n2.empName)) {
            return root;
        }
        //applying recursion on both left and right nodes to derive LCA
        Node left = getLCA(root.left, n1, n2);
        Node right = getLCA(root.right, n1, n2);

        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }
}

//displays the formatted output of the shortest path of communication between the nodes that follows the hierarchy
public void showResult(OrgChartTraversal i, Node root, Node x, Node y) {
    Node z = i.getLCA(root, x, y);  //assign the LCA as the root
    //initialize new ArrayList to handle nodes
    path1 = new ArrayList();
    path2 = new ArrayList();
    //get both children nodes path to root
    i.getNodePath1(z, x);
    i.getNodePath2(z, y);
    //get the last elements which is the root for the both ArrayList which holds the derived children nodes paths
    Object str1 = path1.get(path1.size() - 1);
    Object str2 = path2.get(path2.size() - 1);
    if (str1.equals(str2)) {
        path1.remove(str1);     //remove the root in first child node path so it doesn't make the output cumbersome
        path2.remove(str2);     //remove the root in second child node path so it doesn't make the output cumbersome
    }
    //reverse the order of second child node path so it matches the requirement in the output
    Collections.reverse(path2);
    //iterate through the nodes that forms the path and print it out
    it1 = path1.iterator();
    it2 = path2.iterator();
    while (it1.hasNext()) {
        System.out.print(it1.next() + " -> ");
    }
    System.out.print(z.empName + " (" + z.empID + ")");
    while (it2.hasNext()) {
        System.out.print(" <- " + it2.next());
    }
}