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

Question

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

Это не двоичное дерево поиска.

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

Обработка заказов, предварительных заказов и пост-заказов не работает.

Я пытался сделать предварительный заказ, но не могу понять, как. Например, у нас есть двоичное дерево: Это НЕ двоичное дерево поиска. Мы используем узел порядка сортировки, чтобы упростить поиск пути.

     1 
   /   \
  2     3
 / \   / \
4   5 6   7 

Мы хотим найти путь от 1 до 7:

При предварительном заказе имеем:

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 

Из потока мы получаем путь от 1 -> 7 со всеми узлами на нем.

Очевидно, этого не должно быть.

Любая помощь очень ценится.

Answer 1

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

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

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

В дереве вашего вопроса выше алгоритм поиска пути от 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 - это лист, а не то, что вы ищете, так что поп, стек равен [1 3]
• Теперь вам нужно перейти вправо от 3, толкнуть его, стек теперь [1 3 7]
• Но ПОДОЖДИТЕ! СМОТРЕТЬ! Вы прибыли в узел, который ищете! И посмотри на свой стек! Это путь, который вы хотите.

Answer 2

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

Пример:

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

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

ABDKZ

, если задано M, вывод должен быть ACEM

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 + " ";
    }
}

}

Answer 3

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

       10
     /   \
    8      2
  /  \    /
3     5  2

Подход

• Мы начинаем с корня и сравниваем его с ключом, если они совпадают, затем печатаем путь (если дерево имеет только один узел, то путь содержит только корень).
• Иначе подтолкнуть узел в 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);
    }    

Объяснение

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

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

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

Answer 4

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

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