Python数据结构树与算法分析

1.示例

树的一些属性：

• 层次性：树是按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。

• 一个节点的所有子节点都与另一个节点的所有子节点无关。

• 叶子节点都是独一无二的。

• 嵌套

2.术语及定义

• 节点：树的基础部分。节点的名字 → 键，附加信息 → 有效载荷。

• 边：两个节点通过一条边相连，表示它们之间存在关系。除了根节点，其他每个结点都仅有一条入边，出边则可能有多条。

• 根节点：树中唯一没有入边的结点。

• 路径：由边连接的有序节点列表。

• 子节点：一个节点通过出边与子节点相连。

• 父节点：一个节点是其所有子节点的父节点。

• 兄弟节点：具有同一父节点的结点 → 互称兄弟节点。

• 子树：一个父节点及其所有后代的节点和边构成一棵子树。

• 叶子结点：叶子节点没有子节点。

• 层数：节点n的层数是从根节点到n的唯一路径长度。根节点的层数为0。

• 高度：树的高度是其中节点层数的最大值。

1.定义一：树由节点及连接节点的边构成。

树的属性：

• 有一个根节点除根节点外，其他每个节点都与其唯一的父节点相连。

• 从根节点到其他每个节点有且仅有一条路径。

• 如果每个节点最多有两个子节点 → 二叉树。

2.定义二：一棵树要么为空，要么由一个根节点和零棵或多棵子树构成，子树本身也是一棵树。

每棵子树的根节点通过一条边连到父树的根节点。

3.实现

3.1 列表之列表

树的根节点是myTree[0]，左子树是myTree[1]，右子树是myTree[2]。

# 列表函数
def BinaryTree(r):
   return [r,[],[]] # 根节点r，和两个作为子节点的空列表
# 插入左子树
def insertLeft(root,newBranch):
   t = root.pop(1)
   if len(t) > 1:
       root.insert(1,[newBranch,t,[]])
   else:
       root.insert(1,[newBranch,[],[]])
   return root

## 插入右子树
def insertRight(root , newBranch):
   t = root.pop(2)
   if len(t) > 1:
       root.insert(2,[newBranch,[],t])
   else:
       root.insert(2,[newBranch,[],[]])
   return root
### 树的访问函数
def getRootVal(root):
   return root[0]
def setRootVal(root,newVal):
   root[0] = newVal
def getLeftChild(root):
   return root[1]
def getRightChild(root):
   return root[2]
r = BinaryTree(3)
insertLeft(r,4)
print(r)

3.2节点与引用

定义一个类，其中有根节点和左右子树的属性。

class BinaryTree:
   def __init__(self,rootObj):
       self.key = rootObj
       self.leftChild = None
       self.rightChild = None

## 插入左子节点
   def insertLeft(self,newNode):
       if self.leftChild == None:
           self.leftChild = BinaryTree(newNode)
       else:
           t = BinaryTree(newNode)
           t.left = self.leftChild
           self.leftChild = t
   ## 插入右子节点
   def insertRight(self,newNode):
       if self.rightChild == None:
           self.rightChild = BinaryTree(newNode)
       else:
           t = BinaryTree(newNode)
           t.right = self.rightChild
           self.rightChild = t
   ## 访问函数
   def getRightChild(self):
       return self.rightChild

def getLeftChild(self):
       return self.leftChild

def setRootVal(self,obj):
       self.key = obj
   def getRootVal(self):
       return self.key

4.二叉树的应用

4.1解析树

• 根据完全括号表达式构建解析树

• 如何计算解析树中的表达式

• 如何将解析树还原成最初的数学表达式

解析树构建器：

import operator

from pythonds.basic import Stack
from pythonds.trees import BinaryTree
def buildParseTree(fpexp):
   fplist = fpexp.split()
   pStack = Stack()
   eTree = BinaryTree("")
   pStack.push(eTree)
   currentTree = eTree

for i in fplist:
       if i == "(":
           currentTree.insertLeft("")
           pStack.push(currentTree)
           currentTree = currentTree.getLeftChild()

