Python 二叉树

一、什么是二叉树

二叉树是一种数据结构，它由节点组成，每个节点最多有两个子节点。节点有一个称为“根”的特殊节点，它是整个树的起点。每个节点都有一个有向边连接到其子节点。如果没有子节点，则称该节点为“叶子节点”。根据节点的排列方式，二叉树可以分为以下几种类型：

满二叉树：每个节点都有两个子节点，除了叶子节点外
完全二叉树：不一定每个节点都有两个子节点，但是任何缺失子节点的节点都必须在右边的子树中


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

二、二叉树的遍历

二叉树的遍历是指按照一定方法遍历二叉树节点的过程。常用的遍历方法有前序遍历、中序遍历和后序遍历。

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点


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

    def preorderTraversal(self, root):
        res = []
        if root:
            res.append(root.val)
            res += self.preorderTraversal(root.left)
            res += self.preorderTraversal(root.right)
        return res

    def inorderTraversal(self, root):
        res = []
        if root:
            res += self.inorderTraversal(root.left)
            res.append(root.val)
            res += self.inorderTraversal(root.right)
        return res

    def postorderTraversal(self, root):
        res = []
        if root:
            res += self.postorderTraversal(root.left)
            res += self.postorderTraversal(root.right)
            res.append(root.val)
        return res

三、二叉树的应用

1.表达式树

表达式树是一种二叉树，其中每个叶节点都是一个操作数，而其他节点都是操作符。通过遍历表达式树，可以实现对表达式的计算。


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

    def evaluate(self):
        if self.val.isdigit():
            return int(self.val)
        else:
            left_val = self.left.evaluate()
            right_val = self.right.evaluate()
            if self.val == '+':
                return left_val + right_val
            elif self.val == '-':
                return left_val - right_val
            elif self.val == '*':
                return left_val * right_val
            else:
                return left_val / right_val

2.哈夫曼树

哈夫曼树是一种特殊的树，其中有权重的叶子节点表示字符，并且具有最小的路径权重和。哈夫曼树经常用于编码和解码数据。


class HuffmanTree:
    def __init__(self, freq, left=None, right=None):
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq

    def isLeaf(self):
        return self.left is None and self.right is None

    def buildHuffmanTree(freq_map):
        heap = []
        for char, freq in freq_map.items():
            heapq.heappush(heap, (freq, HuffmanTree(freq, char)))
        while len(heap) > 1:
            freq1, tree1 = heapq.heappop(heap)
            freq2, tree2 = heapq.heappop(heap)
            heapq.heappush(heap, (freq1 + freq2, HuffmanTree(freq1 + freq2, tree1, tree2)))
        return heap[0][1]