Python 数据结构和算法实用指南（二）（3）

Python 数据结构和算法实用指南（二）（2）https://developer.aliyun.com/article/1507554

基于节点的队列

使用 Python 列表来实现队列是一个很好的开始，可以让我们了解队列的工作原理。我们也可以通过使用指针结构来实现自己的队列数据结构。

可以使用双向链表实现队列，并且在这个数据结构上进行插入和删除操作，时间复杂度为*O(1)*。

node类的定义与我们在讨论双向链表时定义的Node相同。如果双向链表能够实现 FIFO 类型的数据访问，那么它可以被视为队列，其中添加到列表中的第一个元素是要被移除的第一个元素。

队列类

queue类与双向链表list类和Node类非常相似，用于在双向链表中添加节点：

class Node(object):
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev
class Queue: 
    def __init__(self): 
        self.head = None 
        self.tail = None 
        self.count = 0 

在创建queue类实例时，self.head和self.tail指针最初设置为None。为了保持Queue中节点数量的计数，这里还维护了count实例变量，最初设置为0。

入队操作

通过enqueue方法向Queue对象添加元素。元素或数据通过节点添加。enqueue方法的代码与我们在第四章中讨论的双向链表的append操作非常相似，列表和指针结构。

入队操作从传递给它的数据创建一个节点，并将其附加到队列的tail，如果队列为空，则将self.head和self.tail都指向新创建的节点。队列中元素的总数增加了一行self.count += 1。如果队列不为空，则新节点的previous变量设置为列表的tail，并且尾部的下一个指针（或变量）设置为新节点。最后，我们更新尾指针指向新节点。代码如下所示：

def enqueue(self, data): 
        new_node = Node(data, None, None) 
        if self.head is None: 
            self.head = new_node 
            self.tail = self.head 
        else: 
            new_node.prev = self.tail 
            self.tail.next = new_node 
            self.tail = new_node 
        self.count += 1

出队操作

使我们的双向链表作为队列的另一个操作是dequeue方法。这个方法移除队列前面的节点。为了移除self.head指向的第一个元素，使用了一个if语句：

def dequeue(self): 
    current = self.head 
         if self.count == 1: 
             self.count -= 1 
             self.head = None 
             self.tail = None 
         elif self.count > 1: 
             self.head = self.head.next 
             self.head.prev = None 
             self.count -= 1 

current被初始化为指向self.head。如果self.count为1，那么意味着列表中只有一个节点，也就是队列。因此，要移除相关的节点（由self.head指向），self.head和self.tail变量被设置为None。

如果队列有多个节点，那么头指针会移动到self.head之后的下一个节点。

在执行if语句之后，该方法返回被head指向的节点。此外，在这两种情况下，即初始计数为1和大于1时，变量self.count都会减少1。

有了这些方法，我们已经实现了一个队列，很大程度上借鉴了双向链表的思想。

还要记住，将我们的双向链表转换成队列的唯一方法是enqueue和dequeue方法。

队列的应用

队列可以在许多实际的计算机应用程序中用于实现各种功能。例如，可以通过排队打印机要打印的内容，而不是为网络上的每台计算机提供自己的打印机。当打印机准备好打印时，它将选择队列中的一个项目（通常称为作业）进行打印。它将按照不同计算机给出的命令的顺序打印出来。

操作系统也会对要由 CPU 执行的进程进行排队。让我们创建一个应用程序，利用队列来创建一个简单的媒体播放器。

媒体播放器队列

大多数音乐播放器软件允许用户将歌曲添加到播放列表中。点击播放按钮后，主播放列表中的所有歌曲都会依次播放。使用队列可以实现歌曲的顺序播放，因为排队的第一首歌曲是要播放的第一首歌曲。这符合 FIFO 首字母缩写。我们将实现自己的播放列表队列以按 FIFO 方式播放歌曲。

