如何遍历由节点组成的二叉树？ （里面的代码）
How do I traverse binary tree made up of nodes? (code inside)
我得到了一个 class，它创建了一个充满 nodes.each 节点的二叉树，节点被赋予了父节点和指向其左或右子节点的指针。
二叉树节点class:
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 级，我需要 return 为真，所以上面的树会 return 为真。我该怎么做呢？谢谢！
可以遍历树的左右两边，求到叶子的最大路径长度：
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
尝试递归思考。让我们从一些定义开始。
- 如果一棵树的左树和右树具有相同的高度并且它的每个子树都是平衡的，那么这棵树就是平衡的。我们还将定义一棵空树作为平衡树。
- 一棵树的高度，h(t) = 1 + max(h(t.left), h(t.right))。在英语中，一棵树的高度是 1 + 它更高的子树的高度。我们还假设一棵空树的高度为 0。
因此，对于树中的每个节点，我们都可以检查其两个子节点的高度并进行比较。如果它们不相等，我们就知道树不平衡，我们 return 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)
额外练习：
我给你的代码可以工作，但不能很好地扩展。如果树变得非常大，它会 运行 慢得多。为什么它很慢，您可以做些什么让它更快？
我得到了一个 class，它创建了一个充满 nodes.each 节点的二叉树，节点被赋予了父节点和指向其左或右子节点的指针。
二叉树节点class:
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 级，我需要 return 为真，所以上面的树会 return 为真。我该怎么做呢？谢谢！
可以遍历树的左右两边，求到叶子的最大路径长度：
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
尝试递归思考。让我们从一些定义开始。
- 如果一棵树的左树和右树具有相同的高度并且它的每个子树都是平衡的，那么这棵树就是平衡的。我们还将定义一棵空树作为平衡树。
- 一棵树的高度，h(t) = 1 + max(h(t.left), h(t.right))。在英语中，一棵树的高度是 1 + 它更高的子树的高度。我们还假设一棵空树的高度为 0。
因此，对于树中的每个节点，我们都可以检查其两个子节点的高度并进行比较。如果它们不相等，我们就知道树不平衡，我们 return 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)
额外练习： 我给你的代码可以工作，但不能很好地扩展。如果树变得非常大，它会 运行 慢得多。为什么它很慢，您可以做些什么让它更快？