Python程序 实现二叉树数据结构

在Python中实现二叉树数据结构十分简单，我们只需要用Node类来表示二叉树中的一个节点，并在其中添加左右子节点，即可实现二叉树数据结构。

定义Node类

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

在Node类中，我们定义了三个成员变量：val、left、right。其中，val表示节点中的值，left和right表示左右子节点的引用。初始化时，我们用None占位。

实现二叉树

实现二叉树，我们只需要用Node类定义节点，然后将节点相互连接即可。例如，下面我们实现了一棵二叉树：

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

这棵二叉树的结构如下：

      1
     / \
    2   3
   / \
  4   5

我们可以通过遍历二叉树的方式，依次输出其中的每个节点。例如，下面我们实现了一个中序遍历函数：

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

在这个函数中，我们使用了递归的方式，依次遍历左子树、输出根节点、遍历右子树。使用上面定义的二叉树时，我们可以这样使用：

inorder_traversal(root)

输出结果为：

4
2
5
1
3

同样，我们也可以实现前序和后序遍历。

完整代码实现

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inorder_traversal(root)

结论

Python实现二叉树数据结构十分简单。我们只需要用Node类来表示一个节点，并通过引用来连接节点之间的关系，即可实现一个二叉树。通过遍历二叉树的方式，我们可以输出其中的每个节点。