遍历二进制搜索树

Question

我在阅读算法简介时遇到了这个关于在不使用堆栈或递归的情况下按顺序遍历二进制搜索树的问题。Hint说，假设测试指针是否相等是合法的操作。我一直在寻找这个问题的解决办法。请给我指路。我不是在找代码。只要给我正确的方向。

此处完全重复

Answer 1

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

思考如何在不使用递归的情况下探索树：您需要做什么？您需要保留哪些指针？树节点是否可以有指向父节点的指针？

希望能有所帮助。

Answer 2

我们需要一个线程化的二进制树来执行顺序遍历，而不需要递归/堆栈。Wiki说："二进制树是通过使所有正常情况下为空的右子指针指向节点的有序后继指针，而所有正常情况下为空的左子指针指向该节点的有序前导指针来线程化的。"

因此，您得到了一个普通的二进制树，将其转换为线程二进制树，这可以使用Morris Traversal来完成。在Morris Traversal中，您要做的是将每个节点与其顺序继承节点连接起来。因此，当访问一个节点时，按顺序搜索它的前一个节点，并让它成为Pred。然后使Pred->right=当前节点，我们也必须恢复更改。你可以更好地参考这个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);
    }
}