我们的媒体播放器队列只允许添加曲目以及播放队列中的所有曲目。在一个完整的音乐播放器中，线程将被用于改进与队列的交互方式，同时音乐播放器继续用于选择下一首要播放、暂停或停止的歌曲。

track类将模拟音乐曲目：

from random import randint 
class Track: 
    def __init__(self, title=None): 
        self.title = title 
        self.length = randint(5, 10) 

每个曲目都保存了歌曲的标题的引用，以及歌曲的长度。歌曲的长度是在5和10之间的随机数。Python 中的随机模块提供了randint函数，使我们能够生成随机数。该类表示包含音乐的任何 MP3 曲目或文件。曲目的随机长度用于模拟播放歌曲或曲目所需的秒数。

要创建几个曲目并打印出它们的长度，我们需要做以下操作：

track1 = Track("white whistle") 
track2 = Track("butter butter") 
print(track1.length) 
print(track2.length) 

前面代码的输出如下：

6
7

根据生成的两个曲目的随机长度，您的输出可能会有所不同。

现在，让我们创建我们的队列。使用继承，我们只需从queue类继承：

import time 
class MediaPlayerQueue(Queue): 
    def __init__(self): 
        super(MediaPlayerQueue, self).__init__() 

通过调用super来适当初始化队列。这个类本质上是一个队列，它在队列中保存了一些曲目对象。要将曲目添加到队列，需要创建一个add_track方法：

def add_track(self, track): 
        self.enqueue(track) 

该方法将track对象传递给队列super类的enqueue方法。这将实际上使用track对象（作为节点的数据）创建一个Node，并将尾部（如果队列不为空）或头部和尾部（如果队列为空）指向这个新节点。

假设队列中的曲目是按照添加的第一首曲目到最后一首曲目的顺序依次播放（FIFO），那么play函数必须循环遍历队列中的元素：

def play(self): 
        while self.count > 0: 
            current_track_node = self.dequeue() 
            print("Now playing {}".format(current_track_node.data.title)) 
            time.sleep(current_track_node.data.length) 

self.count用于计算何时向我们的队列添加了曲目以及何时曲目已被出队。如果队列不为空，对dequeue方法的调用将返回队列前端的节点（其中包含track对象）。然后，print语句通过节点的data属性访问曲目的标题。为了进一步模拟播放曲目，time.sleep()方法会暂停程序执行，直到曲目的秒数已经过去：

time.sleep(current_track_node.data.length)

媒体播放器队列由节点组成。当一首曲目被添加到队列时，该曲目会隐藏在一个新创建的节点中，并与节点的数据属性相关联。这就解释了为什么我们通过对dequeue的调用返回的节点的数据属性来访问节点的track对象：

您可以看到，我们的node对象不仅仅存储任何数据，而是在这种情况下存储曲目。

让我们来试试我们的音乐播放器：

track1 = Track("white whistle") 
track2 = Track("butter butter") 
track3 = Track("Oh black star") 
track4 = Track("Watch that chicken") 
track5 = Track("Don't go") 

我们使用随机单词创建了五个曲目对象作为标题：

print(track1.length) 
print(track2.length) 
>> 8 >> 9

由于随机长度，输出应该与您在您的机器上得到的不同。

接下来，创建MediaPlayerQueue类的一个实例：

media_player = MediaPlayerQueue()

曲目将被添加，play函数的输出应该按照我们排队的顺序打印出正在播放的曲目：

media_player.add_track(track1) 
media_player.add_track(track2) 
media_player.add_track(track3) 
media_player.add_track(track4) 
media_player.add_track(track5) 
media_player.play() 

前面代码的输出如下：

>>Now playing white whistle
 >>Now playing butter butter
 >>Now playing Oh black star
 >>Now playing Watch that chicken
 >>Now playing Don't go

在程序执行时，可以看到曲目按照它们排队的顺序播放。在播放曲目时，系统还会暂停与曲目长度相等的秒数。

摘要

