Python列表构建二叉树

本文将从以下几个方面详细阐述如何使用Python列表构建二叉树：

一、二叉树的基本概念

二叉树是一种重要的数据结构，其每个节点最多有两个子节点，左子节点和右子节点。左子节点始终比右子节点先遍历，称为优先级比右子节点高。

二、Python列表的构建方法

Python列表是一种可变序列，可以存储元素并通过索引进行访问。使用列表可以轻松地构建二叉树。

def BinaryTree(r):
    return [r, [], []]
 
def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch, [], []])
    return root
 
def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root
 
def getRootVal(root):
    return root[0]
 
def setRootVal(root, newVal):
    root[0] = newVal
 
def getLeftChild(root):
    return root[1]
 
def getRightChild(root):
    return root[2]

三、二叉树的遍历方法

二叉树的遍历即按照某种规则访问二叉树中的所有节点。常用的遍历方法有三种：

• 前序遍历：根节点->左子树->右子树
• 中序遍历：左子树->根节点->右子树
• 后序遍历：左子树->右子树->根节点

下面是具体实现：

def preorder(tree):
    if tree:
        print(getRootVal(tree))
        preorder(getLeftChild(tree))
        preorder(getRightChild(tree))
 
def inorder(tree):
    if tree:
        inorder(getLeftChild(tree))
        print(getRootVal(tree))
        inorder(getRightChild(tree))
 
def postorder(tree):
    if tree:
        postorder(getLeftChild(tree))
        postorder(getRightChild(tree))
        print(getRootVal(tree))

四、示例

下面使用代码创建一个二叉树，并使用前序、中序、后序遍历对其进行遍历：

tree = BinaryTree(1)
 
insertLeft(tree, 2)
insertRight(tree, 3)
insertRight(getLeftChild(tree), 4)
insertLeft(getRightChild(tree), 5)
 
preorder(tree)  # 1 2 4 3 5
inorder(tree)  # 2 4 1 5 3
postorder(tree)  # 4 2 5 3 1

可以看到，使用Python列表的方式可以方便地构建二叉树并实现遍历。