Как получить путь от корня до заданного node на двоичном дереве?

Ответ 1

Обход прерывания, иначе известный как поиск по глубине, действительно работает.

• Если вы рекурсивно реализуете обход предлога, тогда, когда вы достигнете желаемого node, вы можете развернуть свой стек (из рекурсивных вызовов) и построить свой путь в обратном порядке.

• Если вы реализуете обход предзаказов нерекурсивно, вы будете строить стек напрямую, поэтому в этом случае, когда вы достигнете желаемого node, у вас уже есть свой путь.

В дереве вашего вопроса выше алгоритм поиска пути от 1 до 7 выполняется следующим образом.

• Начните с 1, вставьте его в стек, теперь стек [1] ​​
• Пройдите влево до 2, нажмите на стек, теперь стек [1 2]
• Перейдите влево до 4, нажмите его, теперь стек [1 2 4]
• Нет детей из 4, и это не то, что вы хотите, так что поп его, теперь стек [1 2]
• Теперь, когда вы вернулись на 2, и вы уже ушли влево, теперь идите вправо, теперь стек [1 2 5]
• Нет детей из 5, поэтому pop, stack теперь [1 2]
• Вы исчерпали детей из 2, так что поп, стек теперь [1]
• Теперь вы вернулись в 1, и вы закончили левый, так что идите прямо к 3, нажмите его, теперь стек [1 3]
• Идите влево, теперь стек [1 3 6]
• 6 - лист, а не то, что вы ищете, поэтому pop, stack is [1 3]
• Теперь вам нужно перейти вправо от 3, нажать его, теперь стек [1 3 7]
• Но ЖДИТЕ! СМОТРЕТЬ! Вы пришли к node, который вы ищете! И посмотри на свой стек! Это путь, который вы хотите.

Ответ 2

Вам предоставляется двоичное дерево (root Node).. и предоставляется ключ, который может быть или не быть в дереве. Вы должны найти полный путь от корня до node.

Пример:

                A
           /           \
       B                C
         \               /
          D           E
        /    \           \
      K      L        M
    /
Z

вы указали node Z (или ключ для node) и заданы node A (root) Таким образом, ваш вывод должен быть

A B D K Z

если M задано, выход должен быть A C E M

public class main_class {
public static void main(String args[] ) {

    //first create tree
    Node rootNode = new Node ('A' , new Node('B',null,
                                             new Node('D',
                                                      new Node('K',
                                                               new Node('Z',null,
                                                               null),null),
                                                      new Node('L',null,null))),
                                    new Node('C',
                                             new Node('E',
                                                      null,
                                                      new Node('M',null,null)),null) );

    ArrayList <Node> path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'Z',path));
    System.out.println(path);
    path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'M',path));
    System.out.println(path);

}
static boolean getPath(Node rootNode, char key, ArrayList<Node> path ){
    //return true if the node is found
    if( rootNode==null)
        return false;
    if (rootNode.getVal()==key){
        path.add(rootNode);
        return true;
    }
    boolean left_check = getPath( rootNode.left,key,path);
    boolean right_check = getPath( rootNode.right,key,path);
    if ( left_check || right_check){
        path.add(rootNode);
        return true;
    }
    return false;

}
static class Node {
    char val;
    Node left;
    Node right;
    public Node( char val, Node left, Node right){
        this.left=left;
        this.right=right;
        this.val=val;
    }
    public char getVal(){
        return val;
    }
   public String toString(){
        return " " + val + " ";
    }
}

}

Ответ 3

Рассмотрим следующее дерево:

       10
     /   \
    8      2
  /  \    /
3     5  2

Подход

• Мы начинаем с корня и сравниваем его с ключом, если они совпадают, а затем печатают путь (если дерево имеет только один node, то путь содержит только корень).
• Else нажмите node в Vector (я рассмотрел вектор для сохранения пути).
• Рекурсивно Пойдите влево и вправо от дерева.

Следующий код поможет:

     void PrintPath(node* root, vector <int> v,int key)
     {
      if(!root)
      return;
      if(root->data==key)
        {
          v.push_back(root->data);
          vector<int>:: iterator it;
          for(it=v.begin();it<v.end();it++)
           {
             cout<<*it<<" ";
           }
            return;
        }
        v.push_back(root->data);
        PrintPath(root->left,v,key);
        PrintPath(root->right,v,key);
    }    

Объяснение

Пусть node будет найдено 5 (ключ) для данного дерева.

Содержание вектора на каждом шаге:

• V = 10
• V = 10,8
• V = 10,8,3 (3 не является ключом к поиску, поэтому мы вернемся назад и идем вправо)
• V = 10,8,5 (5 - это ключ, поэтому напечатайте путь).

Ответ 4

В Java есть 3 решения:
https://codereview.stackexchange.com/questions/105136/path-sum-in-binary-tree
Во-первых, рекурсивный подход, второй - с использованием 2 сатц и последний с использованием двух очередей. Надеюсь, что это поможет

Ответ 5

public List<Node<T>> getPath(T data){
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Boolean found =  getPath(root, stack, data);
        List<Node<T>> path = new ArrayList<Node<T>>();

        if(!found){
            return path;
        }
        return Arrays.asList(stack.toArray((Node<T>[])new Node[stack.size()]));
    }

    public Boolean getPath(Node<T> node, Stack<Node<T>> stack, T data){
        if(node == null){
            return false;
        }
        stack.push(node);

        if(node.data.equals(data)){
            return true;
        }
        Boolean found = getPath(node.left, stack, data) ||
                getPath(node.right, stack, data);

        if(!found ){
            stack.pop();
        }
        return found;
    }