在这一章中，我们利用了我们对链接节点的知识来创建其他数据结构，即“栈”和“队列”。我们已经看到了这些数据结构如何紧密地模仿现实世界中的栈和队列。我们探讨了具体的实现，以及它们不同的类型。我们随后将应用栈和队列的概念来编写现实生活中的程序。

在下一章中，我们将考虑树。将讨论树的主要操作，以及适用它们数据结构的不同领域。

第六章：度

树是一种分层的数据结构。在其他数据结构（如列表、队列和栈）中，我们已经讨论过的项目是以顺序方式存储的。然而，在树数据结构的情况下，项目之间存在父子关系。树数据结构的顶部称为根节点。这是树中所有其他节点的祖先。

树数据结构非常重要，因为它们在各种重要应用中使用。树被用于许多事情，如解析表达式、搜索、存储数据、操作数据、排序、优先队列等。某些文档类型，如 XML 和 HTML，也可以以树形式表示。我们将在本章中看一些树的用途。

在本章中，我们将涵盖以下主题：

• 树的术语和定义
  
• 二叉树和二叉搜索树
  
• 树的遍历
  
• 三叉搜索树
  

技术要求

本章讨论的所有源代码都在本书的 GitHub 存储库中提供，网址为github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-3.x-Second-Edition/tree/master/Chapter06。

术语

让我们考虑与树数据结构相关的一些术语。

要理解树，我们首先需要了解与其相关的基本概念。树是一种数据结构，其中数据以分层形式组织。以下图表包含一个典型的树，由字符节点 A 到 M 标记：

以下是与树相关的术语列表：

• 节点：在前面的图表中，每个圈起来的字母代表一个节点。节点是实际存储数据的任何数据结构。
  
• 根节点：根节点是树中所有其他节点都连接到的第一个节点。在每棵树中，始终存在一个唯一的根节点。我们示例树中的根节点是节点 A。
  
• 子树：树的子树是具有其节点作为其他树的后代的树。例如，节点 F、K 和 L 形成原始树的子树，其中包含所有节点。
  
• 给定节点的子节点总数称为该节点的度。只包含一个节点的树的度为 0。在前面的图表中，节点 A 的度为 2，节点 B 的度为 3，节点 C 的度为 3，同样，节点 G 的度为 1。
  
• 叶节点：叶节点没有任何子节点，是给定树的终端节点。叶节点的度始终为 0。在前面的图表中，节点 J、E、K、L、H、M 和 I 都是叶节点。
  
• 边：树中任意两个节点之间的连接称为边。给定树中边的总数将最多比树中的总节点数少一个。前面示例树结构中显示了一个边的示例。
  
• 父节点：树中具有进一步子树的节点是该子树的父节点。例如，节点 B 是节点 D、E 和 F 的父节点，节点 F 是节点 K 和 L 的父节点。
  
• 子节点：这是连接到其父节点的节点，是该节点的后代节点。例如，节点 B 和 C 是节点 A 的子节点，而节点 H、G 和 I 是节点 C 的子节点。
  
• 兄弟节点：具有相同父节点的所有节点是兄弟节点。例如，节点 B 和 C 是兄弟节点，同样，节点 D、E 和 F 也是兄弟节点。
  
• 层级：树的根节点被认为是在第 0 级。根节点的子节点被认为在第 1 级，第 1 级节点的子节点被认为在第 2 级，依此类推。例如，根节点在第 0 级，节点 B 和 C 在第 1 级，节点 D、E、F、H、G 和 I 在第 2 级。
  
• 树的高度：树中最长路径上的节点总数是树的高度。例如，在前面的树示例中，树的高度为 4，因为最长路径A-B-D-J或A-C-G-M或A-B-F-K都有 4 个节点。
  
• 深度：节点的深度是从树的根到该节点的边的数量。在前面的树示例中，节点 H 的深度为 2。
  

我们将通过考虑树中的节点并抽象出一个类来开始处理树。

