如何遍历由节点组成的二叉树？（内部代码）

Question

我得到了一个类，它创建了一个二叉树，里面充满了每个节点节点被赋予一个父节点和一个指向其左或右子节点的指针。你知道吗

二叉树节点类：

class BTNode():
''' a class that represents a binary tree node'''
def __init__(self, data, parent=None, left_child=None, right_child=None):
    '''(BTNode, obj, BTNode, BTNode, BTNode) -> NoneType
    Constructs a binary tree nodes with the given data'''

    self._parent = parent
    self._left = left_child
    self._data = data
    self._right = right_child

def set_parent(self, parent):
    '''(BTNode, BTNode) -> NoneType
    set the parent to the given node'''
    self._parent = parent
def set_left(self, left_child):
    '''(BTNode, BTNode) -> NoneType
    set the left child to the given node'''
    self._left = left_child

def set_right(self, right_child):
    '''(BTNode, BTNode) -> NoneType
    set the right child to the given node'''
    self._right = right_child
def set_data(self, data):
    '''(BTNode, obj) -> NoneType
    set the data at this node to the given data'''
    self._data = data    

def get_parent(self):
    '''(BTNode) -> BTNode
    return the pointer to the parent of this node'''
    return self._parent

def get_left(self):
    '''(BTNode) -> BTNode
    return the pointer to the left child'''
    return self._left

def get_right(self):
    '''(BTNode) -> BTNode
    return the pointer to the right child'''
    return self._right   
def get_data(self):
    '''(BTNode) -> obj
    return the data stored in this node'''
    return self._data

def has_left(self):
    '''(BTNode) -> bool
    returns true if this node has a left child'''
    return (self.get_left() is not None)
def has_right(self):
    '''(BTNode) -> bool
    returns true if this node has a right child'''
    return (self.get_right() is not None)  
def is_left(self):
    '''(BTNode) -> bool
    returns true if this node is a left child of its parent'''
    # you need to take care of exception here, if the given node has not parent
    return (self.get_parent().get_left() is self)
def is_right(self):
    '''(BTNode) -> bool
    returns true if the given node is a right child of its parent'''
    # you need to take care of exception here, if the given node has not parent
    return (self.get_parent().get_right() is self)
def is_root(self):
    '''(BTNode) -> bool
    returns true if the given node has not parent i.e. a root '''
    return (self.get_parent() is None)

如何创建树的代码示例：

''' create this BT using BTNode
             A
           /   \
         B      C   
        /\       \
       D  E      F
                /
               G
'''
node_G = BTNode("G")
node_F = BTNode("F", None,node_G)
node_G.set_parent(node_F)
node_C = BTNode("C", None, None, node_F)
node_F.set_parent(node_C)
node_D = BTNode("D")
node_E = BTNode("E")
node_B = BTNode("B",None, node_D, node_E)
node_D.set_parent(node_B)
node_E.set_parent(node_B)
node_A = BTNode("A",None, node_B, node_C)
node_B.set_parent(node_A)

我不知道怎么穿过这棵树。有人建议我使用递归，但我不知道如何使用。例如，如果树的高度相差最多1级，我需要返回True，这样上面的树将返回True。我该怎么做？谢谢！你知道吗

Answer 1

试着递归地思考。让我们从几个定义开始。你知道吗

• 一棵树是平衡的，如果它的左树和右树具有相同的高度，并且它的每个子树都是平衡的。此外，我们将定义一个空树作为平衡。你知道吗
• 树的高度，h（t）=1+max（h（t.左），h（t.右））。在英语中，树的高度是1+较高的子树的高度。我们还假设一棵空树的高度为0。你知道吗

因此，对于树中的每个节点，我们可以检查其两个子节点的高度并进行比较。如果它们不相等，我们就知道树是不平衡的，我们返回false。你知道吗

让我们从定义检查树是否平衡的代码开始。你知道吗

def is_balanced(node):
    if node is None:
        return True
    left_height = get_height(node.get_left())
    right_height = get_height(node.get_right())
    return left_height == right_height and is_balanced(node.get_left()) and is_balanced(node.get_right())

现在让我们定义上面使用的函数get_height。因为树的高度是子树高度的函数，所以我们可以使用递归。因为递归需要一个基本情况，所以我们不能无限递归，所以我们可以使用空树的高度为0的事实。你知道吗

def get_height(node):
    if node is None:
        return 0 # Assuming empty tree has a height of 0
    return 1 + max(get_height(node.get_left()), get_height(node.get_right()))

现在我们可以递归地遍历树，并通过调用根上的is_balanced来检查每个节点是否平衡。你知道吗

is_balanced(node_A)

奖励练习： 我给你的代码可以工作，但不能很好地扩展。如果这棵树长得很大，它就会跑得慢得多。为什么它慢？你能做些什么使它更快？你知道吗

Answer 2

您可以遍历树的左右两侧，以找到叶的最大路径长度：

class Tree:
  def __init__(self, **kwargs):
    self.__dict__ = {i:kwargs.get(i) for i in ['value', 'left', 'right']}
  def get_length(self, current=[]):
    yield current+[1]
    yield from getattr(self.left, 'get_length', lambda _:[])(current+[1])
    yield from getattr(self.right, 'get_length', lambda _:[])(current+[1])
  def right_length(self):
    return len(max(getattr(self.right, 'get_length', lambda :[[]])(), key=len))
  def left_length(self):
    return len(max(getattr(self.left, 'get_length', lambda :[[]])(), key=len))

t = Tree(value = 'A', left=Tree(value='B', left=Tree(value='D'), right=Tree(value='E')), right = Tree(value='C', left = Tree(value='F', left=Tree(value='G'))))
print(t.right_length() - t.left_length())

输出：

1