文章目录

一、树的简介1. 树的定义2. 相关概念 二、树的ADT三、树的实现准备1. 树的基本分类2. 树的抽象基类 四、树的概念拾遗1. 深度2. 高度 五、二叉树的简介1. 定义2. ADT3. 抽象基类 六、二叉树的实现1. 基于链表实现二叉树结点对象描述`_Node` 结点位置描述`Position` 非修改类操作`_pos2node(p)``_node2pos(node)``__init__()``__len__()``root()``parent(p)``left(p)``right(p)``num_children(p)` 修改类操作`_add_root(e)``_add_left(p, e)``_add_right(p, e)``_replace(p, e)``_delete(p)``_attach(p, t1, t2)` 2. 链表二叉树各方法时间复杂度 七、一般树的实现

在之前的文章中，不论是列表还是链表，抑或是基于二者实现的栈、队列等数据结构都是线性结构，即元素之间只有“前”和“后”的关系，从本文开始我们将学习最重要的一种非线性数据结构之一——树，这类数据结构可表达更加丰富的对象间关系，从而可以更好地对更多的现实场景进行抽象。

一、树的简介

现实中用树形结构描述信息的案例很多，例如下图所示的《红楼梦》中贾家的家谱图：

1. 树的定义

正式地，当某一个由保存了对象元素的结点所组成的集合满足下列两条性质时，我们将该集合抽象定义为数据结构树T：

如果T非空，则其有一个被称为根结点的特殊结点，该结点没有父结点；T中每一个不是根结点的结点v都有且仅有唯一的一个父结点w。

例如，就上述的《红楼梦》中贾家家谱图来看：

贾家是根结点，该结点没有父节点；除贾家外的其他所有结点都有且仅有一个父结点（这也很好理解，因为所有人都只有一个父亲）。

实际上，根据上述定义，树T还有如下递归特性：树T要么空，要么包含根结点r以及一系列根结点为结点r的子结点的子树（子树可能为空）。

2. 相关概念

除了上述关于树以及根结点的定义外，还有以下将用于后续讨论的重要概念：

兄弟结点：具有同一个父结点的结点之间互为兄弟结点，例如：贾演和贾源、贾珠和贾宝玉；外部结点：没有子结点的结点，例如：贾环；内部结点：有一个或多个子结点的结点；叶子结点：外部结点又称叶子结点；祖先结点：对于两个结点u和v，如果u = v或者u是v的父结点的祖先结点，则结点u是v的祖先结点，例如：从贾宝玉自身到贾政、贾代善、贾源直到贾家都是贾宝玉结点的祖先结点；子孙结点：与祖先结点的概念相对；边：对于一对结点(u, v)，如果u是v的父结点或v是u的父结点，则称(u, v)是树T的一条边，例如：(贾敬, 贾珍)就是一条边；路径：路径是这样一个结点序列，即序列中任意相邻的两个结点都可形成一条边，例如：(贾家, 贾源, 贾代善, 贾政, 贾宝玉)就是一条路径；有序树：如果树的每一个结点的子结点之间都存在有意义线性关系，则这样的树被称为有序树，例如：上述贾家的家谱图就是一个有序树，因为每一父结点的子结点都按照人员年龄大小从左到右排列。

二、树的ADT

本文仍然采用文章【数据结构Python描述】位置列表简介与Python版手工实现中描述位置的方式来抽象地表示树中每一个结点：即每个对象元素都保存在每一个抽象位置处，树的结点关系由结点间的位置来表示。则树ADT至少支持以下非修改类方法：

需要注意的是：

类似文章【数据结构Python描述】位置列表简介与Python版手工实现中使用_Position的实例描述某结点在位置列表中的位置所遇到的情况，如果一个位置实例描述树T中某一个位置的行为不合法，则应该抛出ValueError异常；位置p对象仅支持一个方法element()，即p.element()返回该位置代表的结点处的对象元素；如果树T为有序的，则T.children(p)按照位置p处所有子结点内在顺序进行迭代返回。