树节点

在线性数据结构中，数据项按顺序依次存储，而非线性数据结构将数据项以非线性顺序存储，其中一个数据项可以连接到多个数据项。线性数据结构中的所有数据项可以在一次遍历中遍历，而在非线性数据结构中这是不可能的。树是非线性数据结构；它们以与数组、列表、栈和队列等其他线性数据结构不同的方式存储数据。

在树数据结构中，节点按照父-子关系排列。树中的节点之间不应该有循环。树结构有节点形成层次结构，没有节点的树称为空树。

首先，我们将讨论一种最重要和特殊的树，即二叉树。二叉树是节点的集合，树中的节点可以有零个、1 个或 2 个子节点。简单的二叉树最多有两个子节点，即左子节点和右子节点。例如，在下面的二叉树示例中，有一个根节点，它有两个子节点（左子节点、右子节点）：

如果二叉树的所有节点都有零个或两个子节点，并且没有一个节点有 1 个子节点，则称树为满二叉树。如果二叉树完全填满，底层可能有一个例外，从左到右填充，则称为完全二叉树。

就像我们之前的实现一样，节点是数据的容器，并且持有对其他节点的引用。在二叉树节点中，这些引用是指左右子节点。让我们看一下下面的 Python 代码，构建一个二叉树node类：

class Node: 
        def __init__(self, data): 
            self.data = data 
            self.right_child = None 
            self.left_child = None 

为了测试这个类，我们首先要创建四个节点——n1、n2、n3和n4：

n1 = Node("root node")  
    n2 = Node("left child node") 
    n3 = Node("right child node") 
    n4 = Node("left grandchild node") 

接下来，我们根据二叉树的属性将节点连接起来。我们让n1成为根节点，n2和n3成为它的子节点。最后，我们将n4作为n2的左子节点。看一下下面的图表，看看我们如何将这些节点连接起来：

接下来的代码片段应该按照前面的图表连接节点：

n1.left_child = n2 
    n1.right_child = n3 
    n2.left_child = n4 

在这里，我们设置了一个非常简单的四个节点的树结构。我们想要在树上执行的第一个重要操作是遍历。为了理解遍历，让我们遍历这棵二叉树的左子树。我们将从根节点开始，打印出节点，并向下移动到下一个左节点。我们一直这样做，直到我们到达左子树的末端，就像这样：

current = n1 
    while current: 
        print(current.data) 
        current = current.left_child 

遍历上述代码块的输出如下：

root node 
left child node 
left grandchild node

树的遍历

访问树中所有节点的方法称为树的遍历。这可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来完成。我们将在接下来的小节中讨论这两种方法。

深度优先遍历

在深度优先遍历中，我们从根开始遍历树，并尽可能深入每个子节点，然后继续遍历到下一个兄弟节点。我们使用递归方法进行树遍历。深度优先遍历有三种形式，即中序、前序和后序。

中序遍历和中缀表示法

中序树遍历的工作方式如下。首先，我们检查当前节点是否为空或空。如果不为空，我们遍历树。在中序树遍历中，我们按照以下步骤进行：

1. 我们开始遍历左子树，并递归调用“中序”函数
   
2. 接下来，我们访问根节点
   
3. 最后，我们遍历右子树，并递归调用“中序”函数
   

因此，在“中序”树遍历中，我们按照（左子树、根、右子树）的顺序访问树中的节点。

让我们考虑一个示例来理解中序树遍历：

在“中序”遍历的示例二叉树中，首先，我们递归访问根节点 A 的左子树。节点 A 的左子树以节点 B 为根，所以我们再次转到节点 B 的左子树，即节点 D。我们递归地转到节点 D 的左子树，以便我们得到根节点 D 的左子树。因此，我们首先访问左子节点，即 G，然后访问根节点 D，然后访问右子节点 H。

