如何遍历由节点组成的二叉树?(代码在里面)

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.left(，h(t.right((。在英语中，树的高度是1+其较高子树的高度。此外，我们将假设一棵空树的高度为0

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

让我们从定义代码开始，检查树是否平衡。

defis_balanced(节点(：如果节点为"无"：return Trueleft_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_bBalanced(node.get_right(((

现在让我们定义上面使用的函数get_height。由于树的高度是其子树高度的函数，我们可以使用递归。由于递归需要一个基本情况，因此我们不会无限递归，因此我们可以使用空树的高度为0的事实。

def get_height(节点(：如果节点为"无"：return 0#假设空树的高度为0return 1+max(get_height(node.get_left(((，get_heith(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