天津高端品牌网站建设,网站建设电子合同,制作音乐app,网站站点建设中端口号的作用说明 如果需要用到这些知识却没有掌握#xff0c;则会让人感到沮丧#xff0c;也可能导致面试被拒。无论是花几天时间“突击”#xff0c;还是利用零碎的时间持续学习#xff0c;在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢#xff1f;列表、字典、集…
说明 如果需要用到这些知识却没有掌握则会让人感到沮丧也可能导致面试被拒。无论是花几天时间“突击”还是利用零碎的时间持续学习在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢列表、字典、集合还有……栈Python 有栈吗本系列文章将给出详细拼图。 13章: Binary Tree
The binary Tree: 二叉树每个节点做多只有两个子节点
class _BinTreeNode:def __init__(self, data):self.data dataself.left Noneself.right None# 三种depth-first遍历
def preorderTrav(subtree): 先根序遍历if subtree is not None:print(subtree.data)preorderTrav(subtree.left)preorderTrav(subtree.right)def inorderTrav(subtree): 中(根)序遍历if subtree is not None:preorderTrav(subtree.left)print(subtree.data)preorderTrav(subtree.right)def postorderTrav(subtree): 后根序遍历if subtree is not None:preorderTrav(subtree.left)preorderTrav(subtree.right)print(subtree.data)# 宽度优先遍历(bradth-First Traversal): 一层一层遍历, 使用queue
def breadthFirstTrav(bintree):from queue import Queue # py3q Queue()q.put(bintree)while not q.empty():node q.get()print(node.data)if node.left is not None:q.put(node.left)if node.right is not None:q.put(node.right)class _ExpTreeNode:__slots__ (element, left, right)def __init__(self, data):self.element dataself.left Noneself.right Nonedef __repr__(self):return _ExpTreeNode: {} {} {}.format(self.element, self.left, self.right)from queue import Queue
class ExpressionTree:表达式树: 操作符存储在内节点操作数存储在叶子节点的二叉树。(符号树真难打出来)*/ \ -/ \ / \9 3 8 4(93) * (8-4)Expression Tree Abstract Data Type可以实现二元操作符ExpressionTree(expStr): user string as constructor paramevaluate(varDict): evaluates the expression and returns the numeric resulttoString(): constructs and retutns a string represention of the expressionUsage:vars {a: 5, b: 12}expTree ExpressionTree((a/(b-3)))print(The result , expTree.evaluate(vars))def __init__(self, expStr):self._expTree Noneself._buildTree(expStr)def evaluate(self, varDict):return self._evalTree(self._expTree, varDict)def __str__(self):return self._buildString(self._expTree)def _buildString(self, treeNode): 在一个子树被遍历之前添加做括号在子树被遍历之后添加右括号 # print(treeNode)if treeNode.left is None and treeNode.right is None:return str(treeNode.element) # 叶子节点是操作数直接返回else:expStr (expStr self._buildString(treeNode.left)expStr str(treeNode.element)expStr self._buildString(treeNode.right)expStr )return expStrdef _evalTree(self, subtree, varDict):# 是不是叶子节点, 是的话说明是操作数直接返回if subtree.left is None and subtree.right is None:# 操作数是合法数字吗if subtree.element 0 and subtree.element 9:return int(subtree.element)else: # 操作数是个变量assert subtree.element in varDict, invalid variable.return varDict[subtree.element]else: # 操作符则计算其子表达式lvalue self._evalTree(subtree.left, varDict)rvalue self._evalTree(subtree.right, varDict)print(subtree.element)return self._computeOp(lvalue, subtree.element, rvalue)def _computeOp(self, left, op, right):assert opop_func {: lambda left, right: left right, # or import operator, operator.add-: lambda left, right: left - right,*: lambda left, right: left * right,/: lambda left, right: left / right,%: lambda left, right: left % right,}return op_func[op](left, right)def _buildTree(self, expStr):expQ Queue()for token in expStr: # 遍历表达式字符串的每个字符expQ.put(token)self._expTree _ExpTreeNode(None) # 创建root节点self._recBuildTree(self._expTree, expQ)def _recBuildTree(self, curNode, expQ):token expQ.get()if token (:curNode.left _ExpTreeNode(None)self._recBuildTree(curNode.left, expQ)# next token will be an operator: * / %curNode.element expQ.get()curNode.right _ExpTreeNode(None)self._recBuildTree(curNode.right, expQ)# the next token will be ), remmove itexpQ.get()else: # the token is a digit that has to be converted to an int.curNode.element tokenvars {a: 5, b: 12}
expTree ExpressionTree(((2*7)8))
print(expTree)
print(The result , expTree.evaluate(vars))Heap堆二叉树最直接的一个应用就是实现堆。堆就是一颗完全二叉树最大堆的非叶子节点的值都比孩子大最小堆的非叶子结点的值都比孩子小。 python内置了heapq模块帮助我们实现堆操作比如用内置的heapq模块实现个堆排序:
# 使用python内置的heapq实现heap sort
def heapsort(iterable):from heapq import heappush, heappoph []for value in iterable:heappush(h, value)return [heappop(h) for i in range(len(h))]但是一般实现堆的时候实际上并不是用数节点来实现的而是使用数组实现效率比较高。为什么可以用数组实现呢?因为完全二叉树的性质 可以用下标之间的关系表示节点之间的关系MaxHeap的docstring中已经说明了
class MaxHeap:Heaps:完全二叉树最大堆的非叶子节点的值都比孩子大最小堆的非叶子结点的值都比孩子小Heap包含两个属性order property 和 shape property(a complete binary tree)在插入一个新节点的时候始终要保持这两个属性插入操作保持堆属性和完全二叉树属性, sift-up 操作维持堆属性extract操作只获取根节点数据并把树最底层最右节点copy到根节点后sift-down操作维持堆属性用数组实现heap从根节点开始从上往下从左到右给每个节点编号则根据完全二叉树的性质给定一个节点i 其父亲和孩子节点的编号分别是:parent (i-1) // 2left 2 * i 1rgiht 2 * i 2使用数组实现堆一方面效率更高节省树节点的内存占用一方面还可以避免复杂的指针操作减少调试难度。def __init__(self, maxSize):self._elements Array(maxSize) # 第二章实现的Array ADTself._count 0def __len__(self):return self._countdef capacity(self):return len(self._elements)def add(self, value):assert self._count self.capacity(), can not add to full heapself._elements[self._count] valueself._count 1self._siftUp(self._count - 1)self.assert_keep_heap() # 确定每一步add操作都保持堆属性def extract(self):assert self._count 0, can not extract from an empty heapvalue self._elements[0] # save root valueself._count - 1self._elements[0] self._elements[self._count] # 最右下的节点放到root后siftDownself._siftDown(0)self.assert_keep_heap()return valuedef _siftUp(self, ndx):if ndx 0:parent (ndx - 1) // 2# print(ndx, parent)if self._elements[ndx] self._elements[parent]: # swapself._elements[ndx], self._elements[parent] self._elements[parent], self._elements[ndx]self._siftUp(parent) # 递归def _siftDown(self, ndx):left 2 * ndx 1right 2 * ndx 2# determine which node contains the larger valuelargest ndxif (left self._count andself._elements[left] self._elements[largest] andself._elements[left] self._elements[right]): # 原书这个地方没写实际上找的未必是largestlargest leftelif right self._count and self._elements[right] self._elements[largest]:largest rightif largest ! ndx:self._elements[ndx], self._elements[largest] self._elements[largest], self._elements[ndx]self._siftDown(largest)def __repr__(self):return .join(map(str, self._elements))def assert_keep_heap(self): 我加了这个函数是用来验证每次add或者extract之后仍保持最大堆的性质_len len(self)for i in range(0, int((_len-1)/2)): # 内部节点非叶子结点l 2 * i 1r 2 * i 2if l _len and r _len:assert self._elements[i] self._elements[l] and self._elements[i] self._elements[r]def test_MaxHeap(): 最大堆实现的单元测试用例 _len 10h MaxHeap(_len)for i in range(_len):h.add(i)h.assert_keep_heap()for i in range(_len):# 确定每次出来的都是最大的数字添加的时候是从小到大添加的assert h.extract() _len-i-1test_MaxHeap()def simpleHeapSort(theSeq): 用自己实现的MaxHeap实现堆排序直接修改原数组实现inplace排序if not theSeq:return theSeq_len len(theSeq)heap MaxHeap(_len)for i in theSeq:heap.add(i)for i in reversed(range(_len)):theSeq[i] heap.extract()return theSeqdef test_simpleHeapSort(): 用一些测试用例证明实现的堆排序是可以工作的 def _is_sorted(seq):for i in range(len(seq)-1):if seq[i] seq[i1]:return Falsereturn Truefrom random import randintassert simpleHeapSort([]) []for i in range(1000):_len randint(1, 100)to_sort []for i in range(_len):to_sort.append(randint(0, 100))simpleHeapSort(to_sort) # 注意这里用了原地排序直接更改了数组assert _is_sorted(to_sort)test_simpleHeapSort()14章: Search Trees
二叉差找树性质对每个内部节点V 1. 所有key小于V.key的存储在V的左子树。 2. 所有key大于V.key的存储在V的右子树 对BST进行中序遍历会得到升序的key序列
class _BSTMapNode:__slots__ (key, value, left, right)def __init__(self, key, value):self.key keyself.value valueself.left Noneself.right Nonedef __repr__(self):return {}:{} left:{}, right:{}.format(self.key, self.value, self.left, self.right)__str__ __repr__class BSTMap: BST树节点包含key可payload。用BST来实现之前用hash实现过的Map ADT.性质对每个内部节点V1.对于节点V所有key小于V.key的存储在V的左子树。2.所有key大于V.key的存储在V的右子树对BST进行中序遍历会得到升序的key序列def __init__(self):self._root Noneself._size 0self._rval None # 作为remove的返回值def __len__(self):return self._sizedef __iter__(self):return _BSTMapIterator(self._root, self._size)def __contains__(self, key):return self._bstSearch(self._root, key) is not Nonedef valueOf(self, key):node self._bstSearch(self._root, key)assert node is not None, Invalid map key.return node.valuedef _bstSearch(self, subtree, target):if subtree is None: # 递归出口遍历到树底没有找到key或是空树return Noneelif target subtree.key:return self._bstSearch(subtree.left, target)elif target subtree.key:return self._bstSearch(subtree.right, target)return subtree # 返回引用def _bstMinumum(self, subtree): 顺着树一直往左下角递归找就是最小的,向右下角递归就是最大的 if subtree is None:return Noneelif subtree.left is None:return subtreeelse:return subtree._bstMinumum(self, subtree.left)def add(self, key, value): 添加或者替代一个key的value, O(N) node self._bstSearch(self._root, key)if node is not None: # if key already exists, update valuenode.value valuereturn Falseelse: # insert a new entryself._root self._bstInsert(self._root, key, value)self._size 1return Truedef _bstInsert(self, subtree, key, value): 新的节点总是插入在树的叶子结点上 if subtree is None:subtree _BSTMapNode(key, value)elif key subtree.key:subtree.left self._bstInsert(subtree.left, key, value)elif key subtree.key:subtree.right self._bstInsert(subtree.right, key, value)# 注意这里没有else语句了应为在被调用处add函数里先判断了是否有重复keyreturn subtreedef remove(self, key): O(N)被删除的节点分为三种:1.叶子结点:直接把其父亲指向该节点的指针置None2.该节点有一个孩子: 删除该节点后父亲指向一个合适的该节点的孩子3.该节点有俩孩子:(1)找到要删除节点N和其后继S中序遍历后该节点下一个(2)复制S的key到N(3)从N的右子树中删除后继S即在N的右子树中最小的assert key in self, invalid map keyself._root self._bstRemove(self._root, key)self._size - 1return self._rvaldef _bstRemove(self, subtree, target):# search for the item in the treeif subtree is None:return subtreeelif target subtree.key:subtree.left self._bstRemove(subtree.left, target)return subtreeelif target subtree.key:subtree.right self._bstRemove(subtree.right, target)return subtreeelse: # found the node containing the itemself._rval subtree.valueif subtree.left is None and subtree.right is None:# 叶子nodereturn Noneelif subtree.left is None or subtree.right is None:# 有一个孩子节点if subtree.left is not None:return subtree.leftelse:return subtree.rightelse: # 有俩孩子节点successor self._bstMinumum(subtree.right)subtree.key successor.keysubtree.value successor.valuesubtree.right self._bstRemove(subtree.right, successor.key)return subtreedef __repr__(self):return -.join([str(i) for i in self])def assert_keep_bst_property(self, subtree): 写这个函数为了验证add和delete操作始终维持了bst的性质 if subtree is None:returnif subtree.left is not None and subtree.right is not None:assert subtree.left.value subtree.valueassert subtree.right.value subtree.valueself.assert_keep_bst_property(subtree.left)self.assert_keep_bst_property(subtree.right)elif subtree.left is None and subtree.right is not None:assert subtree.right.value subtree.valueself.assert_keep_bst_property(subtree.right)elif subtree.left is not None and subtree.right is None:assert subtree.left.value subtree.valueself.assert_keep_bst_property(subtree.left)class _BSTMapIterator:def __init__(self, root, size):self._theKeys Array(size)self._curItem 0self._bstTraversal(root)self._curItem 0def __iter__(self):return selfdef __next__(self):if self._curItem len(self._theKeys):key self._theKeys[self._curItem]self._curItem 1return keyelse:raise StopIterationdef _bstTraversal(self, subtree):if subtree is not None:self._bstTraversal(subtree.left)self._theKeys[self._curItem] subtree.keyself._curItem 1self._bstTraversal(subtree.right)def test_BSTMap():l [60, 25, 100, 35, 17, 80]bst BSTMap()for i in l:bst.add(i)def test_HashMap(): 之前用来测试用hash实现的map改为用BST实现的Map测试 # h HashMap()h BSTMap()assert len(h) 0h.add(a, a)assert h.valueOf(a) aassert len(h) 1a_v h.remove(a)assert a_v aassert len(h) 0h.add(a, a)h.add(b, b)assert len(h) 2assert h.valueOf(b) bb_v h.remove(b)assert b_v bassert len(h) 1h.remove(a)assert len(h) 0_len 10for i in range(_len):h.add(str(i), i)assert len(h) _lenfor i in range(_len):assert str(i) in hfor i in range(_len):print(len(h))print(bef, h)_ h.remove(str(i))assert _ iprint(aft, h)print(len(h))assert len(h) 0test_HashMap()
