如何使用Python在二进制树中获得节点的水平？

Question

我试图在Python中实现二进制树程序。我想添加一个功能以获得特定节点的级别。

例如： -

    10      # level 0
   /  \
  5   15    # level 1
 / \ 
3   7       # level 2

如果我们搜索节点3的级别，则应该返回

class BinaryTree:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
        
    def insert(self, data):
        if self.data == data:
            return
        if self.data<data:
            if self.left:
                self.left.insert(data)
            else:
                self.left = BinaryTree(data)
        else:
            if self.right:
                self.right.insert(data)
            else:
                self.right = BinaryTree(data)
        
    def print_tree(self):
        if self:
            print(self.data)    
        if self.left:
            self.left.print_tree()
        elif self.right:
            self.right.print_tree()
            
    def get_level(self, data, level=0):
        print(type(data))
        level += 1
        if self.data == data:
            return level
        elif self.left and self.right:
            if self.left:
                self.left.get_level(data)
            elif self.right:
                self.right.get_level(data)
        return level
    
    def in_order(self):
        if self:
            #left
            in_order(self.left)
            #root
            print(self.data, '->')
            #right
            in_order(self.right)

这是我的二进制树代码。我需要在此类中添加另一个功能，该函数将在给出值之后，告诉节点的级别

：

def get_level(node):
    #some code
    return level


get_level(10) # returns the level of the node 10

Answer 1

这对我有用：

def get_level(self, data, level=0):
    print(type(data))
    level += 1
    if self.data == data:
        return level
    if data > self.data:
        if self.left:
            return self.left.get_level(data,level)
    else:
        if self.right:
            return self.right.get_level(data,level)

    return None

对于10级为1，对于5和15为2级，对于3和7，它是3级。

对于0,1,2级别，只需删除“级别+= 1”行并在递归调用中添加级别变量中的+1。

Answer 2

在进行问题之前，您现有代码中存在一些问题：

• insert方法正在使用树的BST属性（良好），但要去错误的子树以查找插入点的位置。条件如果self.data＆lt; data，则应将其倒置为，如果self.data＆gt;数据。

• 函数inorder具有递归调用，这些调用函数不是作为方法，而是作为全局函数。因此，这意味着此功能的缩进是错误的。它应该在类之外定义，而不是内部。

我需要在此类中添加另一个功能

，您已经拥有该功能，但是它存在以下问题：

• 该功能返回一个级别，但是当您进行递归调用时，您会忽略该返回的值。
• 由于您永远不会通过级别的参数，该级别将始终以0开头，因此返回的值将始终为1。
• 使用elif self.left and self.right您忽略了节点具有的情况一个孩子。
• 从这是BST的事实中，没有任何好处，因此左右子树都经过遍历，而可以通过遵循单个路径找到数据。

我建议在没有级别参数的情况下执行此操作，然后让函数返回级别，就好像给定节点是根一样。呼叫者可以比递归调用后添加1 。

    def get_level(self, data):
        if data == self.data:
            return 0
        level = None
        if data < self.data:
            if self.left:
                level = self.left.get_level(data)
        else:
            if self.right:
                level = self.right.get_level(data)
        if level is not None:
            return level + 1