8 Trees
8.1 general trees
树与数组等线性结构不同，树是以层级的方式来组织的。树是一种抽象数据类型，以层级的方式来存储元素。除了最顶部 的元素，每一个元素都有自己的父元素和零到多个子元素。
如果要正式的定义，一棵树T是一些结点的集合，每个结点都满足以下两点父子关系：
- 如果T不是空的，则它肯定含有一个特殊的结点称为他的根部，树的根部没有父结点。
- 每一个不是根结点的结点都有自己唯一的父结点。
以可以用递归的方式来定义树：一棵树T要么就是空的，要么就包含一个根结点，根结点的子结点也都是树。
一些结点间的关系：
- siblings: 两个结点如果是同一个父结点的子结点则称为兄弟结点
- external node: 没有子结点的结点
- internal node: 至少有一个子结点的结点
- leaves: external node也叫树叶
- ancestor: 结点u是结点v的祖先，如果u = v或者u是v父结点的祖先
- descendant: v是u的后代如果u是v的祖先
edges and paths
- 树T的一条边(u, v)有一对相邻的定点组成
- 路径则是一系列的结点，其中任意两个相邻的结点都是一条边
ordered tree 一棵树是有序的如果它的结点的所有子结点是有序的，这里的有序指子结点可以找出第一个，第二个...
tree ADT
我们将树的每个结点抽象成position，position p可以通过p.element()来返回这个位置的元素
一些抽象方法：
- T.root(): 返回根结点position
- T.is_root(p)
- T.parent(p): 返回父结点的position,如果是根结点则返回None
- T.num_children(p)
- T.children(p): 返回p所有子结点的迭代器
- T.is_leaf(p)
- len(T): 返回树中包含元素(position)的个数
- T.is_empty()
- T.positions(): 返回所有positions的迭代器
- iter(T): 返回所有元素elements的迭代器
所有接受position参数的函数如果接受非法的position输入都会产生ValueError错误
首先实现一个抽象的Tree base class，定义好抽象的method，方便给子类继承使用。
class Tree:
"""abstract base class representing a tree structure"""
class Position:
def element(self):
""" return the element stored at this Position """
raise NotImplementedError('must be implemented by subclass')
def __eq__(self, other):
raise NotImplementedError('must be implemented by subclass')
def __ne__(self, other):
return not (self == other)
def root(self):
raise NotImplementedError('must be implemented by subclass')
def parent(self, p):
raise NotImplementedError('must be implemented by subclass')
def num_children(self, p):
raise NotImplementedError('must be implemented by subclass')
def children(self, p):
raise NotImplementedError('must be implemented by subclass')
def __len__(self):
raise NotImplementedError('must be implemented by subclass')
def is_root(self, p):
return self.root() == p
def is_leaf(self, p):
return self.num_children(p) == 0
def is_empty(self):
return len(self) == 0
计算depth和height
假设p为树的一个position，则p的深度depth是p的祖先结点的数量，但是不包括p本身。显然根结点的深度为0. p的深度等于p的父结点的深度加1。
def depth(self, p):
if self.is_root(p):
return 0
else:
return 1 + self.depth(self.parent(p))
一个位置p的高度height也是使用递归定义的：
- 如果p是叶结点，则p的高度是0
- 否则，p的高度是p的子结点的高度 + 1
- 一个非空的树的高度等于这棵树根结点的高度
- 一个非空的树的高度还等于它所有叶结点的深度中最大的
def _height2(self, p):
""" return the height of the subtree rooted at Position p."""
if self.is_leaf(p):
return 0
else:
return 1 + max(self._height(c) for c in self.children(p))
8.2 二叉树
性质：
- 每个结点最多只有2个子结点
- 每个结点标记为左结点或者右结点
- 一个结点的两个子结点中，左结点的顺序在右结点的前面
- 一棵二叉树如果每个结点都是有0个或者2个子结点，则称为proper的
决策树
决策树用在需要很多yes或者no的问题上。每个结点表示一个问题，左右两条边分别表示两种回答。 决策树是proper二叉树。决策树的每个叶结点位置表示一个决策，对应从根到它的路径中所有边的选择。
二叉树 ADT
- T.left(p): 返回左子结点的位置，如果不存在则返回None
- T.right(p)
- T.sibling(p)
我们现在实现一个新的抽象类BinaryTree，继承于树的基类，实现一些基类的抽象函数，但是仍然 有一些具体的实现没有定义。
class BinaryTree(Tree):
"abstract base class representing a binary tree structure."""
# additional abstract methods
def left(self, p):
raise NotImplementedError("must be implemented by subclass")
def sibling(self, p):
parent = self.parent(p)
if parent is None: # p is root
return None
else:
if p == self.left(parent):
return self.right(parent)
else:
return self.left(parent)
def children(self, p):
"""generate an iteration of Positions representing p's children."""
if self.left(p) is not None:
yield self.left(p)
if self.right(p) is not None:
yield self.right(p)
我们将二叉树同一个深度d上的所有结点标记为level d的一个集合。level 0最多只有一个根结点，level 1最多 2个结点...level d最多有2d个结点. 假设T是非空的二叉树，n,ne,ni和h分别表示结点的数量，外部结点的数量，内部结点的数量，还有树的高度。 则T满足：
- h + 1 <= n <= 2h+1 - 1
- 1 <= ne <= 2h
- h <= ni <= 2h - 1
- log(n+1) - 1 <= h <= n - 1
如果T是proper的二叉树，则满足：
- 2*h+1 <= n <= 2h+1-1
- h+1 <= ne <= 2h
- h <= ni <= 2h-1
- log(n+1) - 1 <= h <= (n-1)/2
- 在一个非空proper二叉树中，ne = ni + 1
8.3 Implementing Trees
树的实现一般使用链式结构。每个结点维护有它的父结点和子结点的引用，还有它自己存储的元素。 树的对象本身维护有根结点的引用和一个变量存储树的结点数量。
现在定义一个实现类LinkedBinaryTree继承于前面的抽象类BinaryTree.
与前面链表的实现一样，我们定义_Node为保护类型，作为实际的存储结构，而提供一个公共接口Position来封装。 定义_validate函数来检查一个位置是否属于这棵树并返回他的结点，还有_make_position函数将一个结点 封装成位置对象。
我们不在树的基类提供一些用来更新树的方法，因为实际具体实现中不同类型的树可能会有不同的更新行为。
对于链式的二叉树，有下面的一些更新方法：
- T.add_root(e): 为一棵空树创建一个根结点，元素e存储到结点中，然后返回根结点的position。如果这棵树不是空的则报错。
- T.add_left(p, e): 用元素e创建一个新结点并作为p的左子结点。如果p已经有左子结点则报错
- T.add_right(p, e)
- T.replace(p, e): 用元素e替换位置p原来的元素，并返回原来的元素
- T.delete(p): 删除位置p，并用它的子结点代替它的位置，返回p位置的元素。如果它有2个子结点则出错
- T.attach(p, T1, T2): p应该是一个叶结点，将T1,T2作为p的左右子结点，然后将T1,T2重置为空
以上这些操作都是可以在O(1)的时间内完成的。我们在LinkedBinaryTree类中将上面6个方法定义为保护类型， 继承于LinkedBinaryTree的类将可以调用这些受保护的方法，并对外提供一个public接口。
class LinkedBinaryTree(BinaryTree):
"""linked representation of a binary tree structure."""
class _Node:
__slots__ = '_element', '_parent', '_left', '_right'
def __init__(self, element, parent=None, left=None, right=None):
self._element = element
self._parent = parent
self._left = left
self._right = right
class Position(BinaryTree.Position):
def __init__(self, container, node):
"""constructor should not be invoked by user."""
self._container = container
self._node = node
def element(self):
return self._node._element
def __eq__(self, other):
return type(other) is type(self) and other._node is self._node
def _validate(self, p):
"""Position -> Node"""
if not isinstance(p, self.Position):
raise TypeError('p must be proper Position type')
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._parent is p._node:
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
"""return Position instance for given node (or None if no node)."""
return self.Position(self, node) if node is not None else None
def __init__(self):
"""create an initially empty binary tree."""
self._root = None
self._size = 0
def __len__(self):
return self._size
def root(self):
return self._make_position(self._root)
def parent(self, p):
node = self._validate(p)
return self._make_position(node._parent)
def left(self, p):
node = self._validate(p)
return self._make_position(node._left)
def right(self, p):
node = self._validate(p)
return self._make_position(node._right)
def num_children(self, p):
node = self._validate(p)
count = 0
if node._left is not None:
count += 1
if node._right is not None:
count += 1
return count
def _add_root(self, e):
if self._root is not None: raise ValueError('root exists')
self._size = 1
self._root = self._Node(e)
return self._make_position(self._root)
def _add_left(self, p, e):
"""create a new left child for Position p, storing element e."""
node = self._validate(p)
if node._left is not None: raise ValueError('left child exists')
self._size += 1
node._left = self._Node(e, node) # args: element, parent
return self._make_position(node._left)
def _add_right(self, p, e):
node = self._validate(p)
if node._right is not None: raise ValueError('right child exists')
self._size += 1
node._right = self._Node(e, node)
return self._make_position(node._right)
def _replace(self, p, e):
"""replace the element at position p with e, and return old element."""
node = self._validate(p)
old = node._element
node._element = e
return old
def _delete(self, p):
"""delete the node at Position p, and replace it with its child, if any.
return the element that had been stored at Position p.
raise ValueError if Position p is valid or p has two children.
"""
node = self._validate(p)
if self.num_children(p) == 2: raise ValueError('p has two children')
if child is not None:
child._parent = node._parent
if node is self._root:
self._root = child
else:
parent = node._parent
if node is parent._left:
parent._left = child
else:
parent._right = child
self._size -= 1
node._parent = node # convention for deprecated node
return node._element
def _attach(self, p, t1, t2):
"""attach trees t1 and t2 as left and right subtrees of external p."""
node = self._validate(p)
if not self.is_leaf(p): raise ValueError('position must be leaf')
if not type(self) is type(t1) is type(t2): # all 3 trees must be same type
raise TypeError('trees types must matct')
self._size += len(t1) + len(t2)
if not t1.is_empty():
t1._root._parent = node
node._left = t1._root
t1._root = None # set t1 instance to empty
t1._size = 0
if not t2.is_empty():
t2._root._parent = node
node._left = t2._root
t2._root = None # set t2 instance to empty
t2._size = 0
数组表示得二叉树
对于树T得每个位置p，f(p)是一个定义如下得整数：
- 如果p是根，则f(p) = 0
- 如果p是一个位置q的左孩子，则f(p) = 2*f(q) + 1
- 如果p是一个位置q的右孩子，则f(p) = 2*f(q) + 2
用数组表示的二叉树有一个很大的缺点是如果要删除某个结点不是那么容易的事情，因为 删除这个结点之后它的所有后代结点的标号都要重新计算。
8.4 树的遍历算法
preorder和postorder前序和后序遍历。
preorder(T, p):
perform 'visit' action for position p
for each child c in T.children(p) do:
preorder(T, c)
前序遍历中，每次到达一个结点，先访问这个结点，然后依次前序遍历它的所有子结点。也就是说， 前序遍历中每个结点一定在它的所有子结点之前被访问。
后序遍历则相反，到达一个结点的时候，先后序遍历完这个结点的所有子结点之后，才访问这个结点， 所以一个结点会在他的所有子结点被访问之后才被访问。
宽度优先遍历
在宽度优先遍历中，我们会先将深度d的所有结点都访问完，然后才会访问深度d+1的结点。 宽度优先遍历可以用在对游戏的分析中，比如当前的一个状态可以得到多少个后序状态，可以通过 宽度优先遍历得到。在实现中，我们使用一个队列就可以简单的实现这种算法。
breadthfirst(T):
将T.root()放到空队列Q中
while Q not empty do:
p = Q.dequeue()
visit p
for each child c in T.children(p) do:
Q.enqueue(c)
中序遍历
inorder(p):
if p has a left child lc then
inorder(c)
visit p
if p has a right child rc then
inorder(c)
中序遍历可以用来遍历算术表达式，如3+1*3/9-5
二叉搜索树
假设S是一个集合，它的元素是有序的，如整数集合。一个binary search tree对于S来说是一个满足下面 条件的二叉树：
- 每个位置p存储一个S的元素，用e(p)表示
- p的左边子树中存储的所有元素都 < e(p)
- p的右边子树中存储的所有元素都 > e(p)
我们可以用二叉搜索树来查找一个元素v是否在一个集合S中，从根部开始一直往下走，如果 当前结点p有e(p) = v则查找成功，否则根据e(p)与v的大小关系到左或右子树中查找，如果走到了 一棵空的子树则说明查找失败。
python实现树遍历
- T.positions(): 产生树T的所有positions的迭代
- iter(T): 产生T的所有元素的迭代器
def __iter__(self):
"""generate an iteration of the tree's elements."""
for p in self.positions():
yield p.element()
现在剩下的就是T.positions()怎么遍历所有位置的问题了，这需要根据实际需要采用上面几种不同的遍历方法。
如前序遍历：
def preorder(self):
"""generate a preorder iteration of positions in the tree."""
if not self.is_empty():
for p in self._subtree_preorder(self.root()): # start recursion
yield p
def _subtree_preorder(self, p):
"""generate a preorder iteration of positions in subtree rooted at p."""
yield p
for c in self.children(p):
for other in self._subtree_preorder(c):
yield other
辅助函数_subtree_preorder的作用事产生以位置p为根的子树的迭代，所以在preorder函数中 直接以self.root()作为参数调用就行。而辅助函数的具体实现中，因为是前序遍历，所以先将当前的p位置 yield出去，然后对于p的每个字结点，都要前序遍历，做法是递归调用辅助函数本身来获取以子结点c作为 根的子树的迭代，并将这个迭代中的每个位置都yield到外层调用。所以从总体上看，辅助函数实现了将 p结点和他的所有后代结点按照前序遍历的顺序yield到外面去。
将这些内部实现封装在positions()函数中给用户使用
def positions(self):
return self.preorder()
假设现在要遍历一个目录结构，输出如下：
Electronics R’Us
1 R&D
2 Sales
2.1 Domestic
2.2 International
2.2.1 Canada
2.2.2 S. America
这里每一级的目录要按序号来排列，同时还要输出每个元素的一个序号路径。这个序号标签由位置决定， 与根结点到当前结点的路径相关。
现在定义函数preorder_label(T, p, d, path)来输出根为p的子树T的目录结构，d为p的深度， path是从根结点下来的一个路径，是一个list，纪录路径中所选的结点是它父结点的第几个子结点，如 从根结点开始连续选三次第一个孩子，则路径为[0,0,0]。
def preorder_label(T, p, d, path):
"""Print labeled representation of subtree of T rooted at p at depth d."""
label = '.'.join(str(j + 1) for j in path) # 标签下标从1开始，所以j+1
print(2*d*' ' + label, p.element())
path.append(0)
for c in T.children(p):
preorder_label(T, c, d+1, path)
path[-1] += 1
path.pop()