0

我花时间在网站上查看了类似的问题和答案并实施了一些，但我仍然卡住了，看来我的问题有点不同和棘手。我面临这样一种情况，即在给定节点作为输入的情况下，我必须确定遵循节点层次结构的最短通信路径。假设我有一棵树：
                                                                                CEO
                                                                                   |
                                                           ------------------------------------------
                                                          | |
                                               行政总监 财务总监
                                                          | |
                                                          | -------------------
                                                          | | |
                                                   经理 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()它应该打印遵循层次结构的最短通信路径。所以如果我要输入seven哪个代表Supervisor 1比如inorder(seven)程序应该输出：

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

但是从我的实现中，我得到了这样的输出：

Supervisor 1(16)

请我在修复我的代码时需要帮助...谢谢
编辑：
感谢@nash_ag，我已经修复了上面指出的初始问题，但后来我想扩展 inorder() 方法以接受 2 个参数左右一个父母的孩子所以如果给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)请大家帮帮我

4

2 回答 2

0

我遇到了这些教程LOWEST COMMON ANCESTOR IN A BINARY TREE并在 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());
    }
}
于 2014-12-27T21:10:01.777 回答
0

现在您的代码不parent包含每个节点的指针，当您inorder(seven)第一次运行时，您会得到n = seven运行良好的指针，但是作为叶节点（seven又名Supervisor 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());
  }
}
于 2014-12-23T12:57:55.643 回答