Python算法学习[4]—树、二叉树、霍夫曼树&算法实现

叁歲伎倆 2023-09-29 23:01 72阅读 0赞

#### 树、二叉树、霍夫曼树&算法实现 ####

在计算机科学的领域中，树是一种非常重要的数据结构，它被广泛应用于算法和程序设计中。二叉树和霍夫曼树是树的两个变种，也是常用的算法和数据结构。

本文将介绍树、二叉树和霍夫曼树的基本概念和应用，并提供Python代码实现。希望能够帮助读者更好地理解这些数据结构和算法。

1.  树  
    树是由节点和边组成的非线性数据结构，具有以下特点：

每个节点都只有一个父节点（除了根节点）。  
节点可以有任意数量的子节点。  
没有环路（即无向图）。  
树通常用来表示层次关系，在程序设计中，树可以作为搜索、排序、存储以及索引等方面的基础数据结构。

下面是一个简单的Python代码，用于实现树：

class Node:
        def __init__(self, value=None):
            self.value = value
            self.children = []
    
        def add_child(self, value):
            node = Node(value)
            self.children.append(node)
    
        def __repr__(self):
            return str(self.value)

在上述代码中，Node类表示树的节点，其中包含该节点的值和子节点列表。节点可以使用add\_child()方法添加到树中，并且可以通过\_\_repr\_\_()方法进行打印。

1.  二叉树  
    二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以用于搜索、排序、编译器等方面。

接下来是一个简单的Python代码，用于实现二叉树：

class BinaryTreeNode:
        def __init__(self, value=None):
            self.value = value
            self.left = None
            self.right = None
    
        def __repr__(self):
            return str(self.value)
    
    
    class BinaryTree:
        def __init__(self):
            self.root = None
    
        def insert(self, value):
            if self.root is None:
                self.root = BinaryTreeNode(value)
                return
    
            queue = [self.root]
            while queue:
                node = queue.pop(0)
                if not node.left:
                    node.left = BinaryTreeNode(value)
                    return
                elif not node.right:
                    node.right = BinaryTreeNode(value)
                    return
                else:
                    queue.append(node.left)
                    queue.append(node.right)
    
        def inorder_traversal(self, node):
            if not node:
                return
            self.inorder_traversal(node.left)
            print(node.value)
            self.inorder_traversal(node.right)
    
        def preorder_traversal(self, node):
            if not node:
                return
            print(node.value)
            self.preorder_traversal(node.left)
            self.preorder_traversal(node.right)
    
        def postorder_traversal(self, node):
            if not node:
                return
            self.postorder_traversal(node.left)
            self.postorder_traversal(node.right)
            print(node.value)

在上述代码中，BinaryTreeNode类表示二叉树的节点，其中包含该节点的值、左子节点和右子节点。BinaryTree类表示二叉树，其中包含根节点和操作方法，如插入、遍历等等。

1.  霍夫曼树  
    霍夫曼树是一种用于数据压缩的有根树。霍夫曼树的构建过程是将权重从最小的叶子节点开始合并，直到所有节点都合并为根节点为止。该算法可用于压缩数据，因为频繁出现的字符会被赋予较短的编码。

霍夫曼树是一种常用于数据压缩的有根树。该树的构建过程是将权值最小的叶子节点不断合并，直到所有节点都合并为根节点为止。通常情况下，频繁出现的字符会被赋予较短的编码，而不常用的字符则会被赋予较长的编码。

下面是一个简单的Python代码，用于实现霍夫曼树：

import heapq
    
    
    class HuffmanNode:
        def __init__(self, value=None):
            self.value = value
            self.left = None
            self.right = None
    
        def __lt__(self, other):
            return self.value < other.value
    
    
    def build_huffman_tree(data):
        heap = []
    
        for key, value in data.items():
            node = HuffmanNode(value)
            node.left = key
            heapq.heappush(heap, node)
    
        while len(heap) > 1:
            node1 = heapq.heappop(heap)
            node2 = heapq.heappop(heap)
            merged_node = HuffmanNode(node1.value + node2.value)
            merged_node.left = node1
            merged_node.right = node2
            heapq.heappush(heap, merged_node)
    
        return heap[0]
    
    
    def generate_huffman_codes(tree, code, codes):
        if tree is None:
            return
    
        if tree.left is None and tree.right is None:
            codes[tree.left] = code
    
        generate_huffman_codes(tree.left, code + "0", codes)
        generate_huffman_codes(tree.right, code + "1", codes)
    
    
    if __name__ == "__main__":
        data = {
        'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
        huffman_tree = build_huffman_tree(data)
        huffman_codes = {
        }
        generate_huffman_codes(huffman_tree, "", huffman_codes)
        print("Huffman Codes:", huffman_codes)

在上述代码中，我们首先定义一个HuffmanNode类表示霍夫曼树的节点。为了能够通过优先队列构建霍夫曼树，我们重载了比较运算符\_\_lt\_\_()。

接下来，我们使用build\_huffman\_tree()函数来构建霍夫曼树。该函数接收一个字典类型的数据，其中键表示字符，值表示字符出现的频率。该函数首先将每个字符和对应的频率转换为一个HuffmanNode对象，并将它们插入堆中。然后不断从堆中弹出两个权值最小的节点，将它们合并成一个新的节点，并将该节点再次插入堆中，直到只剩一个节点为止。

最后，我们使用generate\_huffman\_codes()函数来生成霍夫曼编码。该函数接收三个参数：当前节点、目前已生成的编码、以及保存编码的字典。如果当前节点是叶子节点，则将它的编码加入到字典中。否则，递归调用该函数分别生成左子树和右子树的编码。

在主函数中，我们使用一个示例字典来构建霍夫曼树，并生成对应的编码。最后，我们打印生成的编码。