Suche nach Pfad Zwischen Zwei Knoten in einem Binären Baum

Habe ich die folgende einfache Struktur:

Suche nach Pfad Zwischen Zwei Knoten in einem Binären Baum

Mein Ziel ist es, den Weg zu finden zwischen den beiden manager-Knoten.

Werden die beiden Knoten ausgewählt werden, die Eingabe in der cmd.

So kann der Benutzer-Typ "java BinaryTree manager1 manager2' und in der Ausgabe wird der Pfad benötigt, der zweite manager. Dieses Beispiel soll Folgendes ausgegeben:

'Manager1 > Boss < Manager2'

Den code habe ich so weit definiert den Knoten, aber ich brauche eine Methode findPath drucken Sie den Pfad.

CODE: `

public class BinaryTree 
    {

 public static void main(String[] args)
 {
  Node boss = new Node(1);
  Node manager1 = new Node(2);
  Node manager2 = new Node(3);

  boss.left = manager1;
  boss.right = manager2;

  String path = findPath(args[0], args[1]);
  System.out.println(path);
  } 

 static class Node
 {
  Node left;
  Node right;
  int value;

  public Node(int value)
  {
   this.value = value;
  }
 }
}`

Vielen Dank für jede Hilfe 🙂

  • Hat Ihr Baum haben jede vorhersagbare / erschließbare Struktur? Das ist, können Sie sagen, ob eine Person wird in der linken oder rechten Unterbaum durch eine Regel? Wenn nicht, wirst du keine chance haben, aber Sie müssen tun, eine vollständige Traversierung des Baums auf der Suche, wo sich die Knoten, die Sie suchen.
  • Ja, ich hätte diese, Knoten-id ' s für das obige Beispiel so würde es sein Chef (1), Manager1(2), manager2(3)
  • Und was ist die Regel, die regelt, dass 2 Links und 3 rechts, Kind 1? Klar, es ist nicht die übliche weniger als " - relation.
  • stackoverflow.com/questions/22960057/... und geeksforgeeks.org/find-distance-two-given-nodes könnte hilfreich sein.
  • Wir können versuchen, die kleinen speed-up-Prozess, indem Sie auf übergeordneten Knoten. Dann den besten Weg zu finden den Weg zwischen die Führungskräfte der Suche nach der ersten gemeinsamen Vorfahren (das kann man in logn - nur Sie werden vollen Pfad von der Wurzel zu manager1, dann kompletten Pfad von der Wurzel zu manager2, dann finden letzten gemeinsamen Knoten). Dann sind Sie nur den Druck Weg von Manager1 zu Ahnen, und vom Vorfahren auf Manager2.
  • Ich glaube, dass ein vollständiges Durchlaufen des Baumes erforderlich ist. Sie haben Zugriff auf alle code-Beispiele, wie dies zu tun? Dank

InformationsquelleAutor Conor Bradley | 2014-12-02
  1. 3

    In den meisten Allgemeinen Sinn, die Sie finden, müssen die Pfade von der Wurzel zu jedem Knoten, und führen Sie Sie zusammen.

    Wie finden Sie die Pfade hängt von der Anordnung des Baumes; im schlimmsten Fall ist eine vollständige Traversierung des Baumes.

    In der merge-Schritt, prune alle gemeinsamen Vorfahren von beiden Pfaden, aber verfolgen die nächsten gemeinsamen Vorfahren. Der Pfad, den Sie wollen, ist das Gegenteil von dem, was übrig geblieben ist, den Weg zu manager-1, dann die nächsten gemeinsamen Vorfahren ("Chef" im Diagramm), dann ist der Weg zu manager-2.

    Stellen Sie sicher, um Platz für die Fälle, in denen ein manager ist ein Vorfahre des anderen (der merge-Prozedur, die ich beschrieben funktioniert immer noch, aber einer der getrimmt Pfade leer). Auch stellen Sie sicher, trap oder Platz für Fälle, in denen manager 1 = = - manager 2.

    Wenn Ihr Baum hat die Struktur über die einfache Baum-Topologie, dann kann es möglich sein, zu optimieren, einige der oben genannten, vor allem den Pfad zu finden -.

    • Ich glaube, dass ein vollständiges Durchlaufen des Baumes erforderlich ist. Sie haben Zugriff auf alle code-Beispiele, wie dies zu tun? Dank
    • Die beiden wichtigsten Entscheidungen für eine vollständige Baum-traversal sind depth-first search und breadth-first-Suche. Sie sollten finden zahlreiche Erläuterungen und code-Beispiele verwenden diese Begriffe. Ihr Fall ist etwas besonderes, du musst Bedenken, dass der Pfad zu jedem Knoten, aber das ist machbar.
    InformationsquelleAutor John Bollinger
  2. 0

    Hier ist das Programm zum drucken der Pfad zwischen 2 Knoten.

    import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PrintPath {

    static List<Node> path = new ArrayList<Node>();
    static boolean foundBoth;
    /**
     * @param args
     */
    public static void main(String[] args) {
        Node root = Node.createTree();
        printPath(root,9,11);
        System.out.println(path);
    }

    static boolean printPath(Node root,int val1 ,int val2){
        if(root==null){
            return false;
        }
        if(root.data == val1 || root.data == val2){
            addToPath(root);
            if(!foundBoth)
                foundBoth = findDown(root,(root.data==val1)?val2:val1);
            return true;
        }
        if(!foundBoth){
        boolean left = printPath(root.getLeft(), val1, val2);
        if(left){
            addToPath(root);
        }
        boolean right = printPath(root.getRight(), val1, val2);
        if(right)
        addToPath(root);
        return (left|| right);
        }else{
            return true;
        }

    }

    private static void addToPath(Node root) {
        path.add(root);
    }


    static boolean findDown(Node root,int val2){
        if(root == null){
            return false;
        }
        if(root.data == val2){
            addToPath(root);
            return true;
        }
        boolean left = findDown(root.getLeft(), val2);
        if(left){
            addToPath(root);
            return true;
        }
        boolean right = findDown(root.getRight(), val2);
        if(right){
            addToPath(root);
            return true;
        }
        return false;
    }

}
    • Dieser code funktioniert in der Suche nach allen Knoten, die auf dem Pfad liegen b/w 2 Knoten. Ich werde versuchen, weiter optimieren, und erneut veröffentlichen.
    InformationsquelleAutor RockSolid
Schreibe einen Kommentar