Drukuj każdą ścieżkę drzewa bez rekursywnego

Question

Jak wydrukować każdą ścieżkę liści drzewa bez użycia rekursji.

To jest drzewo, NIE binarne drzewo

struct node { 
    int data 
    std::vector<node*> children; 
} 

wydrukować wszystkie ścieżki od korzenia do liścia, czyli po to drzewo

• r: jest węzeł główny
• d, m, n są dziećmi r
• x, y, z są dziećmi
• nie ma dziecko za m
• o, p 'n' są dzieci

 
-------------root 
------d   m   n 
---x y z    o p 

Wynik powinien być:

 
root-d-x 
root-d-y 
root-d-z 
root-m 
root-n-o 
root-n-p 

Próbowałem użyć nierekursywnych drogę, ale bezskutecznie.

Answer 1

Strategia jest prosta. Zejdź w dół, w prawo, a potem w górę. W każdym punkcie wiesz, gdzie iść dalej.

Zachowaj wektor, który jest twoim bieżącym miejscem w drzewie. Uruchom go w katalogu głównym. A następnie w pseudokod:

while True: 
    if not a leaf: 
     current_place.push_back(0) // move down one 
    else: 
     print current path. 
     while can't move right: 
      if at root: 
       exit() 
      current_place.pop_back() //move up one 
     current_place[-1] += 1 

Te operacje będą wymagać wywołania funkcji. Ale są to wywołania funkcji z pętlami, a nie rekursją, więc nie są rekurencyjne.

Answer 2

W końcu to tylko wykres. Istnieją różne typy przejazdów wykresów. Po prostu używaj plików dfs ze stosu i drukuj węzły, z których nie masz przednich krawędzi.

Answer 3

public static void printAllPathToLeafNonRecursive(Node root) { 

    if (root == null) { 
     return; 
    } 

    Queue<Object> q = new LinkedList<Object>(); 
    q.add(root); 
    q.add(root.data + ""); 

    while(!q.isEmpty()){ 

     Node head = (Node) q.poll(); 
     String headPath = (String) q.poll(); 

     if(head.isLeaf()){ 
      System.out.println(headPath); 
      continue; 
     } 

     if(head.left!=null){ 
      String leftStr = headPath + "->" + head.left.data; 
      q.add(head.left); 
      q.add(leftStr); 
     } 

     if(head.right!=null){ 
      String rightStr = headPath + "->" + head.right.data; 
      q.add(head.right); 
      q.add(rightStr); 
     } 
    } 


} 

Answer 4

Oto rozwiązanie w języku Python oparte wyłącznie na wstępnym iteratywnym przechodzeniu za pomocą stosu. Drukuje zarówno ścieżki, jak i sumy ścieżek.

class Stack(object): # just for reference 
    def __init__(self): 
     self.a = [] 

    def push(self, b): 
     self.a.append(b) 

    def peek(self): 
     return self.a[-1] 

    def pop(self): 
     return self.a.pop() 

    def isEmpty(self): 
     return len(self.a) == 0 

    def show(self): 
     return self.a 

def paths(troot): # you should create your own Tree and supply the root 
    current = troot 
    s = Stack() 
    s.push(current) 
    s.push(str(current.key)) 
    s.push(current.key) 

    while not s.isEmpty(): 
     pathsum = s.pop() 
     path = s.pop() 
     current = s.pop() 

     if not current.left and not current.right: 
      print 'path: %s, pathsum: %d' % (path, pathsum) 

     if current.right: 
      rightstr = path + "->" + str(current.right.key) 
      rightpathsum = pathsum * 10 + current.right.key 
      s.push(current.right) 
      s.push(rightstr) 
      s.push(rightpathsum) 

     if current.left: 
      leftstr = path + "->" + str(current.left.key) 
      leftpathsum = pathsum * 10 + current.left.key 
      s.push(current.left) 
      s.push(leftstr) 
      s.push(leftpathsum) 

Na przykład, na poniższym drzewa:

      3             
        / \ 
        / \ 
        /  \ 
        /  \ 
       /   \ 
       /   \ 
       /    \ 
       /    \ 
       1      7       
     / \     / \ 
     / \    / \ 
     /  \    /  \ 
     /  \   /  \ 
     0   2   5   8    
    / \  / \  / \  / \ 
    / \ / \ / \ / \ 
    NUL NUL NUL NUL  4  6 NUL  9  

Wyjście będzie:

>>> paths() 
    path: 3->1->0, pathsum: 310 
    path: 3->1->2, pathsum: 312 
    path: 3->7->5->4, pathsum: 3754 
    path: 3->7->5->6, pathsum: 3756 
    path: 3->7->8->9, pathsum: 3789 

Answer 5

public static void RoottoPathPrint(BinaryTreeNode root) { 
    Stack<Object> stack = new Stack<Object>(); 
    if (root == null) 
     return; 
    stack.push(root.getData() + ""); 
    stack.push(root); 
    while (!stack.isEmpty()) { 
     BinaryTreeNode temp = (BinaryTreeNode) stack.pop(); 
     String path = (String) stack.pop(); 

     if (temp.getRight() != null) { 
      stack.push(path + temp.getRight().getData()); 
      stack.push(temp.getRight()); 
     } 
     if (temp.getLeft() != null) { 
      stack.push(path + temp.getLeft().getData()); 
      stack.push(temp.getLeft()); 
     } 
     if (temp.getLeft() == null && temp.getRight() == null) { 
      System.out.println(path); 
     } 
    } 
} 

