0

時間をかけてサイトで同様の質問と回答をチェックし、いくつか実装しましたが、まだ行き詰まっています。私の問題は少し異なり、扱いにくいようです。ノードを入力として指定すると、ノードの階層に従う最短の通信経路を決定する必要があるというシナリオに直面しています。次のようなツリーがあるとし
                                                                                ます
                                                                                   。
                                                           ----------------------------------------------
                                                          | | |
                                               ディレクター 管理者 ディレクター 財務
                                                          | | |
                                                          | | -------------------
                                                          | | | | |
                                                   マネージャー 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)ます。また、与えられた場合、編集した Java コードは次のinorder(seven, six)ように返されます。Supervisor 1 (16) Manager 1 (6) Director Admin (2) CEO(1) Director Finance (3) Manager 3 (15) 

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とPRINT A PATH FROM ROOT TO NODE IN BINARY TREEに出会い、最後に問題を解決するのに役立ちました。最初に 2 つのノードの 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 に答える