三、树的实现准备

对于树的ADT本文不会像之前的数据结构文章一样直接对其进行具体实现，下面指出之前的论述方法所存在的部分问题：

首先，下列三篇文章分别使用列表、单向线性链表以及单向循环链表作为对象元素存储容器实现了队列这一数据结构：

【数据结构Python描述】队列和双端队列简介及其高效率版本Python实现【数据结构Python描述】单向线性链表简介、Python实现及应用【数据结构Python描述】单向循环链表简介、Python语言实现及应用

问题在于，分析上述三种实现方式的代码后可知：

不同实现的ADT一致但彼此间未建立关联，因为这些具体实现本身就是以队列的ADT为蓝本；不同实现中部分方法的实现完全一样（如：is_empty()、__len__()等）。

针对上述两个问题，很自然地需要考虑：

是否可以将针对同一数据结构ADT的不同实现关联起来；是否可以降低不同实现间的代码重复度。

实际上，Python中的抽象基类就可用于解决上述两个问题，即使用抽象基类：

表达某一数据结构的ADT；实现不同实现中的共有和实用方法。

1. 树的基本分类

对于树定义抽象基类的另一个考虑是，截至目前本文讨论的都是一般性的树，但实际使用最多的是二叉树BinaryTree，即所有结点的子结点数量不大于2个的一类树，且根据使用列表还是链表实现，又可以分为ArrayBinaryTree和LinkedBinaryTree，而上述给出的非修改类方法组成的ADT适用于所有类型的树。

因此将上述ADT封装在一个抽象基类Tree中，实现BinaryTree时只需继承Tree即可，而实现ArrayBinaryTree和LinkedBinaryTree只需继承BinaryTree并实现抽象方法即可。

2. 树的抽象基类

基于Python中的继承、抽象基类和接口定义抽象基类的方法，下面给出一般树的抽象基类完整定义。

from abc import ABCMeta, abstractmethodclass Tree(metaclass=ABCMeta):"""表示一般树的抽象基类"""class Position(metaclass=ABCMeta):"""嵌套定义的位置类，其实例对象用于描述结点在树中的位置"""@abstractmethoddef element(self):"""用于返回某位置处的对象元素:return: 结点处的对象元素"""@abstractmethoddef __eq__(self, other):"""使用'=='判断两个Position实例是否代表同一个位置:param other: 另一个Position的实例:return: Boolean"""@abstractmethoddef __ne__(self, other):"""使用'!='判断两个Position实例是否不代表同一个位置:param other: 另一个Position的实例:return: Boolean"""@abstractmethoddef __len__(self):"""返回树中所有结点数量:return: 结点数量"""@abstractmethoddef root(self):"""返回代表数根结点的位置对象，如树为空则返回None"""@abstractmethoddef parent(self, p):"""返回位置p处结点的父结点所在位置，如p处为根结点则返回None:param p: 某结点所在位置:return: 某结点的父结点所在位置"""@abstractmethoddef num_children(self, p):"""返回位置p处结点的子结点数目:param p: 结点位置:return: 结点的子结点数目"""@abstractmethoddef children(self, p):"""生成位置p处结点的所有子结点的一个迭代:param p: 结点位置:return: 子结点位置"""@abstractmethoddef __iter__(self):"""生成一个树的结点元素的迭代"""@abstractmethoddef positions(self):"""生成一个树的结点位置的迭代"""def is_root(self, p):"""如果位置p处的结点为根结点则返回True"""return self.root() == pdef is_leaf(self, p):"""如果位置p处的结点无任何子结点则返回True"""return self.num_children(p) == 0def is_empty(self):"""如果树为空，则返回True"""return len(self) == 0

分析上述代码可知：