接下来，我们访问节点 B，然后访问节点 E。这样，我们已经访问了根节点 A 的左子树。所以下一步，我们访问根节点 A。之后，我们将访问根节点 A 的右子树。在这里，我们转到根节点 C 的左子树，它是空的，所以下一步我们访问节点 C，然后访问节点 C 的右子节点，即节点 F。

因此，这个示例树的中序遍历是“G-D-H-B-E-A-C-F”。

树的递归函数的 Python 实现，以返回树中节点的“中序”列表如下：

def inorder(self, root_node): 
        current = root_node 
        if current is None: 
            return 
        self.inorder(current.left_child) 
        print(current.data) 
        self.inorder(current.right_child) 

我们通过打印访问的节点来访问节点。在这种情况下，我们首先递归调用“中序”函数与current.left_child，然后访问根节点，最后我们再次递归调用“中序”函数与current.right_child。

中缀表示法（也称为逆波兰表示法）是一种常用的表示算术表达式的表示法，其中操作符放置在操作数之间。通常使用这种方式来表示算术表达式，因为这是我们在学校通常学到的方式。例如，操作符被插入（插入）在操作数之间，如3 + 4。必要时，可以使用括号来构建更复杂的表达式，例如(4 + 5) * (5 - 3)。

表达式树是一种特殊的二叉树，可用于表示算术表达式。表达式树的中序遍历产生中缀表示法。例如，考虑以下表达式树：

前面的表达式树的中序遍历给出了中缀表示法，即(5 + 3)。

前序遍历和前缀表示法

前序树遍历的工作方式如下。首先，我们检查当前节点是否为空或空。如果不为空，我们遍历树。前序树遍历的工作方式如下：

1. 我们从根节点开始遍历
   
2. 接下来，我们遍历左子树，并递归调用“前序”函数与左子树
   
3. 接下来，我们遍历右子树，并递归调用“前序”函数与右子树
   

因此，要以前序方式遍历树，我们按照根节点、左子树和右子树节点的顺序访问树。

考虑以下示例树以了解前序遍历：

在上面的二叉树示例中，首先我们访问根节点A。接下来，我们转到根节点A的左子树。节点A的左子树以节点B为根，因此我们访问这个根节点，然后转到根节点B的左子树，即节点D。然后我们访问节点D，并转到根节点D的左子树，然后我们访问左子节点G，它是根节点D的子树。接下来，我们访问根节点D的右子节点，即节点H。接着，我们访问根节点B的右子树的右子节点，即节点E。因此，以这种方式，我们已经访问了根节点A和以根节点A为根的左子树。现在，我们将访问根节点A的右子树。在这里，我们访问根节点C，然后我们转到根节点C的左子树，它为空，所以下一步，我们访问节点C的右子节点，即节点F。

这个示例树的前序遍历将是A-B-D-G-H-E-C-F。

pre-order树遍历的递归函数如下：

def preorder(self, root_node): 
        current = root_node 
        if current is None: 
            return 
        print(current.data) 
        self.preorder(current.left_child) 
        self.preorder(current.right_child) 

前缀表示法通常被称为波兰表示法。在这种表示法中，运算符位于其操作数之前。前缀表示法是 LISP 程序员熟知的。例如，要添加两个数字 3 和 4 的算术表达式将显示为+ 3 4。由于没有运算符优先级的歧义，因此不需要括号：* + 4 5 - 5 3。

让我们考虑另一个例子，即(3 +4) * 5。这也可以用前缀表示法表示为* (+ 3 4) 5。

表达式树的前序遍历将得到算术表达式的前缀表示法。例如，考虑以下表达式树：

上述树的前序遍历将以前缀表示法给出表达式为+- 8 3 3。

后序遍历和后缀表示法

post-order树遍历的工作方式如下。首先，我们检查当前节点是否为空。如果不为空，我们遍历树。post-order树遍历的工作方式如下：

1. 我们开始遍历左子树并递归调用postorder函数
   
