python中的二叉樹排序用法及說明

更新時(shí)間：2026年03月23日 15:10:03 作者：實(shí)相無相

這篇文章主要介紹了python中的二叉樹排序用法及說明,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

二叉樹排序的詳細(xì)步驟

1、構(gòu)建一棵二叉搜索樹

定義一個(gè)節(jié)點(diǎn)結(jié)構(gòu)，包括節(jié)點(diǎn)值、左孩子指針和右孩子指針。
從待排序數(shù)組中取出最小值作為根節(jié)點(diǎn)。
遞歸構(gòu)建左子樹和右子樹，左子樹包含比根節(jié)點(diǎn)小的元素，右子樹包含比根節(jié)點(diǎn)大的元素。

2、中序遍歷二叉搜索樹

從根節(jié)點(diǎn)開始，按照左-根-右的順序遍歷整棵樹。
在遍歷過程中，將節(jié)點(diǎn)的值依次插入到已排序數(shù)組中。

3、返回已排序數(shù)組

返回已排序數(shù)組作為最終的排序結(jié)果。

Python代碼實(shí)現(xiàn)

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

def binary_tree_sort(arr):
    if not arr:
        return []
    
    # 構(gòu)建二叉搜索樹
    root = TreeNode(min(arr))
    queue = [root]
    i = 0
    while i < len(arr):
        node = queue.pop(0)
        if arr[i] < node.val:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        else:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    
    # 中序遍歷二叉搜索樹，將節(jié)點(diǎn)的值依次插入到已排序數(shù)組中
    res = []
    stack = []
    while queue:
        node = queue.pop(0)
        if stack:
            parent = stack[-1]
            if parent.val > node.val:
                while stack and stack[-1].val > node.val:
                    res.append(stack.pop())
                parent.right = node
                node.left = parent
            else:
                parent.left = node
                node.right = parent
        stack.append(node)
    while stack:
        res.append(stack.pop())
    return res[::-1]  # 返回已排序數(shù)組，由于是中序遍歷，因此需要反轉(zhuǎn)結(jié)果數(shù)組