用于描述位置的Position类以嵌套的方式定义在了Tree的内部，且其中的方法也均定义为了抽象方法；对上述树的所有ADT方法，多数都定义为了抽象方法，而is_root()、is_leaf()、is_empty()这几个方法虽然定义为普通方法，但其实现依赖于其他抽象方法，实际上这体现了算法设计中常用的一种设计模式——模板方法设计模式。

四、树的概念拾遗

除前面提及的和树相关定义，树以及其结点还有两个重要概念：深度和高度。

1. 深度

普通定义：如果p为树T的某结点位置，则对于位置p处的结点，其除自身外的所有祖先结点数量称为位置p处结点的高度。递归定义： 如果位置p处为根结点，则该位置处的结点深度为0；如果位置p处不是根结点，则该位置处的结点深度等于其父结点深度加1。

基于上述树的递归定义，可以在上述Tree中添加一个递归方法depth()以通过给定树T的位置p来计算该位置的结点高度：

def depth(self, p):"""返回位置p处结点的高度:param p: 结点位置:return: 结点高度"""if self.is_root(p):return 0else:return 1 + self.depth(self.parent(p))

上述depth()方法的时间复杂度为 O ( d p + 1 ) O(d_p+1) O(dp​+1)，其中 d p d_p dp​表示位置p处结点的深度，因为该算法的递归次数和当前位置处结点的祖先结点（结点自身为自身的祖先结点）数量相同，而每次递归均使用定长时间。

实际上，如果树T中结点总数为 n n n，则上述depth()方法的最坏时间复杂度为 O ( n ) O(n) O(n)，此时树T的所有结点仅形成一条分支。虽然depth()方法的运行时间与树T的结点个数 n n n呈函数关系，但通常我们使用结点深度 d p d_p dp​作为函数参数：

一方面这更直观；另一方面 d p d_p dp​通常小于 n n n。

2. 高度

递归定义：仿照结点深度的递归定义，结点高度的递归定义为：

如果位置p处为叶子结点，则该结点高度为0；如果位置p处不为叶子结点，则该结点高度为其所有子结点中最大的高度加1。

一般也将树T的根结点高度称为树的高度，而一个非空树T的高度等于其所有叶子结点深度中的最大值。

下面使用结点高度的递归定义在Tree中给出一个最坏时间复杂度为 O ( n ) O(n) O(n)（其中 n n n为树T结点数量）的结点高度计算方法_height()：

def _height(self, p):"""返回位置p处结点的高度:param p: 结点位置:return: 结点高度"""if self.is_leaf(p):return 0else:return 1 + max(self._height(child) for child in self.children(p))

下面分析为什么说_height()的最坏时间复杂度为 O ( n ) O(n) O(n)：

虽然我们至此还未实现T.children()方法，但后续可知对该方法有最坏时间复杂度为 O ( c p + 1 ) O(c_p+1) O(cp​+1)的实现，其中 c p c_p cp​为位置p处结点的子结点数量，基于此下面分析为什么说_height()的最坏时间复杂度为 O ( n ) O(n) O(n)：

上述_height()实现中每一个位置处非递归调用的时间复杂度为 O ( c p + 1 ) O(c_p+1) O(cp​+1)；当位置p代表根结点时，上述_height()方法达到算法的最坏情况。

因此，此时所有位置处的时间复杂度和为 O ( ∑ p ( c p + 1 ) ) = O ( ∑ p c p + n ) O(\sum_p(c_p+1))=O(\sum_p{c_p}+n) O(∑p​(cp​+1))=O(∑p​cp​+n)，而如果 c p c_p cp​代表任意位置p处的子结点数量，则 ∑ p c p = n − 1 \sum_p{c_p}=n-1 ∑p​cp​=n−1，因此上述_height()实现的最坏时间复杂度为 O ( n ) O(n) O(n)。

上述_height()方法可以使用结点位置p计算其高度，而实际中使用最多的是计算整个树T的高度，为了避免每次都显式指定p为根结点位置，可以如下所示重新定义一个height()方法，在其中调用非公有方法_height()：

