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

Question

У меня есть задание, и мне нужна помощь с помощью метода.

Так у меня есть дерево, как это:

   A 
      / \ 
      B  C 
     / \/ \ 
      D E F  G 
     / \ 
     H  I 
    / \ 
    J  K 

и мой метод:

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {  

    prev = t; 

    if(t.getLeft() != null) { 
     preorderNext(t.getLeft(), v, prev); 
    } 

    if(t.getRight() != null) { 
     preorderNext(t.getRight(), v, prev); 
    } 


    if(prev == v) { 
     return t; 
    } 

    return null; 
} 

Лектор дал простую реализацию дерева. Класс называется BinaryTree, и если вы хотите связать узел с узлом, вы указываете, что такое правый и левый дочерний узел BinaryTree.

Узел имеет две ссылки (один слева и другой справа), и нет ссылки на голову.

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

Но когда я запускаю тесты, он сообщает мне, что следующий узел предзаказа из A есть B, а следующий узел предварительного заказа из K выдает исключение null, но это должно быть я?

Любые идеи о том, где я ошибаюсь? Переменная prev должна содержать ссылку на последний посещенный узел, поэтому, если он равен узлу v (который является указанным узлом, чтобы вернуть узел после v), не должен ли я получить следующий узел?

Answer 1

Ниже приведена репликация выполнения preorder traversal.

public void preOrderTraversal(BinaryTree root){ 
    if(root == null) return; 

    System.out.println(root); 
    preOrderTraversal(root.getLeft()); 
    preOrderTraversal(root.getRight()); 
} 

Примечания:

1. Я не уверен в своем подходе; почему вы возвращаете узел? В любом случае, когда root имеет значение null с таким подходом, вы можете вернуть «emptyNode» и обработать его с помощью оператора if.
2. Как вы можете видеть, я имею дело только с root, с любым уровнем root изменений. Попытайтесь визуализировать это с помощью прогона, и вы поймете эту концепцию.
3. Вам не хватает проверки нулевых узлов в начале (особенно для t).

Вы можете продолжать адаптировать свои результаты к этому.

Заключительное примечание относится к сложности выполнения этого подхода во время выполнения, поэтому я настоятельно рекомендую понять сложности во время выполнения для рекурсивных функций. Это поможет вам много в будущем. Проверьте this wikipedia article для повторных отношений.

Answer 2

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

решения задачи итерационный способ с использованием стека может быть гораздо лучше подход:

public BinaryTree preOrderNext(BinaryTree toSearch) { 

    Stack<BinaryTree> openList = new Stack<BinaryTree>(); 

    openList.push(root); 

    while (openList.empty() == false) { 
     BinaryTree curr = openList.pop(); 

     if (curr.getRight() != null) 
      openList.push(curr.getRight()); 

     if (curr.getLeft() != null) 
      openList.push(curr.getLeft()); 

     if (curr.equals(toSearch) && openList.empty() == false){ 
      return openList.pop(); 
     } 
    } 
    return null; 
} 

Этот метод не тестировался, но должен работать.

Answer 3

Я предоставляю ответ, который работает в O(h) времени работы.

class Node { 
    public int key; 
    public Node l; 
    public Node r; 
    public Node p; 

    public Node(int key) { 
     this.key = key; 
     this.l = null; 
     this.r = null; 
     this.p = null; 
    } 
} 

public Node preorderNext(Node v) { 
    if (v.l != null) { 
     return v.l; 
    } else if (v.r != null) { 
     return v.r; 
    } else { 
     while (v.p != null) { 
      if (v == v.p.l) { 
       if (v.p.r != null) { 
        return v.p.r; 
       } else { 
        v = v.p; 
       } 
      } else { 
       if (v.p.p == null) { 
        return null; 
       } else if (v.p == v.p.p.l) { 
        if (v.p.p.r != null) { 
         return v.p.p.r; 
        } else { 
         v = v.p; 
        } 
       } else { 
        v = v.p; 
       } 
      } 
     } 
     return null; 
    } 
}