java - 迭代查找 AVL 树中的节点

Question

有人知道如何在 AVL 树中迭代搜索特定节点吗？我的意思是，随着树的高度的复杂性。我写了一些代码，但实际上我不知道如何迭代地搜索节点(递归不会有问题):

public class AuDTree<E extends Comparable<? super E>> implements AuDTreeInterface<E> {

private class Node{

    public Node left;
    public Node right;
    public Node parent;
    public E value;

    public Node(E value){
        left = null;
        right = null;
        parent = null;
        this.value = value;
    }

}

public Node root;

public AuDTree(){
    this.root = null;
}


@Override
public boolean isEmpty() {
    if(root == null){
        return true;
    }
    else{
        return false;
    }

}

@Override
public int count() {

    return count(root);

}

private int count(Node n) {
    if (n == null) {
        return 0;
    }
    if (n.left == null && n.right == null) {
        return 1;
    } else {
        return count(n.left) + count(n.right);
    }
}

@Override
public int getHeight() {
    return getHeight(root);
}

private int getHeight(Node n) {
    if (n == null) {
        return -1;
    }
    return Math.max(getHeight(n.left), getHeight(n.right)) + 1;
}

@Override
public boolean isAVLTree() {
    return isAVLTree(root);
}

public boolean isAVLTree(Node n){
     Node prev = null;

        if(root == null)
        {
            if(!isAVLTree(root.left))
            return false;

            if(prev != null && root.value.compareTo(prev.value) <= 0)
                return false;
            prev = root;
            return isAVLTree(root.right);
        }
        return true;
}

@Override
public boolean contains(E value) {
if(isEmpty()) return false;
        else if(value == root) return true;
        else{

先谢谢了:)

Answer 1

安AVL tree只是一种特殊的二叉搜索树，你可以search it同样的方法:

We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found before a null subtree is reached, then the key is not present in the tree.

对于您的实现，它看起来像这样:

public boolean contains(E value) {
    Node current = root;

    while (current != null) {
        int comparison = value.compareTo(current.value);
        if (comparison == 0) {
            return true;
        } else if (comparison < 0) {
            current = current.left;
        } else { //comparison > 0
            current = current.right;
        }
    }

    return false;
}