def _height(self, p):"""返回位置p处结点的高度:param p: 结点位置:return: 结点高度"""if self.is_leaf(p):return 0else:return 1 + max(self._height(child) for child in self.children(p))def height(self, p=None):"""返回位置p处结点的高度，默认返回根结点高度:param p: 结点位置:return: 结点高度"""if p is None:p = self.root()return self._height(p)

五、二叉树的简介

1. 定义

基本定义：二叉树是每个结点至多有两个子结点的有序树。

基于上述定义一般将一个结点的两个子结点分别称为左子结点和右子结点，左和右的区分以两个结点的自然顺序划分，如：本文开头红楼梦家谱图（需要注意这不是二叉树，但不妨碍以此为例）中，贾珍和贾惜春作为贾敬的子结点，如果其中所有人都之多有两个子女，则因为贾珍年长于贾惜春，因此贾珍为左子结点，贾惜春为右子结点。

除此之外，关于二叉树还有如下几个概念：

（左）右子树：以（左）右子结点为根结点的子树；满二叉树：每一个结点都有0个或两个子结点的二叉树。

基于上述概念，还可以给出二叉树的递归定义：

递归定义：一个树T为空或其满足下列要求时该树为二叉树：

包含一个根结点r；根结点r有一个左子树（可能为空），该子树为二叉树；根结点r有一个右子树（可能为空），该子树也为二叉树。

实际上，满二叉树的案例有很多，如下面的有效数学表达式( ( ( ( 3 + 1 ) × 3 ) / ( ( 9 − 5 ) + 2 ) ) − ( ( 3 × ( 7 − 4 ) ) + 6 ) ) ((((3 + 1) × 3)/((9 − 5) + 2)) − ((3 × (7 − 4)) + 6)) ((((3+1)×3)/((9−5)+2))−((3×(7−4))+6))：该二叉树的叶子结点均为变量或常量，内部结点均为+、-、×和/等运算符号，且：

如果一个结点为叶子结点，则其值为变量或常量本身；如果一个结点为内部结点，则其值为对所有子结点计算后得出的值。

2. ADT

由于二叉树是一般树的特殊情况，故其ADT除了具有上述一般树的ADT所具有的非修改类操作外，还额外支持以下几个非修改类操作：

T.left(p)：返回位置p处结点的左子结点位置，当位置p处结点无左子结点时返回None；T.right(p)：返回位置p处结点的右子结点位置，当位置p处结点无右子结点时返回None；T.sibling(p)：返回位置p处结点的兄弟结点，当位置p处结点无兄弟结点时返回None。

3. 抽象基类

上述我们将表示一般树的类Tree定义为了抽象基类，由于具体实现二叉树既可基于链表也可基于列表，因此为了确保对同一套二叉树ADT的不同实现之间建立关联，并且提高代码的复用程度，此处仍将描述二叉树的类BinaryTree定义为抽象基类。

需要注意的是，抽象基类之间也可以通过继承来进一步提高代码的复用程度，故这里在定义二叉树的抽象基类BinaryTree的时候让其继承描述一般树的抽象基类Tree，这也从侧面反应了定义抽象基类的好处。

class BinaryTree(Tree, metaclass=ABCMeta):"""表示二叉树的抽象基类"""@abstractmethoddef left(self, p):"""返回位置p处结点的左子结点，如该处结点无左子结点则返回None:param p: 结点位置:return: 结点位置或None"""@abstractmethoddef right(self, p):"""返回位置p处结点的右子结点，如该处结点无右子结点则返回None:param p: 结点位置:return: 结点位置或None"""def sibling(self, p):"""返回位置p处结点的兄弟结点，如该处结点无兄弟结点则返回None:param p: 结点位置:return: 结点位置或None"""parent = self.parent(p)if parent is None: # 如果位置p处为根结点，则该位置处的结点无兄弟结点return Noneelse:if p == self.left(parent): # 如果位置p处是左结点，则返回右结点位置（可能无）return self.right(parent)else: # 如果位置p处是右结点，则返回左结点位置（可能无）return self.left(parent)def children(self, p):"""生成位置p处结点的子结点迭代:param p: 结点位置:return: 结点位置迭代"""if self.left(p) is not None:yield self.left(p)if self.right(p) is not None:yield self.right(p)

