如何得到无序二叉搜索树中节点的左右子节点？

Question

我遇到了这个问题：下面的方法必须返回左侧子节点中的值，或者-1（如果它不存在）。

public int getLeftChild(int el) {...}
/* Same for the right child */

现在，参数是一个int值，它指示父节点的值。另一个问题是...树不是有序的，只有正整数值。所以，我可以在根中有一个0的值，在左边的子项中有3的值，在右边的子项中有1的值，以此类推...我想不出该怎么解决这件事。我不能将像LinkedList或Stack这样的ADT用于任何目的。二叉树类有一个字段根,类型为node：

public class Node {
    private int value;
    private Node leftChild;
    private Node rightChild;
    /*Getters and Setters...*/
}

Answer 1

类似这样的方法会起作用：

public int getLeftChild(int el) {
    int not_found = -1;
    Stack<Node> nodes_to_search = new Stack<>();
    nodes_to_search.add(this);

    while(!stack.isEmpty()){
        Node root = nodes_to_search.pop();
        if(root.value == el){
            return (root.leftChild != null) ? root.leftChild.value  : not_found;
        }
        if(root.leftChild != null)   nodes_to_search.push(root.leftChild);
        if(root.rightChild != null)  nodes_to_search.push(root.rightChild);
    }
    return not_found;
}

您必须在左和右子树中进行搜索，因为树没有排序。每次找到一个有效的子树（即，不是null)，就添加到元素堆栈中进行搜索。在满足搜索条件时停止搜索。