如果节点中没有剩余的子节点，如何在二进制搜索树中获取同级节点

Question

我试图使用递归为数据大于值的第一个节点找到节点，但我发现如果N3没有剩余子节点，我就无法从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

Edit：您要查找的内容称为深度优先搜索(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将只返回第一次出现的情况。