关于上述代码，需要注意的几点是：

BinaryTree也从Tree中继承了在其中嵌套定义的类Position，此外还定义了left()和right()两个需要其具体子类（和抽象父类相对的概念）实现的抽象方法；BinaryTree还基于left()和right()两个方法对sibling()方法进行了具体实现（实际上这是模板方法设计模式的体现）；BinaryTree还具体实现了继承自Tree中的抽象方法children()，这是基于二叉树定义中对一个结点的子结点数量限制以及left()和right()两个方法得到的，这又从侧面反应了在抽象基类Tree中定义一般树的共有和实用方法的优势：可能会有四叉树QuadTree，其可以继承children()方法之后给出不同的具体实现。

六、二叉树的实现

截至目前，本文定义的Tree和BinaryTree都是抽象基类，即无法对其进行实例化来使用，其中一个最主要原因我们还未定义树的内部应该如何表达一个结点，鉴于二叉树形式的简单性，这里先给出对二叉树的具体类实现代码。

1. 基于链表实现二叉树

树中的结点可以有多种表达方式，其中自然地一种方式是使用链式结构，下面通过继承BinaryTree实现一个描述二叉树的具体类LinkedBinaryTree。

在实现LinkedBinaryTree从Tree以及BinaryTree两个抽象基类中继承的抽象方法之前，需要先定义描述树的结点以及结点位置的类_Node以及Position：

结点对象描述

仿照链表中的结点定义并结合二叉树的定义，按照下图定义一个二叉树的结点，即一个结点对象至少有四个属性：

element：保存指向对象元素的引用；left：保存指向左子结点的引用；right：保存指向右子结点的引用；parent：保存指向父结点的引用。

_Node

基于上述讨论，在具体二叉树类LinkedBinaryTree中嵌套定义表示结点的类_Node：

class _Node: # 用于表示结点的类__slots__ = 'element', 'parent', 'left', 'right'def __init__(self, element, parent=None, left=None, right=None):self.element = elementself.parent = parentself.left = leftself.right = right

此处我们将描述结点的类定义为受保护的，原因是我们希望为LinkedBinaryTree的用户提供更加简单的使用方式，即直接通过位置来操作树。

结点位置描述

仿照位置列表中对于结点位置的抽象描述，类似地，下面在LinkedBinaryTree中嵌套定义了描述一个树的结点所在位置的类Position，该类直接继承了抽象基类Tree中嵌套定义的抽象基类Position并实现了其中定义的所有抽象方法。

Position

下面实现的Position注意事项和位置列表中对于结点位置的抽象描述所遵循的原则一致：

class Position(BinaryTree.Position):"""用于描述结点位置的类"""def __init__(self, container, node):self._container = containerself._node = nodedef element(self):"""返回保存在该位置处的对象元素"""return self._node.elementdef __eq__(self, other):"""当self和other表示同一个结点的位置时，返回True"""return type(self) is type(other) and other._node is self._nodedef __ne__(self, other):"""当self和other表示不同结点的位置时返回True"""return not (self == other)

非修改类操作

上面已经分别实现了表示二叉树结点以及结点位置的类，下面正式实现二叉树继承自抽象基类的抽象方法之前，还需要实现两个特殊的实用方法_pos2node(p)以及_node2pos(node)。

由于LinkedBinaryTree提供用户通过位置的方式来操作树，但树的底层仍然使用结点来组织数据，因此上述两个方法主要用于实现结点对象和位置对象之间的转换，并实现在转换之前进行必要的数据验证以提高数据结构的鲁棒性。

