遍历二叉搜索树

Question

我正在阅读 算法简介 我遇到了这个关于 In-order 的问题不使用堆栈或递归的二叉搜索树的遍历。提示说假设测试指针是否相等是一个合法的操作。我一直在寻找这个问题的解决方案。请给我一些指导。我不是在寻找代码。只要给我正确的方向。

完全重复此处

Answer 1

没有堆栈或递归意味着您必须使用指针。没有给你代码，也没有给你确切的答案，因为你要求不要:)

想想如何在不使用递归的情况下探索树：你需要做什么？您需要保留什么指针？树节点可以有指向父节点的指针吗？

希望有帮助。

Answer 2

我们需要一个线程二叉树来进行无递归/堆栈的有序遍历。
维基百科说“二叉树是通过使所有通常为空的右子指针指向该节点的中序后继者，以及所有通常为空的左子指针指向该节点的中序前驱者来线程化的”

所以你是给定一个普通的二叉树，将其转换为线程二叉树，这可以使用莫里斯遍历来完成。
在莫里斯遍历中，您要做的是将每个节点与其有序后继节点连接起来。所以在访问一个节点时，搜索它的有序前驱节点并设其为Pred。
然后使 Pred->right=Current 节点，我们也必须恢复更改。您可以更好地参考此 http://www.geeksforgeeks.org/archives/6358 以获得精彩的内容解释。

Answer 3

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