2. 接下来，我们遍历右子树并递归调用postorder函数
   
3. 最后，我们访问根节点
   

因此，简而言之，关于post-order树遍历，我们按照左子树、右子树和最后根节点的顺序访问树中的节点。

考虑以下示例树以理解后序树遍历：

在上图中，我们首先递归访问根节点A的左子树。我们到达最后的左子树，也就是根节点 D，然后我们访问它的左节点，即节点G。然后，我们访问右子节点 H，然后我们访问根节点 D。按照相同的规则，我们接下来访问节点B的右子节点，即节点E。然后，我们访问节点B。接着，我们遍历节点A的右子树。在这里，我们首先到达最后的右子树并访问节点F，然后我们访问节点C。最后，我们访问根节点A。

这个示例树的后序遍历将是G-H-D-E-B-F-C-A。

树遍历的post-order方法的实现如下：

def postorder(self, root_node): 
        current = root_node 
        if current is None: 
            return 
        self.postorder(current.left_child) 
        self.postorder(current.right_child) 
        print(current.data)

后缀或逆波兰表示法（RPN）将运算符放在其操作数之后，如3 4 +。与波兰表示法一样，运算符的优先级不会引起混淆，因此永远不需要括号：4 5 + 5 3 - *。

以下表达式树的后序遍历将给出算术表达式的后缀表示法：

上述表达式树的后缀表示法是8 3 -3 +。

广度优先遍历

广度优先遍历从树的根开始，然后访问树的下一级上的每个节点。然后，我们移动到树的下一级，依此类推。这种树遍历方式是广度优先的，因为它在深入树之前通过遍历一个级别上的所有节点来扩展树。

让我们考虑以下示例树，并使用广度优先遍历方法遍历它：

在前面的图表中，我们首先访问level 0的根节点，即值为4的节点。我们通过打印出它的值来访问这个节点。接下来，我们移动到level 1并访问该级别上的所有节点，即值为2和8的节点。最后，我们移动到树的下一级，即level 3，并访问该级别上的所有节点。该级别上的节点是1，3，5和10。

因此，该树的广度优先遍历如下：4，2，8，1，3，5和10。

这种遍历模式是使用队列数据结构实现的。从根节点开始，我们将其推入队列。访问队列前面的节点（出队）并打印或存储以供以后使用。左节点被添加到队列，然后是右节点。由于队列不为空，我们重复这个过程。

该算法的 Python 实现将根节点4入队，出队并访问该节点。接下来，节点2和8入队，因为它们分别是下一级的左节点和右节点。节点2出队以便访问。接下来，它的左节点和右节点，即节点1和3，入队。此时队列前面的节点是8。我们出队并访问节点8，然后将其左节点和右节点入队。这个过程一直持续到队列为空。

广度优先遍历的 Python 实现如下：

from collections import deque 
    class Tree: 
        def breadth_first_traversal(self): 
            list_of_nodes = [] 
            traversal_queue = deque([self.root_node]) 

我们将根节点入队，并在list_of_nodes列表中保留访问过的节点的列表。使用dequeue类来维护队列：

while len(traversal_queue) > 0: 
            node = traversal_queue.popleft() 
            list_of_nodes.append(node.data) 
               if node.left_child: 
                traversal_queue.append(node.left_child) 
            if node.right_child: 
                traversal_queue.append(node.right_child) 
        return list_of_nodes

如果traversal_queue中的元素数量大于零，则执行循环体。队列前面的节点被弹出并附加到list_of_nodes列表中。第一个if语句将左子节点入队，如果提供了左节点则存在。第二个if语句对右子节点执行相同的操作。

list_of_nodes列表在最后一个语句中返回。

二叉树

二叉树是每个节点最多有两个子节点的树。二叉树中的节点以左子树和右子树的形式组织。如果树有一个根 R 和两个子树，即左子树T1和右子树T2，那么它们的根分别称为左继和右继。