elif i not in "+-*/)":
           currentTree.setRootVal(eval(i))
           parent = pStack.pop()
           currentTree = parent
       elif i in "+-*/":
           currentTree.setRootVal(i)
           currentTree.insertRight("")
           currentTree = currentTree.getRightChild()
       elif i == ")":
           currentTree = pStack.pop()
       else:
           raise ValueError("Unkown Operator :" + i )
   return eTree

## 计算二叉解析树的递归函数
def evaluate(parseTree):
   opers = {
       "+":operator.add,"-":operator.sub,
       "*":operator.mul,"/":operator.truediv
   }

leftC = parseTree.getLeftChild()
   rightC = parseTree.getRightChild()

if leftC and rightC:
       fn = opers[parseTree.getRootVal()]
       return fn(evaluate(leftC),evaluate(rightC))
   else:
       return parseTree.getRootVal()

4.2树的遍历

• 前序遍历【根左右】

• 中序遍历【左根右】

• 后序遍历【左右根】

前序遍历算法实现为外部函数：

def preorder(tree):
   if tree:
       print(tree.getRootVal())
       preorder(tree.getLeftChild())
       preorder(tree.getRightChild)

前序遍历算法实现为BinaryTree类的方法

def preorder(self):
   print(self.key)
   if self.leftChild:
       self.leftChild.preorder()
   if self.rightChild:
       self.rightChild.preorder()

后序遍历函数

def postorder(tree):
   if tree != None:
       postorder(tree.getLeftChild())
       postorder(tree.getRightChild())
       print(tree.getRootVal())

中序遍历函数

def inorder(tree):
   if tree != None:
       inorder(tree.getLeftChild())
       print(tree.getRootVal())
       inorder(tree.getRightChild())

5.利用二叉堆实现优先级队列

队列一个重要的变体 → 优先级队列。和队列一样，优先级队列从头部移除元素，不过元素的逻辑顺序是由优先级决定的，优先级最高的元素在最前，最低的元素在最后。

实现优先级队列的经典方法 → 二叉堆。入队和出队操作均可达到O(logn)

• 最小堆【最小的元素一直在队首】

• 最大堆【最大的元素一直在队首】 6.6.2 二叉堆的实现

结构属性：

• 完全二叉树：除了最底层，其他每一层的节点都是满的。且在最底层，从左往右填充节点。

• 完全二叉树可以用一个列表直接表示。

堆的有序性：对于堆中任意元素x及其父元素p，p都不大于x。

堆操作

代码实现：

class EchaDui:
   # 新建二叉堆
   def __init__(self):
       self.heapList = [0]
       self.currentSize = 0

