独白:
利用算法进行查找指定元素,最近学习二分查找和二叉树遍历。二分查找前提是在有序中进行查找,二叉树引入了树的概念。树的概念其中有许多小知识点,也是一种新的数据结构。还是之前的感悟,需了解其本质才会写出更好的算法。
二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
- '''
- 二分查找
- 时间复杂度:O(logn)
- '''
- '''
- 前提是在一个有序的列表
- '''
- import time
- #
- # def binary_search(list, item):
- # ''' 非递归实现 '''
- #
- # first = 0
- # last = len(list) - 1
- # while first <= last :
- # midpoint = ( first + last ) // 2
- # if list[midpoint] == item:
- # return True
- # elif item < list[midpoint]:
- # last = midpoint - 1
- # else:
- # first = midpoint + 1
- # return False
- def binary_search(list, item):
- """ 递归实现 """
- print(list)
- if len(list) == 0:
- return False
- else:
- midpoint = len(list) // 2
- if list[midpoint] == item:
- return True
- else:
- if list[midpoint] > item:
- return binary_search(list[:midpoint], item)
- else:
- return binary_search(list[midpoint + 1:], item)
- if __name__ == '__main__':
- # 开始时间
- first_time = time.time()
- # 建立个有序的列表
- lis = [1, 2, 5, 6, 7, 8, 9, 17, 156, 678]
- # 列表排序
- print(binary_search(lis, 6))
- # 结束时间
- last_time = time.time()
- print("共用时%s" % (last_time - first_time))
树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由 n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 "树" 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
二叉树是每个节点最多有两个子树的树结构。通常子树被称作 "左子树"(left subtree)和 "右子树"(right subtree)
性质 1: 在二叉树的第 i 层上至多有 2^(i-1) 个结点(i>0)
性质 2: 深度为 k 的二叉树至多有 2^k - 1 个结点(k>0)
性质 3: 对于任意一棵二叉树,如果其叶结点数为 N0,而度数为 2 的结点总数为 N2,则 N0=N2+1;
性质 4: 具有 n 个结点的完全二叉树的深度必为 log2(n+1)
性质 5: 对完全二叉树,若从上至下、从左至右编号,则编号为 i 的结点,其左孩子编号必为 2i,其右孩子编号必为 2i+1;其双亲的编号必为 i/2(i=1 时为根, 除外)
- class Node(object):
- '''节点类'''
- def __init__(self, elem, lchild = None, rchild = None):
- self.elem = elem
- self.lchild = lchild
- self.rchild = rchild
- class Tree(object):
- '''树类'''
- def __init__(self, root = None):
- self.root = root
- def add(self, elem):
- '''为树添加节点'''
- node = Node(elem)
- # 如果是空树,对根节点进行赋值
- if self.root == None:
- self.root = node
- return
- else:
- queue = []
- queue.append(self.root)
- # 对已有节点进行层次遍历
- while queue:
- # 弹出队列的第一个元素
- cur = queue.pop(0)
- if cur.lchild is None:
- cur.lchild = node
- return
- elif cur.rchild is None:
- cur.rchild = node
- return
- else:
- # 如果左右节点不为空,加入队列继续判断
- queue.append(cur.lchild)
- queue.append(cur.rchild)
二叉树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次,我们把这种对所有节点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历, 深度优先一般用递归,广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
对于一颗二叉树,深度优先搜索 (Depth First Search) 是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。我们来给出它们的详细定义,然后举例看看它们的应用。
- def preorder(self, root):
- """递归实现先序遍历"""
- if root == None:
- return
- print(root.elem)
- self.preorder(root.lchild)
- self.preorder(root.rchild)
- def inorder(self, root):
- """递归实现中序遍历"""
- if root == None:
- return
- self.inorder(root.lchild)
- print(root.elem)
- self.inorder(root.rchild)
- def postorder(self, root):
- """递归实现后续遍历"""
- if root == None:
- return
- self.postorder(root.lchild)
- self.postorder(root.rchild)
- print (root.elem)
从树的 root 开始,从上到下从从左到右遍历整个树的节点
- def breadth_travel(self, root):
- """利用队列实现树的层次遍历"""
- if root == None:
- return
- queue = []
- queue.append(root)
- while queue:
- node = queue.pop(0)
- print (node.elem)
- if node.lchild != None:
- queue.append(node.lchild)
- if node.rchild != None:
- queue.append(node.rchild)
来源: http://www.bubuko.com/infodetail-2428608.html