树表示由边连接的节点。 它是一个非线性数据结构。 它具有以下属性 -
- 一个节点被标记为根节点。
- 除根节点之外,每个节点都与一个父节点相关联。
- 每个节点可以有任意数量的子节点。
这里使用前面讨论的节点概念,在python中创建一个树形数据结构。 我们将一个节点指定为根节点,然后将更多节点添加为子节点。 下面是创建根节点的程序。
创建根节点
只需创建一个Node
类并添加一个值给节点。这样它将变成只有根节点的树。参考以下代码实现 -
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
print(self.data)
root = Node(199)
root.PrintTree()
执行上面示例代码,得到以下结果 -
199
向树中插入元素
要插入一个节点到树中,可使用上面创建的相同Node
类并为其添加插入。 insert
方法将节点的值与父节点进行比较,并决定将其添加为左节点或右节点。 最后,PrintTree
方法打印树。参考以下代码实现 -
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()
执行上面示例代码,得到以下结果 -
3
6
12
14
遍历树
树可以通过决定访问每个节点的序列来遍历。 正如可以清楚地看到的,可以从一个节点开始,然后访问左边的子树第一个和右边的子树。 或者也可以先访问右边的子树,然后访问左边的子树。 因此,这些树遍历方法有不同的名称。
详细请参考:https://www.yiibai.com/python/py_data_structure/python_tree_traversal_algorithms.html