以下图表是一个具有五个节点的二叉树的示例：

以下是我们对前面图表的观察：

• 每个节点都保存对右节点和左节点的引用，如果节点不存在
  
• 根节点用5表示
  
• 根节点有两个子树，左子树有一个节点，即值为3的节点，右子树有三个节点，值分别为7，6和9。
  
• 值为3的节点是左继节点，而值为7的节点是右继节点
  

常规的二叉树在树中排列元素方面没有其他规则。它只需满足每个节点最多有两个子节点的条件。

二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树。它是计算机科学应用中最重要和最常用的数据结构之一。二叉搜索树是一棵结构上是二叉树的树，并且非常有效地在其节点中存储数据。它提供非常快速的搜索操作，插入和删除等操作也非常简单和方便。

如果树中任意节点的值大于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值，则称二叉树为二叉搜索树。例如，如果K1、K2和K3是三个节点树中的关键值（如下图所示），则应满足以下条件：

1. K2<=K1的关键值
   
2. 关键值K3>K1
   

以下图表描述了这一点：

让我们考虑另一个例子，以便更好地理解二叉搜索树。考虑以下树：

这是 BST 的一个例子。在这棵树中，左子树中的所有节点都小于或等于该节点的值。同样，该节点的右子树中的所有节点都大于父节点的值。

测试我们的树是否具有 BST 的属性时，我们注意到根节点左子树中的所有节点的值都小于 5。同样，右子树中的所有节点的值都大于 5。这个属性适用于 BST 中的所有节点，没有例外。

考虑另一个二叉树的例子，让我们看看它是否是二叉搜索树。尽管以下图表看起来与前一个图表相似，但它并不符合 BST 的条件，因为节点7大于根节点5；然而，它位于根节点的左侧。节点4位于其父节点7的右子树中，这是不正确的。因此，以下图表不是二叉搜索树：

二叉搜索树实现

让我们开始在 Python 中实现 BST。我们需要跟踪树的根节点，因此我们首先创建一个Tree类，其中包含对根节点的引用：

class Tree: 
        def __init__(self): 
            self.root_node = None 

这就是维护树状态所需的全部内容。让我们在下一节中研究树上的主要操作。

二叉搜索树操作

二叉搜索树上可以执行的操作包括插入、删除、查找最小值、查找最大值、搜索等。我们将在后续小节中讨论它们。

查找最小和最大节点

二叉搜索树的结构使得查找具有最大或最小值的节点非常容易。

要找到树中具有最小值的节点，我们从树的根开始遍历，并每次访问左节点，直到到达树的末端。类似地，我们递归遍历右子树，直到到达末端，以找到树中具有最大值的节点。

例如，考虑以下图表；我们从节点6向下移动到3，然后从节点3移动到1，以找到具有最小值的节点。类似地，要找到树中具有最大值的节点，我们从根向树的右侧移动，然后从节点6移动到节点8，然后从节点8移动到节点10以找到具有最大值的节点。以下是一个 BST 树的例子：

找到最小和最大节点的概念也适用于子树。因此，根节点为8的子树中的最小节点是节点7。同样，该子树中具有最大值的节点是10。

返回最小节点的 Python 实现如下：

def find_min(self): 
        current = self.root_node 
        while current.left_child: 
            current = current.left_child 
        return current 

while循环继续获取左节点并访问它，直到最后一个左节点指向None。这是一个非常简单的方法。

同样，以下是返回最大节点的方法的代码：

def find_max(self): 
        current = self.root_node 
        while current.right_child: 
            current = current.right_child 
        return current 

在 BST 中查找最小值或最大值的运行时间复杂度为 O(h)，其中h是树的高度。

基本上还有两个其他操作，即insert和delete，它们对 BST 非常重要。在对树应用这些操作时，确保我们保持 BST 树的属性是很重要的。

Python 数据结构和算法实用指南（二）（4）https://developer.aliyun.com/article/1507566