快捷導(dǎo)航

Python樹的重建實現(xiàn)示例

更新時間：2023年11月23日 11:12:59 作者：Echo_Wish

樹的重建是一種從給定的遍歷序列中恢復(fù)原樹結(jié)構(gòu)的算法,本文就來介紹一下Python樹的重建實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下

樹的重建（Tree Reconstruction）是一種從給定的遍歷序列中恢復(fù)原樹結(jié)構(gòu)的算法。在本文中，我們將討論樹的重建問題以及常見的重建算法，包括先序遍歷和中序遍歷序列重建二叉樹，以及層序遍歷序列重建二叉樹。我們將提供Python代碼實現(xiàn)，并詳細(xì)說明每個算法的原理和步驟。

1. 先序遍歷和中序遍歷序列重建二叉樹

給定一個二叉樹的先序遍歷序列和中序遍歷序列，我們可以通過遞歸地進(jìn)行樹的重建。先序遍歷序列的第一個元素為根節(jié)點，在中序遍歷序列中找到該元素，將其分為左子樹和右子樹，然后遞歸對左右子樹進(jìn)行同樣的操作。

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

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    index = inorder.index(root_val)
    
    root.left = build_tree(preorder[1:index + 1], inorder[:index])
    root.right = build_tree(preorder[index + 1:], inorder[index + 1:])
    
    return root

2. 層序遍歷序列重建二叉樹

給定一個二叉樹的層序遍歷序列，我們可以使用隊列來逐層構(gòu)建樹結(jié)構(gòu)。隊列中的每個元素代表一個樹節(jié)點，我們按照層序遍歷的順序依次將節(jié)點加入隊列，并根據(jù)隊列中的順序建立樹的連接關(guān)系。

from collections import deque

def build_tree_level_order(level_order):
    if not level_order:
        return None
    
    root = TreeNode(level_order[0])
    queue = deque([root])
    i = 1
    
    while i < len(level_order):
        current = queue.popleft()
        
        left_val = level_order[i]
        i += 1
        if left_val is not None:
            current.left = TreeNode(left_val)
            queue.append(current.left)
        
        right_val = level_order[i]
        i += 1
        if right_val is not None:
            current.right = TreeNode(right_val)
            queue.append(current.right)
    
    return root

示例

示例1：先序遍歷和中序遍歷序列重建二叉樹

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

root = build_tree(preorder, inorder)

# 驗證重建的樹
def inorder_traversal(root):
    if root is not None:
        inorder_traversal(root.left)
        print(root.val, end=" ")
        inorder_traversal(root.right)

print("Inorder Traversal of Reconstructed Tree:")
inorder_traversal(root)

輸出結(jié)果：

Inorder Traversal of Reconstructed Tree:
9 3 15 20 7

示例2：層序遍歷序列重建二叉樹

level_order = [3, 9, 20, None, None, 15, 7]

root_level_order = build_tree_level_order(level_order)

# 驗證重建的樹
def inorder_traversal_level_order(root):
    if root is not None:
        inorder_traversal_level_order(root.left)
        print(root.val, end=" ")
        inorder_traversal_level_order(root.right)

print("Inorder Traversal of Reconstructed Tree from Level Order:")
inorder_traversal_level_order(root_level_order)

輸出結(jié)果：