_pos2node(p)

由于描述结点位置的对象由数据结构的用户使用，因此为了提高数据结构的鲁棒性，需要在底层对该位置转换为结点对象之前做有效性检查：

确保p为描述该二叉树对象元素位置的Position类的实例；确保在p描述的位置处，其对象元素属于当前二叉树；确保在p描述的位置处，其对象元素没有被删除。

在确保描述结点位置的对象有效性，返回该位置对象所代表的结点对象：

def _pos2node(self, p: Position):"""如果位置p有效，返回该位置处的结点引用"""if not isinstance(p, self.Position):raise TypeError('位置p:', p, '必须为准确的Position类型！')if p._container is not self:raise ValueError('位置p', p, '不属于当前位置列表！')if p._node.parent is None and p._node.element is None:raise ValueError('位置p', p, '已失效！')return p._node

_node2pos(node)

由于对底层结点的操作由数据结构的实现者进行，因此实现者有义务确保给定的结点对象是有效的，因此无需像上述方法一样做复杂的情况考虑：

def _node2pos(self, node):"""根据给定结点，创建并返回位置引用，当结点为None时返回None"""return self.Position(self, node) if node is not None else None

__init__()

对于链表的实现，原则上只要给定头结点的引用就可以头结点通过遍历找到其中所有结点，事实上为了能够有效地得到链表的结点个数，我们还定义了一个用于记录链表结点个数的实例属性。

类似地，由于这里基于链式存储结构实现二叉树，所以仿照链表的实现我们也定义两个实例属性就可以描述一个二叉树实例，即：

一个实例属性root用于指向二叉树的根结点；一个实例属性size用于保存当前二叉树的结点个数。

基于上述讨论，可得LinkedBinaryTree的初始化方法实现如下：

def __init__(self):"""创建一个空的二叉树"""self._root = Noneself._size = 0

实际上，采用上述描述二叉树的方式，一个具有五个结点的二叉树可以通过下图来表示：

__len__()

该方法的实现只要返回二叉树实例对象的_size属性即可：

def __len__(self):"""返回二叉树实例中结点个数"""return self._size

root()

该方法原为定义在抽象基类Tree中的抽象方法，这里对其进行具体实现，具体方法是使用实用方法_node2pos(node)：

def root(self):"""返回代表二叉树根结点位置的对象，当二叉树为空时返回None"""return self._node2pos(self._root)

需要注意的是由于当_root属性为None时（即此时二叉树为空）方法root()也返回None这一点由_node2pos()方法保证。

parent(p)

如前所述，由于数据结构底层仍使用结点组织数据对象，因此需要：

先将p引用的位置对象转换为结点对象；然后获得上述结点的父结点后将其转换为位置对象即可。

def parent(self, p):"""返回代表位置p处结点的父结点的位置对象"""node = self._pos2node(p)return self._node2pos(node.parent)

left(p)

该方法实现类似parent()：

def left(self, p):"""返回代表位置p处结点的左子结点的位置对象，如无左子结点则返回None"""node = self._pos2node(p)return self._node2pos(node.left)

right(p)

该方法实现类似parent()：

def right(self, p):"""返回代表位置p处结点的右子结点的位置对象，如无右子结点则返回None"""node = self._pos2node(p)return self._node2pos(node.right)

num_children(p)

由于二叉树任何结点都至多有两个子结点——左子结点、右子结点，因此实现该方法只要判断该位置处的结点的左右子结点情况即可：

def num_children(self, p):"""返回位置p处结点的子结点数量"""node = self._pos2node(p)count = 0if node.left is not None:count += 1if node.right is not None:count += 1return count

至此，我们实现了二叉树中除__iter__()和positions()以外的绝大部分非修改类操作，由于树形结构的复杂性，这两个方法实现需要专门的知识，因此其实现留待后续独立的博客进行讲解。

修改类操作

