Python - 二叉树

上一页
下一页

Tree 表示由边连接的节点。它是一个非线性数据结构。它具有以下属性 -

  • 一个节点被标记为 Root node （根节点）。
  • 除根节点以外的每个节点都与一个父节点相关联。
  • 每个节点都可以有一个 chid node 的 arbiatry 编号。

我们使用前面讨论的概念 os 节点在 python 中创建一个树数据结构。我们将一个节点指定为根节点，然后添加更多节点作为子节点。以下是创建根节点的程序。

创建根

我们只需创建一个 Node 类，并为该节点添加 assign 值。这将变为只有根节点的 tree。

例


class Node:
	 	def __init__(self, data):
	 	 	 self.left = None
	 	 	 self.right = None
	 	 	 self.data = data
	 	def PrintTree(self):
	 	 	 print(self.data)

root = Node(10)
root.PrintTree()

输出

执行上述代码时，它会产生以下结果 -

10

插入到树中

要插入到树中，我们使用上面创建的相同节点类，并向其添加插入类。插入类将节点的值与父节点进行比较，并决定将其添加为左节点或右节点。最后，使用 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

遍历树

可以通过决定访问每个节点的序列来遍历树。正如我们可以清楚地看到的，我们可以从一个节点开始，然后先访问左侧的子树，然后访问右侧的子树。或者我们也可以先访问右子树，然后再访问左子树。因此，这些树遍历方法有不同的名称。

树遍历算法

遍历是一个访问树的所有节点的过程，也可以打印它们的值。因为，所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们有三种方法可以遍历一棵树。

  • 顺序遍历
  • 预购遍历
  • 后序遍历

顺序遍历

在这种遍历方法中，首先访问左子树，然后访问根，然后访问右子树。我们应该永远记住，每个节点都可以代表一个子树本身。

在下面的 python 程序中，我们使用 Node 类为根节点以及左节点和右节点创建占位符。然后，我们创建一个 insert 函数来向树中添加数据。最后，通过创建一个空列表并首先添加左节点，然后添加根节点或父节点来实现 In-order 遍历逻辑。

最后添加左侧节点，完成 In-order 遍历。请注意，每个子树都会重复此过程，直到遍历完所有节点。

例


class Node:
	 	def __init__(self, data):
	 	 	 self.left = None
	 	 	 self.right = None
	 	 	 self.data = data
# Insert Node
	 	def insert(self, data):
	 	 	 if self.data:
	 	 	 	 	if data < self.data:
	 	 	 	 	 	 if self.left is None:
	 	 	 	 	 	 	 	self.left = Node(data)
	 	 	 	 	 	 else:
	 	 	 	 	 	 	 	self.left.insert(data)
	 	 	 	 	else 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()
# Inorder traversal
# Left -> Root -> Right
	 	def inorderTraversal(self, root):
	 	 	 res = []
	 	 	 if root:
	 	 	 	 	res = self.inorderTraversal(root.left)
	 	 	 	 	res.append(root.data)
	 	 	 	 	res = res + self.inorderTraversal(root.right)
	 	 	 return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

输出

执行上述代码时，它会产生以下结果 -

[10, 14, 19, 27, 31, 35, 42]

预购遍历

在这种遍历方法中，首先访问根节点，然后访问左侧子树，最后访问右侧子树。

在下面的 python 程序中，我们使用 Node 类为根节点以及左节点和右节点创建占位符。然后，我们创建一个 insert 函数来向树中添加数据。最后，通过创建一个空列表并首先添加根节点，然后添加左节点来实现 Pre-order 遍历逻辑。

最后，添加右侧节点，完成 Pre-order 遍历。请注意，将对每个子树重复此过程，直到遍历完所有节点。

例


class Node:
	 	def __init__(self, data):
	 	 	 self.left = None
	 	 	 self.right = None
	 	 	 self.data = data
# Insert Node
	 	def insert(self, data):
	 	 	 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()
# Preorder traversal
# Root -> Left ->Right
	 	def PreorderTraversal(self, root):
	 	 	 res = []
	 	 	 if root:
	 	 	 	 	res.append(root.data)
	 	 	 	 	res = res + self.PreorderTraversal(root.left)
	 	 	 	 	res = res + self.PreorderTraversal(root.right)
	 	 	 return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

输出

执行上述代码时，它会产生以下结果 -

[27, 14, 10, 19, 35, 31, 42]

后序遍历

在这种遍历方法中，最后访问根节点，因此得名。首先，我们遍历左侧子树，然后遍历右侧子树，最后遍历根节点。

在下面的 python 程序中，我们使用 Node 类为根节点以及左节点和右节点创建占位符。然后，我们创建一个 insert 函数来向树中添加数据。最后，通过创建一个空列表并首先添加左节点，然后添加右节点来实现 Post-order 遍历逻辑。

最后添加根节点或父节点以完成 Post-order 遍历。请注意，将对每个子树重复此过程，直到遍历完所有节点。

例


class Node:
	 	def __init__(self, data):
	 	 	 self.left = None
	 	 	 self.right = None
	 	 	 self.data = data
# Insert Node
	 	def insert(self, data):
	 	 	 if self.data:
	 	 	 	 	if data < self.data:
	 	 	 	 	 	 if self.left is None:
	 	 	 	 	 	 	 	self.left = Node(data)
	 	 	 	 	 	 else:
	 	 	 	 	 	 	 	self.left.insert(data)
	 	 	 	 	else if 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()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

输出

执行上述代码时，它会产生以下结果 -

[10, 19, 14, 31, 42, 35, 27]
打印本页
上一页
下一页