Печать каждого листа пути дерева без рекурсивного

Question

Как распечатать каждый путь к дереву без использования рекурсии.

Это дерево, НЕ бинарного дерева

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

печать все пути от корня до листа, то есть следующее дерево при

• г: является корневым узлом
• d, m, n are r's children
• x, y, z are d s дети
• нет ребенка для т
• о, р являются н-х детей

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

Результат должен быть:

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

Я пытался использовать нерекурсивную путь, но потерпел неудачу.

Answer 1

Стратегия проста. Идите вниз, прямо, затем вверх. В каждом пункте вы знаете, куда идти дальше.

Сохраните вектор, который является вашим текущим местом в дереве. Начните его с корня. А затем в псевдокоде:

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 

Эти операции потребуют вызова функций. Но они являются вызовами функций с циклами, а не рекурсией, поэтому они не являются рекурсивными.

Answer 2

В конце концов, это всего лишь график. Существуют разные типы обходов графика. Просто используйте dfs со стеком и напечатайте узлы, из которых у вас нет передних ребер.

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

Это решение на основе Python, основанное исключительно на итеративном обходе с предварительным порядком с использованием стека. Печатает как пути, так и пути.

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) 

Например, для следующего дерева:

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

Выходной сигнал будет:

>>> 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); 
     } 
    } 
} 

Идея заключается в том, чтобы следить за оба пути и узлы в одном стеке, когда мы пересекаем дерево. Стек этого объекта позаботится об этом. Надеюсь, что помогло!

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

Для п-арной дерева - DFS и 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; 
    } 
} 

Выход

-----------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)