Ideą jest, aby śledzić zarówno ścieżki i węzłów w jednym stosie, gdy przechodzimy przez drzewo. Stos obiektów zajmuje się tym. Mam nadzieję, że pomogło !!

Answer 6

private void rootToLeaf(BSTNode root){ 
    Stack<Map<BSTNode,ArrayList<Integer>>> tmpStack = new Stack<Map<BSTNode,ArrayList<Integer>>>(); 
    Map<BSTNode,ArrayList<Integer>> tmpMap = new HashMap<BSTNode,ArrayList<Integer>>(); 
    //List<Integer> tmp_arraylist = new ArrayList<Integer>(); 
    ArrayList<Integer> tmpList = new ArrayList<Integer>(); 
    tmpList.add(root.data); 
    tmpMap.put(root, tmpList); 
    tmpStack.push(tmpMap); 
    while(!tmpStack.isEmpty()){ 
     Map<BSTNode,ArrayList<Integer>> temp_map = tmpStack.pop(); 
     for(BSTNode node : temp_map.keySet()){ 
      if(node.getLeft()==null && node.getRight()==null){ 
       for(int i: temp_map.get(node)){ 
        System.out.print(i+" "); 
       } 
       System.out.println(); 
      } 
      if(node.getRight()!=null){ 
       ArrayList<Integer> tmp_List = new ArrayList<Integer>(); 
       for(int i: temp_map.get(node)){ 
        tmp_List.add(i); 
       } 
       tmp_List.add(node.getRight().getData()); 
       Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>(); 
       tmphashMap.put(node.getRight(), tmp_List); 
       tmpStack.push(tmphashMap); 
      } 
      if(node.getLeft()!=null){ 
       ArrayList<Integer> tmp_List = new ArrayList<Integer>(); 
       for(int i: temp_map.get(node)){ 
        tmp_List.add(i); 
       } 
       tmp_List.add(node.getLeft().getData()); 
       Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>(); 
       tmphashMap.put(node.getLeft(), tmp_List); 
       tmpStack.push(tmphashMap); 
      } 
     } 

    } 
} 

Answer 7

Dla drzewa n-ary - Ścieżka w oparciu DFS i BFS, Sum

      100  
        // \  \ 
        1  2  3  4 
/////   / \ 
10 11 12 13 14    40 41 
           /\ 
           400 401 


public void traverseDFS(Node root) { 
    Stack<Node> s = new Stack<Node>(); 
    Stack<String> sPath = new Stack<>(); 
    Stack<Integer> sSum = new Stack<>(); 
    s.push(root); sPath.push(root.Id + ""); sSum.push(root.Id); 

    while (!s.isEmpty()) { 
     // Pop out 
     Node head = s.pop(); String headPath = sPath.pop(); Integer headSum = sSum.pop(); 
     if(head.children == null || head.children.isEmpty()){ //Leaf 
     System.out.println(headPath + "(" + headSum+")"); 
     continue; 
     } 
     for(Node child : head.children) { 
     String path = headPath + "->" + child.Id; 
     Integer sum = headSum + child.Id; 
     // Push on stack 
     s.push(child); sPath.push(path); sSum.push(sum); 
     } 
    } 
    } 

public static void traverseBFS(Node root) { 

    Queue<Node> q = new LinkedList<>(); 
    Queue<String> qPath = new LinkedList<>(); 
    Queue<Integer> qSum = new LinkedList<>(); 
    q.add(root); qPath.add(root.Id + ""); qSum.add(root.Id); 

    while(!q.isEmpty()){ 
     // Poll the q 
     Node head = q.poll(); String headPath = qPath.poll(); Integer headSum = qSum.poll(); 
     if(head.children == null || head.children.isEmpty()){ //Leaf 
     System.out.println(headPath + "(" + headSum+")"); 
     continue; 
     } 
     for(Node child : head.children) { 
     String path = headPath + "->" + child.Id; 
     Integer sum = headSum + child.Id; 
     // Add to the q 
     q.add(child); qPath.add(path); qSum.add(sum); 
     } 
    } 
    } 

class Node { 
    int Id; 
    String Data; 
    Node Parent; 
    ArrayList<Node> children; 

    public Node(int id, String data) { 
    Id = id; 
    Data = data; 
    } 
} 

Wyjście

-----------Depth FS------------- 
100->4->41(145) 
100->4->40->401(545) 
100->4->40->400(544) 
100->3(103) 
100->2(102) 
100->1->14(115) 
100->1->13(114) 
100->1->12(113) 
100->1->11(112) 
100->1->10(111) 
-----------BFS------------- 
100->2(102) 
100->3(103) 
100->1->10(111) 
100->1->11(112) 
100->1->12(113) 
100->1->13(114) 
100->1->14(115) 
100->4->41(145) 
100->4->40->400(544) 
100->4->40->401(545)