java—如何在无序的二叉搜索树中获得节点的左右子节点？

yb3bgrhw 于 2021-07-08 发布在 Java

关注(0)|答案(1)|浏览(566)

我遇到了这个问题：下面的方法必须返回左子节点中的值，如果不存在，则返回-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...*/
}

Java binary-search-tree

来源：https://stackoverflow.com/questions/65040145/how-to-get-the-left-and-right-child-of-a-node-in-an-unordered-binary-search-tree

1条答案

按热度按时间

00jrzges1#

像这样的方法会奏效：

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;
}

你必须在两个方向都搜索 left 以及 right 子树，因为树没有排序。每次您找到一个有效的子树（即，不为null）时，您都会添加到要搜索的元素堆栈中。当满足搜索条件时停止搜索。

赞(0）回复(0）举报 2021-07-09

我来回答

java—如何在无序的二叉搜索树中获得节点的左右子节点？

1条答案

相关问题

热门标签

最新问答