使用Python实现树形排序算法

2023-04-11 00:00:00 python 算法排序

树形排序算法是通过建立一棵树形结构，按照特定的排序规则将每个节点插入到对应位置，从而实现排序的算法。以下是使用Python实现树形排序算法的详细步骤：

定义节点类

首先需要定义一个节点类，用于存储排序对象的值以及左右子树的引用。代码实现如下：

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

定义插入方法

接下来需要定义一个插入方法，将每个节点按照排序规则插入到树中。规则一般是左子树小于父节点，右子树大于父节点。以下是代码实现：

def insert(root, node):
    if root is None:
        root = node
    else:
        if node.val < root.val:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)
        else:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)

定义遍历方法

最后需要定义一个遍历方法，将排序后的结果按照指定顺序输出。以下是针对二叉搜索树（BST）的中序遍历实现：

def inorder_traversal(root, result):
    if root:
        inorder_traversal(root.left, result)
        result.append(root.val)
        inorder_traversal(root.right, result)

至此，树形排序算法的实现完成了。以下是完整代码和范例演示：

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

def insert(root, node):
    if root is None:
        root = node
    else:
        if node.val < root.val:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)
        else:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)

def inorder_traversal(root, result):
    if root:
        inorder_traversal(root.left, result)
        result.append(root.val)
        inorder_traversal(root.right, result)

def tree_sort(arr):
    root = None
    for val in arr:
        insert(root, Node(val))
    result = []
    inorder_traversal(root, result)
    return result

# 范例演示
arr1 = [5, 3, 7, 2, 4, 6, 8]
arr_sorted1 = tree_sort(arr1)
print(arr_sorted1)  # [2, 3, 4, 5, 6, 7, 8]

arr2 = ["p", "i", "d", "a", "n", "c", "o", "d", "e", ".", "c", "o", "m"]
arr_sorted2 = tree_sort(arr2)
print(arr_sorted2)  # [".", "a", "c", "d", "e", "i", "m", "n", "o", "p"]

相关文章