geekdoc-python-zh/docs/py4b/tree-data-structure-in-python.md

Python 中的树形数据结构

原文：https://www.pythonforbeginners.com/data-structures/tree-data-structure-in-python

就特性和数据结构而言，Python 是一种非常丰富的语言。它有很多内置的数据结构，比如 python 字典、列表、元组、集合、frozenset 等等。除此之外，我们还可以使用类创建自己的自定义数据结构。在本文中，我们将学习 Python 中的二叉树数据结构，并尝试使用一个例子来实现它。

Python 中的树型数据结构是什么？

树是一种数据结构，其中数据项使用引用以分层方式连接。每棵树由一个根节点组成，从这个根节点我们可以访问树的每个元素。从根节点开始，每个节点包含零个或多个与其连接的节点作为子节点。一个简单的二叉树可以描述如下图所示。

Tree Data Structure

树数据结构的一部分

树由根节点、叶节点和内部节点组成。每个节点通过一个称为边的引用连接到它的智利。

**根节点:**根节点是一棵树的最顶层节点。它总是创建树时创建的第一个节点，我们可以从根节点开始访问树的每个元素。在上面的例子中，包含元素 50 的节点是根节点。

**父节点:**任何节点的父节点都是引用当前节点的节点。在上面的示例中，50 是 20 和 45 的父级，20 是 11、46 和 15 的父级。同样，45 是 30 和 78 的父代。

**子节点:**父节点的子节点是父节点使用引用指向的节点。在上面的例子中，20 和 45 是 50 的孩子。节点 11、46 和 15 是 20 和 30 的子节点，节点 78 是 45 的子节点。

**边:**父节点通过其连接到子节点的引用称为边。在上面的例子中，连接任意两个节点的每个箭头都是一条边。

**叶节点:**这些是树中没有子节点的节点。在上面的例子中，11、46、15、30 和 78 是叶节点。

**内部节点:**内部节点是指至少有一个子节点的节点。在上面的例子中，50、20 和 45 是内部节点。

什么是二叉树？

二叉树是一种树形数据结构，其中每个节点最多可以有 2 个子节点。这意味着二叉树中的每个节点可以有一个、两个或没有子节点。二叉树中的每个节点都包含数据和对其子节点的引用。这两个孩子根据他们的位置被命名为左孩子和右孩子。二叉树中节点的结构如下图所示。

Node of a Binary Tree

我们可以使用如下的类在 python 中定义如上所示结构的节点。

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None

这里，节点的构造函数将数据值作为输入，创建 BinaryTreeNode 类型的对象，将数据字段初始化为给定的输入，并将对子节点的引用初始化为 None。稍后可以将子节点分配给节点。下图显示了一个二叉树的例子。

Binary Tree Data Structure

我们可以用 python 实现上面的二叉树，如下所示。

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

node1 = BinaryTreeNode(50)
node2 = BinaryTreeNode(20)
node3 = BinaryTreeNode(45)
node4 = BinaryTreeNode(11)
node5 = BinaryTreeNode(15)
node6 = BinaryTreeNode(30)
node7 = BinaryTreeNode(78)

node1.leftChild = node2
node1.rightChild = node3
node2.leftChild = node4
node2.rightChild = node5
node3.leftChild = node6
node3.rightChild = node7

print("Root Node is:")
print(node1.data)

print("left child of the node is:")
print(node1.leftChild.data)

print("right child of the node is:")
print(node1.rightChild.data)

print("Node is:")
print(node2.data)

print("left child of the node is:")
print(node2.leftChild.data)

print("right child of the node is:")
print(node2.rightChild.data)

print("Node is:")
print(node3.data)

print("left child of the node is:")
print(node3.leftChild.data)

print("right child of the node is:")
print(node3.rightChild.data)

print("Node is:")
print(node4.data)

print("left child of the node is:")
print(node4.leftChild)

print("right child of the node is:")
print(node4.rightChild)

print("Node is:")
print(node5.data)

print("left child of the node is:")
print(node5.leftChild)

print("right child of the node is:")
print(node5.rightChild)

print("Node is:")
print(node6.data)

print("left child of the node is:")
print(node6.leftChild)

print("right child of the node is:")
print(node6.rightChild)

print("Node is:")
print(node7.data)

print("left child of the node is:")
print(node7.leftChild)

print("right child of the node is:")
print(node7.rightChild) 

输出:

Root Node is:
50
left child of the node is:
20
right child of the node is:
45
Node is:
20
left child of the node is:
11
right child of the node is:
15
Node is:
45
left child of the node is:
30
right child of the node is:
78
Node is:
11
left child of the node is:
None
right child of the node is:
None
Node is:
15
left child of the node is:
None
right child of the node is:
None
Node is:
30
left child of the node is:
None
right child of the node is:
None
Node is:
78
left child of the node is:
None
right child of the node is:
None

结论

在本文中，我们讨论了 Python 中的树形数据结构和二叉树数据结构。要了解更多关于 Python 中数据结构的知识，可以阅读这篇关于 python 中链表的文章。