def percUp(self,i):
       while i // 2 > 0:
           if self.heapList[i] < self.heapList[i // 2]:
               tmp = self.heapList[i // 2]
               self.heapList[i // 2] = self.heapList[i]
               self.heapList[i] = tmp

i = i // 2
   # 新加元素
   def insert(self,k):
       self.heapList.append(k)
       self.currentSize = self.currentSize + 1
       self.percUp(self.currentSize)

def percDown(self,i):
       while (i * 2) <= self.currentSize:
           mc = self.minChild(i)
           if self.heapList[i] > self.heapList[mc]:
               tmp = self.heapList[i]
               self.heapList[i] = self.heapList[mc]
               self.heapList[mc] = tmp
           i = mc
   def minChild(self,i):
       if i * 2 + 1 > self.currentSize:
           return i * 2
       else:
           if self.heapList[i*2] < self.heapList[i*2 + 1]:
               return i * 2
           else:
               return i * 2 + 1
   ## 从二叉堆中删除最小的元素
   def delMin(self):
       retval = self.heapList[1]
       self.heapList[1] = self.heapList[self.currentSize]
       self.currentSize = self.currentSize - 1
       self.heapList.pop()
       self.percDown(1)
       return retval

## 根据元素列表构建堆
   def builgHeap(self,alist):
       i = len(alist) // 2
       self.currentSize = len(alist)
       self.heapList = [0] + alist[:]
       while (i > 0):
           self.percDown(i)
           i = i - 1

6.二叉搜索树

6.1搜索树的实现

二叉搜索树依赖性质：小于父节点的键都在左子树中，大于父节点的键则都在右子树。

代码实现：

class BinarySearchTree:
   def __init__(self):
       self.root = None
       self.size = 0
   def length(self):
       return self.size
   def __len__(self):
       return self.size
   def __iter__(self):
       return self.root.__iter__()
   # 插入新节点
   def put(self,key,val):
       if self.root:
           self._put(key,val,self.root)
       else:
           self.root = TreeNode(key,val)
       self.size = self.size + 1

def _put(self,key,val,currentNode):
       if key < currentNode.key:
           if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
           else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
       else:
           if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
           else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)
   def __setitem__(self, key, value):
       self._put(key,value)

## 查找键对应的值
   def get(self,key):
       if self.root:
           res = self._get(key,self.root)
           if res:
               return res.payload
           else:
               return None
       else:
           return None
   def _get(self,key,currentNode):
       if not currentNode:
           return None
       elif currentNode.key == key:
           return currentNode
       elif key < currentNode.key:
           return self._get(key,currentNode.leftChild)
       else:
           return self._get(key,currentNode.rightChild)
   def __getitem__(self, key):
       return self.get(key)

# 检查树中是否有某个键
   def __contains__(self, key):
       if self._get(key,self.root):
           return True
       else:
           return False
   # 删除
   def delete(self,key):
       if self.size > 1:
           nodeToRemove = self._get(key,self.root)
           if nodeToRemove:
               self.remove(nodeToRemove)
               self.size = self.size - 1
           else:
               raise KeyError("Error,key not in tree")
       elif self.size == 1 and self.root.key == key:
           self.root = None
           self.size = self.size - 1
       else:
           raise KeyError("Error,key not in tree")
   def __delitem__(self, key):
       self.delete(key)

"""
       1. 待删除节点没有子节点
       2. 待删除节点只有一个子节点
       3. 待删除节点有两个子节点
   """
   # 寻找后继结点
   def findSuccessor(self):
       succ = None
       if self.hasRightChild():
           succ = self.rightChild.findMin()
       else:
           if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
       return succ

def findMin(self):
       current = self
       while current.hasLeftChild():
           current = current.leftChild
       return current

def spliceOut(self):
       if self.isLeaf():
           if self.isLeftChild():
               self.parent.leftChild = None
           else:
               self.parent.rightChild = None
       elif self.hasAnyChildren():
           if self.hasLeftChild():
               if self.isLeftChild():
                   self.parent.leftChild = self.leftChild
               else:
                   self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent

else:
               if self.isLeftChild():
                   self.parent.leftChild = self.rightChild
               else:
                   self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

def remove(self,currentNode):
       if currentNode.isLeaf():
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
       elif currentNode.hasBothChildren():
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload
       else:
           if currentNode.hasLeftChild():
               if currentNode.isLeftChild():
                   currentNode.leftChild.parent = currentNode.parent
                   currentNode.parent.leftChild = currentNode.leftChild
               elif currentNode.isRightChild():
                   currentNode.leftChild.parent = currentNode.parent
                   currentNode.parent.rightChild = currentNode.leftChild
               else:
                   currentNode.replaceNodeData(currentNode.leftChild.key,
                                               currentNode.leftChild.payload,
                                               currentNode.leftChild.leftChild,
                                               currentNode.leftChild.rightChild
                                               )
           else:
               if currentNode.isLeftChild():
                   currentNode.rightChild.parent = currentNode.parent
                   currentNode.parent.leftChild = currentNode.rightChild
               elif currentNode.isRightChild():
                   currentNode.rightChild.parent = currentNode.parent
                   currentNode.parent.rightChild = currentNode.rightChild
               else:
                   currentNode.replaceNodeData(currentNode.rightChild.key,
                   currentNode.rightChild.payload,
                   currentNode.rightChild.leftChild,
                   currentNode.rightChild.rightChild                            
                                               )
   # 二叉搜索树迭代器
   def __iter__(self):
       if self:
           if self.hasLeftChild():
               for elem in self.leftChild:
                   yield elem
           yield self.key
           if self.hasRightChild():
               for elem in self.rightChild:
                   yield elem

class TreeNode:
   def __init__(self,key,val,left = None,right = None,parent = None):
       self.key = key
       self.payload = val
       self.leftChild = left
       self.rightChild = right
       self.parent = parent

def hasLeftChild(self):
       return self.leftChild
   def hasRightChild(self):
       return self.rightChild
   def isLeftChild(self):
       return self.parent and self.parent.leftChild == self
   def isRightChild(self):
       return self.parent and self.parent.rightChild == self
   def isRoot(self):
       return not self.parent
   def isLeaf(self):
       return not (self.rightChild or self.leftChild)
   def hasAnyChildren(self):
       return self.rightChild or self.leftChild
   def replaceNodeData(self,key,value,lc,rc):
       self.key = key
       self.payload = value
       self.leftChild = lc
       self.rightChild = rc
       if self.hasLeftChild():
           self.leftChild.parent = self
       if self.hasRightChild():
           self.rightChild.parent = self

7.平衡二叉搜索树（AVL树）

实现AVL树时，要记录每个节点的平衡因子。

平衡因子 = 左右子树的高度之差

&rarr; 保证树的平衡因子为-1，0,1，可以使得关键操作获得更好的大O性能

#from 第6章树.二叉搜索树 import TreeNode
def _put(self, key, val, currentNode):
   if key < currentNode.key:
       if currentNode.hasLeftchi1d():
           self._put(key, val, currentNode.leftChild)
       else:
           currentNode.leftChild = TreeNode(key, val,parent=currentNode)
           self.updateBalance(currentNode.leftChild)
   else:
       if currentNode.hasRightChild():
           self._put(key, val, currentNode.rightChild)
       else:
           currentNode.rightchild - TreeNode(key, val,parent=currentNode)
           self.updateBalance(currentNode.rightChild)
def updateBalance(self, node):
   if node.balanceFactor > 1 or node.balanceFactor < -1:
       self.rebalance(node)
       return
   if node.parent != None:
       if node.isLeftChild():
           node.parent.balanceFactor += 1
       elif node.isRightChild():
           node.parent.balanceFactor -= 1
       if node.parent.balanceFactor != 0:
           self.updateBalance(node.parent)
# 实现左旋
def rotateLeft (self, rotRoot) :
   newRoot = rotRoot .rightchild
   rotRoot .rightChild = newRoot.leftChild
   if newRoot . leftChild !=None :
       newRoot . leftChild. parent = rotRoot
   newRoot.parent =rotRoot.parent
   if rotRoot .isRoot( ):
       self.root = newRoot
   else:
       if rotRoot .isLeftChild():
           rotRoot.parent .leftChild = newRoot
       else:
           rotRoot.parent .rightChild = newRoot
   newRoot . leftChild = rotRoot
   rotRoot.parent = newRoot
   rotRoot. balanceFactor = rotRoot . balanceFactor + 1 - min(newRoot . balanceFactor,0)
   newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )

# 实现再平衡
def rebalance(self, node) :
   if node. balanceFactor < 0:
       if node .rightChild .balanceFactor > 0:
           self.rotateRight (node.rightChild)self.rotateLeft (node)
       else:
           self.rotateLeft (node)
   elif node. balanceFactor > 0 :
       if node . leftChild. balanceFactor < 0:
           self.rotateLeft (node. leftChild)
           self.rotateRight (node)
       else:
           self.rotateRight (node)
nceFactor + 1 - min(newRoot . balanceFactor,0)
   newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )
# 实现再平衡
def rebalance(self, node) :
   if node. balanceFactor < 0:
       if node .rightChild .balanceFactor > 0:
           self.rotateRight (node.rightChild)self.rotateLeft (node)
       else:
           self.rotateLeft (node)
   elif node. balanceFactor > 0 :
       if node . leftChild. balanceFactor < 0:
           self.rotateLeft (node. leftChild)
           self.rotateRight (node)
       else:
           self.rotateRight (node)

来源：https://blog.csdn.net/weixin_44226181/article/details/125793309