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列表的方式可以方便地構建二叉樹並實現遍歷。