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

Question

我被赋予一个类，它创建一个充满nodes.each节点的二叉树，它被赋予一个父节点和一个指向其左或右子节点的指针。

二叉树节点类：

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

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

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

Answer 2

尝试递归思考。让我们从几个定义开始。

• 如果一棵树的左树和右树具有相同的高度，并且它的每一棵子树都是平衡的，那么它就是平衡的。此外，我们将一个空树定义为平衡的。
• 树的高度，h（t） = 1 最大值（h（t.left）， h（t.right））。在英语中，一棵树的高度是其较高的子树的高度的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()))

现在我们可以递归地遍历树，并通过在根上调用＜code＞is_balanced＜/code＞来检查每个节点是否平衡。

is_balancednode_A

奖励练习：我给你的代码可以工作，但它不会很好地扩展。如果树变得非常大，它的运行速度会慢得多。为什么它很慢，你能做些什么来让它更快？