Обход бинарного дерева поиска

Question

Я читал Введение в алгоритмы Я натолкнулся на эту проблему с обходом по порядку дерева двоичного поиска без использования стека или рекурсии.Хинт подсказывает, что проверка указателей на равенство является законной операцией. Я застрял в поиске решения этой проблемы.Пожалуйста, дайте мне какое-то направление.Я не ищу код.Просто дайте мне правильное направление.

Точный дубликат здесь

Answer 1

Нам нужно бинарное дерево с резьбой для выполнения обхода в порядке без рекурсии / стека. Вики говорит: «Двоичное дерево пронизывается созданием всех правильных дочерних указателей, которые обычно были бы нулевыми, указывают на преемник-префикс узла, и всеми левыми дочерними указателями, которые обычно были бы нулевыми точками, на предшественник inorder узла»

Итак, вам дано нормальное двоичное дерево, конвертируйте его в резьбовое двоичное дерево, что можно сделать с помощью Morris Traversal . В Morris Traversal вы собираетесь соединить каждый узел с его преемником по порядку. Поэтому при посещении узла найдите его предшественника по порядку и пусть он будет Pred. затем сделайте Pred-> right = Current node, и мы также должны отменить изменения. Вы можете лучше отослать это http://www.geeksforgeeks.org/archives/6358 для хорошего объяснения.

Answer 2

Здравствуйте, Parminder. Я реализовал ваш вопрос в java. Пожалуйста, проверьте его один раз

class InorderWithoutRecursion {
    public static void morrisTraversal(TreeNode root) {

        TreeNode current,pre;

    if(root == null)
        return; 

    current = root;
    while(current != null){
        if(current.left == null){
            System.out.println(current.data);
            current = current.right;
        }
        else {
      /* Find the inorder predecessor of current */
            pre = current.left;
            while(pre.right != null && pre.right != current)
            pre = pre.right;

      /* Make current as right child of its inorder predecessor */
        if(pre.right == null){
            pre.right = current;
            current = current.left;
        }

      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
        else {
            pre.right = null;
            System.out.println(current.data);
            current = current.right;
        }
      } 
  } 
}
 public static void main(String[] args) {
        int[] nodes_flattened = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        TreeNode root = TreeNode.createMinimalBST(nodes_flattened);
        morrisTraversal(root);
    }
}

Для класса TreeNode ниже код поможет вам ..

public class TreeNode {
    public int data;      
    public TreeNode left;    
    public TreeNode right; 
    public TreeNode parent;

    public TreeNode(int d) {
        data = d;
    }

    public void setLeftChild(TreeNode left) {
        this.left = left;
        if (left != null) {
            left.parent = this;
        }
    }

    public void setRightChild(TreeNode right) {
        this.right = right;
        if (right != null) {
            right.parent = this;
        }
    }

    public void insertInOrder(int d) {
        if (d <= data) {
            if (left == null) {
                setLeftChild(new TreeNode(d));
            } else {
                left.insertInOrder(d);
            }
        } else {
            if (right == null) {
                setRightChild(new TreeNode(d));
            } else {
                right.insertInOrder(d);
            }
        }
    }

    public boolean isBST() {
        if (left != null) {
            if (data < left.data || !left.isBST()) {
                return false;
            }
        }

        if (right != null) {
            if (data >= right.data || !right.isBST()) {
                return false;
            }
        }       

        return true;
    }

    public int height() {
        int leftHeight = left != null ? left.height() : 0;
        int rightHeight = right != null ? right.height() : 0;
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public TreeNode find(int d) {
        if (d == data) {
            return this;
        } else if (d <= data) {
            return left != null ? left.find(d) : null;
        } else if (d > data) {
            return right != null ? right.find(d) : null;
        }
        return null;
    }

    private static TreeNode createMinimalBST(int arr[], int start, int end){
        if (end < start) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode n = new TreeNode(arr[mid]);
        n.setLeftChild(createMinimalBST(arr, start, mid - 1));
        n.setRightChild(createMinimalBST(arr, mid + 1, end));
        return n;
    }

    public static TreeNode createMinimalBST(int array[]) {
        return createMinimalBST(array, 0, array.length - 1);
    }
}

Answer 3

Нет стека или рекурсии означает, что вы должны использовать указатели. Не предоставив ни кода, ни точного ответа, поскольку вы просили не делать этого :)

Подумайте, как исследовать дерево, не используя рекурсию: что вам нужно сделать? Какие указатели вам нужно сохранить? Может ли узел дерева иметь указатель на родителя?

Надеюсь, это поможет.