如果节点中没有左child，如何在二叉搜索树中获取兄弟节点

Question

我正在尝试使用递归查找其数据大于该值的第一个节点的节点，但我发现如果 N3 没有剩余 child，我无法从 N3 转到 N4。谁能帮我想出一种方法来编写这部分代码，以便我可以转到 N4，这是 N3 的兄弟点头？谢谢！

ps：它应该在移动到下一个叶子之前搜索从根到叶子的单个路径，一些预期的测试用例是

print(find(root,100000)) #Returns N8 (node search order N1,N3, N4, N8)
print(find(root,100)) #Returns root
print(find(root,800000)) #Returns N7 (node search order N1, N3, N4, N8, N2, N5, N6, N7 )
print(find(n2,200000)) #Returns N5 (search starts from subtree at N2)

下面的代码是如何构建树和我的部分代码：

#The tree definition
class BinaryTreeNode:
    def __init__(self, name,data):
        self.name = name #The name of the node
        self.data = data #Data associated with the node
        self.leftChild = None #Left child
        self.rightChild = None #Right child
    
    #adds a left and right child to the node. Note that the left child is added first
    #I.e., there may be a left child without a right child but there cannot be a right child without a left child
    def add_children(self,left,right=None): 
        self.leftChild = left
        self.rightChild = right
        
    #str function for printing the contents of a node
    def __str__(self):
        rval = self.name
        if self.leftChild:
            rval += " Left: " + self.leftChild.name
        if self.rightChild:
            rval += " Right: " + self.rightChild.name
        return rval
    
    #repr function for internal representation
    def __repr__(self):
        return self.name

#Code for building the tree
root = BinaryTreeNode("root",33000)
n1 = BinaryTreeNode("N1",55000)
n2 = BinaryTreeNode("N2",120000)
n3 = BinaryTreeNode("N3",72000)
n4 = BinaryTreeNode("N4",88000)
n5 = BinaryTreeNode("N5",224000)
n6 = BinaryTreeNode("N6",56000)
n7 = BinaryTreeNode("N7",920000)
n8 = BinaryTreeNode("N8",183000)


root.add_children(n1,n2)
n1.add_children(n3,n4)
n4.add_children(n8)
n2.add_children(n5)
n5.add_children(n6,n7)

以下是我获取节点的代码：

def find(node,value):
    if node.data>value: return node.name
    if node.leftChild is not None and node.leftChild.data >value:
        return node.leftChild.name
    if node.leftChild is not None and node.leftChild.data <=value:
        return find(node.leftChild,value)
    else:
# in this part, I think I need to find the sibling node, i.e, go from N3 to N4
        return find(node.rightChild,value)

Answer 1

编辑：您要查找的称为深度优先搜索 (DFS)。

您的二叉搜索树实现存在问题：插入新节点时它不平衡。当它可以是 O(logn) 时，这会将搜索时间增加到 O(n)。

如果您希望您的树是这样的，下面是搜索整棵树的代码：

def find(node,value):
    if node:  # equivalent to  `if node is not None`
        if node.data > value:
            return node.name
        return find(node.leftChild, value) or find(node.rightChild, value)

    # returns `None` if node is None
    # python will return node.name over None

请注意 python 只会 return 第一次出现。

如果节点中没有左child，如何在二叉搜索树中获取兄弟节点

how to get sibling node in binary search tree if there is no left child in a node

python

algorithm

binary-tree

depth-first-search