截至目前，我们已经实现了绝大多数二叉树实例对象的非修改类操作，然而由LinkedBinaryTree的初始化方法可知，此时创建的二叉树实例为空树（实际上目前我们仍然不能对LinkedBinaryTree进行实例化操作，因为仍存在继承自抽象基类的抽象方法__iter__()和positions()未得到实现），而我们至今还未提供任何修改类方法（增删结点等）。

实际上，我们至此才考虑定义并实现二叉树的修改类方法，原因之一是：如果这些方法定义在抽象基类Tree或BinaryTree中，则这些公有的抽象方法必定需要被所有的具体子类实现，但是在有些情况下鉴于树形结构的复杂性，我们并不想为数据结构的使用这暴露这些操作，以避免产生不必要的误操作。

鉴于以上考虑，并结合修改二叉树实例的具体需要，定义下面若干个受保护的修改类操作：

T._add_root(e)：为空二叉树创建一个根结点，并让根结点的element域引用对象元素e，最后返回代表该结点的位置对象，如果调用此方法之前二叉树非空则抛出异常。T._add_left(p, e)：创建一个新结点并让其element域引用对象元素e，并将该结点连接为位置p代表的结点的左子结点；如果位置p代表的结点已有左子结点，则抛出异常。T._add_right(p, e)：创建一个新结点并让其element域引用对象元素e，并将该结点连接为位置p代表的结点的右子结点；如果位置p代表的结点已有右子结点，则抛出异常。T._replace(p, e)：将位置p处结点的element域改为引用对象元素e，并返回其原先引用的对象元素；T._delete(p)：删除位置p处结点并返回结点的element域引用的对象元素，如果该结点有且仅有一个子结点，则使用子结点代替其位置，如果该结点有两个子结点，则抛出异常；T._attach(p, t1, t2)：给定三个同类型的二叉树T、t1和t2以及代表T某叶子结点的位置p，通过将t1和t2的根结点分别连接为位置p处叶子结点的左右子结点，实现树的链接。

下面给出上述方法的具体实现：

_add_root(e)

该方法可根据功能要求即可实现：

def _add_root(self, e):"""如果二叉树为空则将元素e封装为结点后置为根结点并返回结点位置，否则抛出ValueError异常"""if self._root is not None:raise ValueError('此二叉树非空！')self._size = 1self._root = self._Node(e)return self._node2pos(self._root)

_add_left(p, e)

该方法可通过以下步骤实现：

首先得到位置p处的结点；然后判断该结点是否已经有左子结点；如果位置p处结点无左子结点，则建立元素e经封装后得到的结点和位置p处的结点。

def _add_left(self, p, e):"""为位置p处的结点创建保存元素e的左子结点并返回结点位置，如果位置p处结点已有左子结点则抛出ValueError异常"""node = self._pos2node(p)if node.left is not None:raise ValueError('位置', p, '处已存在左子结点！')self._size += 1node.left = self._Node(e, parent=node) # 左子结点的父结点是nodereturn self._node2pos(node.left)

_add_right(p, e)

实现方式同_add_left()：

def _add_right(self, p, e):"""为位置p处的结点创建保存元素e的右子结点并返回结点位置，如果位置p处结点已有右子结点则抛出ValueError异常"""node = self._pos2node(p)if node.right is not None:raise ValueError('位置', p, '处已存在左子结点！')self._size += 1node.right = self._Node(e, parent=node) # 右子结点的父结点是nodereturn self._node2pos(node.right)

_replace(p, e)

根据方法功能即可实现：

def _replace(self, p, e):"""替换位置p处结点的元素为e，并返回旧元素"""node = self._pos2node(p)old = node.elementnode.element = ereturn old

_delete(p)

该方法的实现较为复杂，可分为以下几个步骤：

