Python探索之创建二叉树

在Python中，创建二叉树可以通过定义一个树节点类和一个二叉树类来实现。下面分别讲解这两个类的设计。

定义树节点类

树节点类定义了二叉树节点的基本属性和方法，包括节点值、左子节点和右子节点等。具体实现如下：

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

通过构造函数（init）创建节点，并以val参数为节点的值。

定义二叉树类

二叉树类定义了二叉树的基本属性和方法，包括根节点、插入节点和遍历二叉树等。具体实现如下：

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert_node(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_node(self.root, val)

    def _insert_node(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert_node(node.left, val)
        else:
            node.right = self._insert_node(node.right, val)
        return node

    def inorder_traversal(self, node):
        res = []
        if node:
            res = self.inorder_traversal(node.left)
            res.append(node.val)
            res = res + self.inorder_traversal(node.right)
        return res

通过构造函数（init）创建二叉树，并以root参数为根节点。insert_node方法用于插入节点，如果二叉树为空，则根节点为新节点；否则将新节点插入到合适的位置。_insert_node方法是插入节点的内部递归方法。inorder_traversal方法实现了中序遍历二叉树，并返回遍历结果。

示例说明

下面通过两个示例说明如何利用上述类创建二叉树。

示例一

如何创建一棵包含5、2、8、1、4、3的二叉树？

# 创建二叉树
bt = BinaryTree()

bt.insert_node(5)
bt.insert_node(2)
bt.insert_node(8)
bt.insert_node(1)
bt.insert_node(4)
bt.insert_node(3)

# 遍历二叉树
res = bt.inorder_traversal(bt.root)
print(res)

运行结果为：[1, 2, 3, 4, 5, 8]

示例二

如何创建一棵包含'A'、'B'、'C'、'D'、'E'、'F'的二叉树？

# 创建二叉树
bt = BinaryTree()

bt.insert_node('A')
bt.insert_node('B')
bt.insert_node('C')
bt.insert_node('D')
bt.insert_node('E')
bt.insert_node('F')

# 遍历二叉树
res = bt.inorder_traversal(bt.root)
print(res)

运行结果为：['A', 'B', 'C', 'D', 'E', 'F']

通过以上两个示例，我们可以看出，在Python中创建二叉树可以通过定义一个树节点类和一个二叉树类来实现。同时，通过实现二叉树类中的insert_node和遍历方法，可以方便地操作和了解二叉树的结构和特性。