Python二叉树用法介绍

╰半橙微兮° 2024-03-24 21:45 15阅读 0赞

二叉树是一种非常重要的数据结构，它在计算机科学中得到了广泛应用，例如在搜索算法、图形渲染和游戏AI等领域。本文将以Python二叉树为中心，从多个角度对其进行详细阐述，包括二叉树定义、二叉树遍历、二叉搜索树、平衡二叉树等内容。

### 一、二叉树定义 ###

二叉树是一种有根树，它满足以下条件：

*  每个节点最多有两个子节点
 *  每个节点只有一个父节点
 *  左子节点是其父节点的左子树，而右子节点是其父节点的右子树

按照这个定义，我们可以使用Python中的类来定义一个简单的二叉树：

class Node:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
    
    class BinaryTree:
        def __init__(self, root):
            self.root = Node(root)

其中，Node类表示二叉树的节点，BinaryTree表示整个树，它的根节点是一个Node类型的节点实例。

### 二、二叉树遍历 ###

二叉树遍历是指按照一定顺序访问二叉树的所有节点。常见的二叉树遍历方式有三种，即先序遍历、中序遍历和后序遍历。

#### 1、先序遍历 ####

先序遍历是指先访问根节点，再访问左子节点和右子节点。使用递归实现先序遍历的代码如下：

def preorder_traversal(self, start, traversal):
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_traversal(start.left, traversal)
            traversal = self.preorder_traversal(start.right, traversal)
        return traversal

#### 2、中序遍历 ####

中序遍历是指先访问左子节点，再访问根节点和右子节点。使用递归实现中序遍历的代码如下：

def inorder_traversal(self, start, traversal):
        if start:
            traversal = self.inorder_traversal(start.left, traversal)
            traversal += (str(start.value) + "-")
            traversal = self.inorder_traversal(start.right, traversal)
        return traversal

#### 3、后序遍历 ####

后序遍历是指先访问左子节点，再访问右子节点和根节点。使用递归实现后序遍历的代码如下：

def postorder_traversal(self, start, traversal):
        if start:
            traversal = self.postorder_traversal(start.left, traversal)
            traversal = self.postorder_traversal(start.right, traversal)
            traversal += (str(start.value) + "-")
        return traversal

### 三、二叉搜索树 ###

二叉搜索树（BST）是一种特殊的二叉树，它满足以下条件：

*  左子节点的值小于其父节点的值
 *  右子节点的值大于其父节点的值
 *  左右子树也都是二叉搜索树

二叉搜索树常用于实现关键字查找和排序等应用。下面是一个简单的Python BST实现：

class BST:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
    
        def insert(self, value):
            if value < self.value:
                if self.left is None:
                    self.left = BST(value)
                else:
                    self.left.insert(value)
            else:
                if self.right is None:
                    self.right = BST(value)
                else:
                    self.right.insert(value)
    
        def search(self, value):
            if value == self.value:
                return True
            elif value < self.value:
                if self.left is None:
                    return False
                else:
                    return self.left.search(value)
            else:
                if self.right is None:
                    return False
                else:
                    return self.right.search(value)

其中，insert方法用于将值添加到BST中，search方法用于查找给定值是否存在于BST中。

### 四、平衡二叉树 ###

平衡二叉树（BST）是一种特殊的二叉树，它满足以下条件：

*  左子树和右子树的高度差不超过1
 *  左右子树也都是平衡二叉树

平衡二叉树能够提高查找、插入和删除操作的效率，常见的平衡二叉树有红黑树、AVL树等。下面是一个简单的Python AVL树实现：

class AVLTree:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
            self.height = 1
    
        def insert(self, value):
            if value < self.value:
                if self.left is None:
                    self.left = AVLTree(value)
                else:
                    self.left.insert(value)
            else:
                if self.right is None:
                    self.right = AVLTree(value)
                else:
                    self.right.insert(value)
    
            self.height = 1 + max(self.get_height(self.left), self.get_height(self.right))
            balance = self.get_balance()
    
            if balance > 1 and value < self.left.value:
                return self.right_rotate()
    
            if balance < -1 and value > self.right.value:
                return self.left_rotate()
    
            if balance > 1 and value > self.left.value:
                self.left = self.left.left_rotate()
                return self.right_rotate()
    
            if balance < -1 and value < self.right.value:
                self.right = self.right.right_rotate()
                return self.left_rotate()
    
            return self
    
        def get_height(self, node):
            if not node:
                return 0
            return node.height
    
        def get_balance(self):
            return self.get_height(self.left) - self.get_height(self.right)
    
        def left_rotate(self):
            new_root = self.right
            self.right = new_root.left
            new_root.left = self
            self.height = 1 + max(self.get_height(self.left), self.get_height(self.right))
            new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
            return new_root
    
        def right_rotate(self):
            new_root = self.left
            self.left = new_root.right
            new_root.right = self
            self.height = 1 + max(self.get_height(self.left), self.get_height(self.right))
            new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
            return new_root

其中，insert方法用于将值添加到AVL树中，get\_height方法用于计算节点高度，get\_balance方法用于计算树的平衡因子，left\_rotate和right\_rotate方法用于实现AVL树的平衡操作。