首先得到位置p处的结点对象；其次判断位置p处结点是否有且仅有一个子结点；当且仅当上述判断为是时才进行下列操作： 使得位置p处结点的父结点成为其子结点的父结点，即旁路位置p处的结点；根据位置p处的结点是否为根结点需要做如下对应操作： 当位置p处结点为根结点时，此时需要将其子结点“扶正”为新的根结点；当位置p处结点为一个左结点时，此时需要将其子结点“扶正”为新的左结点；当位置p处结点为一个右结点时，此时需要将其子结点“扶正”为新的右结点。

def _delete(self, p):"""删除位置p处结点并返回结点的对象元素，如果该结点有且仅有一个子结点则使用子结点代替其位置，如果该结点有两个子结点，则抛出异常"""node = self._pos2node(p)if self.num_children(p) == 2:raise ValueError('位置', p, "处有两个子结点！")child = node.left if node.left else node.right # child可能为Noneif child is not None:child.parent = node.parent # 待删除结点的父结点成为其子结点的父结点if node is self._root:self._root = child # 待删除的结点如为根结点则起子结点成为新的根结点else:parent = node.parentif node is parent.left:parent.left = childelse:parent.right = childself._size -= 1node.parent = None # 识别已删除结点的约定node.element = None # 识别已删除结点的约定return node.element

_attach(p, t1, t2)

实现该方法只要将二叉树t1和t2的根结点分别链接为位置p处结点的左右子结点即可，只是需要注意的是在完成链接后t1和t2已经不是独立存在的二叉树了，因此需要将原本指向二者根结点的变量置为None：

def _attach(self, p, t1, t2):"""将同类型的二叉树t1和t2在本树位置p的叶子结点处分别链接成左右子树"""node = self._pos2node(p)if not self.is_leaf(p):raise ValueError('位置p：', p, '处的结点必须为叶子结点！')if not (type(t1) is type(self) and type(t2) is type(self)):raise TypeError('t1：', t1, '、t2：', t2, '必须为', type(self))self._size += (len(t1) + len(t2))if not t1.is_empty(): # 将t1链接为位置p处结点的左子树t1._root.parent = nodenode.left = t1._roott1._root = None # 链接后已不存在t1这个二叉树t1._size = 0if not t2.is_empty(): # 将t2链接为位置p处结点的右子树t2._root.parent = nodenode.right = t2._roott2._root = None # 链接后已不存在t2这个二叉树t2._size = 0

2. 链表二叉树各方法时间复杂度

下面给出LinkedBinaryTree中所有方法的时间复杂度：

__len__方法因为使用保存结点数量的实例属性，故时间复杂度为 O ( 1 ) O(1) O(1)，而is_empty方法仅需调用一次__len__方法，因此时间复杂度也为 O ( 1 ) O(1) O(1)；由于root、left、right、parent、num_children方法的实现中不包含任何循环，其调用的实用方法也不包含任何循环，因此这些方法的时间复杂度均为 O ( 1 ) O(1) O(1)，进一步地，sibling、children以及num_children方法的实现均依赖对前述方法的有限次调用，故其时间复杂度也为 O ( 1 ) O(1) O(1)；方法depth和height方法的时间复杂度在前面已经进行了分析，此处不再赘述；对于所有上述二叉树LinkedBinaryTree的修改类操作，由于其中代码及其调用的实用方法均不包含任何形式的循环，故其时间复杂度也为 O ( 1 ) O(1) O(1)。

七、一般树的实现

前面我们使用结点的链式存储结构实现了一个二叉树LinkedBinaryTree，其中的每个结点都显式保存了指向其左右子结点的引用。

对于一般结构的树而言，由于我们并不能事先知道每一个结点可能有几个子结点，因此考虑使用一个容器作为结点的属性，该容器中保存了其所在结点的所有子结点引用，这样的容器可以是一个Python的列表，也可以是一个链表。

基于上述讨论，如果使用一个Python列表作为这样的一个容器，则一个采用结点链式存储结构的一般树如下图所示：

鉴于文章篇幅，本文不再对如上图所示的一般树进行具体实现，留待感兴趣的读者自行实现。