• 非线性数据结构；
• 包括根，枝，叶三部分；也可以说由节点(node)和边(edge)组成；
• 层次化，各个子节点之间独立每个叶节点具有唯一性；
• 树中所有节点的最大曾经称为树的高度根节点所在的层级为0。

树的实现

嵌套列表实现

子树结构与树相同，是一种递归数据结构。

atree=['a',['left',[],[]],['right',[],[]]]

插入方法的实现(以插入左树为例)。

def insertLeft(root,newBranch):
  t = root.pop(1)  
  #提取左子节点
  if len(t) > 1:
  #如果左子节点存在，则需要先插入新节点再将原来的节点作为其左子节点   
    root.insert(1,[newBranch,t,[]])
  else:
    root.insert(1,[newBranch,[],[]])

树的链表实现

• 节点链表法：链表中每个节点保存节点的数据项以及左右子树的链接。

插入方法：加入中间变量，将插入节点与原先节点相连接。

应用

• 树表示表达式

树的遍历(Tree Traversals)

遍历(Traversals)：对数据集中所有数据进行访问。对于线性数据结构，按顺序访问即可。

树的遍历包括：前序遍历（根–左–右），中序遍历（左–根–右）和后序遍历（左–右–根）。

优先队列与二叉堆

优先队列：先入先出，内部次序由优先级确定

二叉堆（Binary Heap）实现优先队列

入队和出队的复杂度均为O（log n）。如果使操作始终保持再对数量级上，二叉树必须保持平衡。可以通过完全二叉树近似实现平衡。

完全二叉树：叶节点最多只出现在最底层和次底层；最底层的叶节点集中在左边（最多由有一个节点例外）。

性质：若节点下表为p,则其左子节点下标为2p，右子节点下标为2p+1。所以可以使用非嵌套列表表示完全二叉树。

堆次序（Heap Order）：父节点的key小于其子节点。

二叉堆

二叉堆的性质：

• 完全二叉树：可以用非嵌套数组表示
• 堆：任意路径为有序数列。

二叉堆操作的实现

列表保存堆数据，列表中下标为0项不用。

class BinHeap:
  def __init__():
    self.heapList = [0]
    self.currentsize = 0

• insert（key）

  为了保证二叉堆中堆的性质，需要将插入key上浮至正确的位置。插入时先添加到末尾并改变二叉树currentsize的值，之后进行上浮操作。

  #上浮(i 二叉树节点数)
  def perUp(self,i):
    while i // 2 > 0:  #到根节点j结束循环
      #与父节点比较
      if self.heapList[i] < self.heapList[i//2]:   
        #与父节点交换位置
        i = i // 2
  

• delMin()

  删除堆中最小的key，即根节点。最后一个节点代替根节点并下沉。

  # 下沉
  def percDown(self,i):
    # 是否存在左节点
    while (i * 2) <= self.currentSize:
      mc = self.minChild(i) # 返回子节点的较小值的位置
      if self.heapList[i] > self.heapList[mc]:
        # 交换下沉
        ......
      i = mc
  

• buildHeap(lst)

  利用下沉法从无序表生成堆。从最后一个节点的父节点处开始下沉（len(list)//2处），并不断迭代；为保证完全二叉树的性质，需要在无序表前端插入一个空值。

二叉查找树（Binary Search Tree）

二叉查找树比父节点大key的在右子树，比父节点小的key在左子树。

二叉搜索树的实现

• put(key,val)

  插入key构造BST。若无节点直接将插入节点作为根节点否则调用函数_put(key,val,root)来放至key。在该辅助函数中，若key比当前节点小，则放到左子树；若比当前节点大则放到右子树。索引赋值与插入方法相同，对于此类特殊方法需要前后加双下划线。

  二叉树是一种动态查找表。特点是，树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

• get(self,key)

  若根节点不存在返回空值，否则调用调用函数_get(self,key,currentNode)。在该函数中若找当对应的key则返回，否则比较key与树中key的大小，对其左、右子树递归调用函数。

• 迭代器__iter__(self)

  def __iter__(self):
    if self:
      if self.hasLeftChild():
        for elem in self.leftChild:
          # in在这里相当于递归
          yield elem
      yield self.key
      ......
  

• delete(self,key) 先用_get方法找到要删除的节点之后执行删除self.remove(nodeToRemove)。删除节点时的情况：

  1. 该节点无子节点（叶节点）—直接执行删除。
  2. 该节点有一个子节点—删除后将其子节点与其父节点连接，并对“删除节点是父节点的左/右节点？删除节点唯一子节点是其左/右节点？被删节点为根节点？”进行讨论。
  3. 该节点有两个子节点—将被删节点右子树最小的节点（根据BST的性质该节点有右子节点或为叶节点）替换被删节点。

二叉查找树的性能受到插入顺序的影响。

平衡二叉树（AVL Tree）

在实现过程中，与 BST差别在于需要对每个节点加入平衡因子。平衡因子是左右子树的高度差，大于0为左重，小于0为右重。平衡树的每个节点的平衡因子在-1到1之间。AVL树的搜索时间复杂度为O（log n）。

在插入方法中需要接入更新平衡因子的函数，自下而上更新每个节点的平衡因子。

重新平衡

将不平衡的子树进行旋转实现，左重右旋，右重左旋，左旋挂右，右旋挂左。在旋转过程中，只有新根节点和就根节点的平衡因子发生了变化。

def rotateLeft(self,rotRoot):
  newRoot = rotRoot.rightChild
  rotRoot.rightChild = newRoot.leftChild
  # 新根左子节点，挂到旧根的右子节点,父与子相连。左旋挂右。
  if newRoot.leftChild != None:
    newRoot.leftChild.parent = rotRoot 
    # 子与父相连
    ... ...
    # 整理节点之间关系
    ... ...
    rotRoot.blanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor,0)
    newRoot.blanceFactor = newRoot.balanceFactor + 1 + max(newRoot.balanceFactor,0)

在左旋要检查右子节点的因子，若右子节点左重则应先右旋在左旋。同样，右旋也需要进行类似操作。

引用

• 数据结构与算法Python版_中国大学MOOC(慕课)