建设个人博客网站,wordpress xss跨站脚本漏洞,网站建设营销词,图书馆网站建设工作总结数据结构与算法#xff1a;二叉树专题前言前提条件基础知识二叉树链式存储结构二叉树中序遍历二叉树层序遍历常见编程题把一个有序整数数组放到二叉树中逐层打印二叉树结点数据求一棵二叉树的最大子树和判断两棵二叉树是否相等把二叉树转换为双向链表判断一个数组是否是二元查…
数据结构与算法二叉树专题前言前提条件基础知识二叉树链式存储结构二叉树中序遍历二叉树层序遍历常见编程题把一个有序整数数组放到二叉树中逐层打印二叉树结点数据求一棵二叉树的最大子树和判断两棵二叉树是否相等把二叉树转换为双向链表判断一个数组是否是二元查找树后序遍历的序列找出排序二叉树上任意两个结点的最近共同父结点复制二叉树二叉树进行镜像反转在二叉排序树中找出第一个大于中间值的结点前言 本文是个人学习笔记由于水平有限难免出现错漏敬请批评改正。更多精彩内容可点击进入数据结构与算法专栏或我的个人主页查看 前提条件 熟悉Python熟悉数据结构与算法 基础知识 二叉树(BinaryTree)也称为二分树、二元树、对分树等它是 n(n≥0)个有限元素的集合该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时称该二叉树为空二叉树。在二叉树中一个元素也称作一个结点。二叉树的递归定义为:二叉树或者是一棵空树或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树左子树和右子树又同样都是一棵二叉树。二叉树的基本概念:(1)结点的度。结点所拥有的子树的个数称为该结点的度。(2)叶子结点。度为0的结点称为叶子结点或者称为终端结点。(3)分支结点。度不为0的结点称为分支结点或者称为非终端结点。一棵树的结点除叶子结点外其余的都是分支结点。(4)左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。(5)路径、路径长度。如果一棵树的一串结点 n1,n2,…,nk 有如下关系:结点 ni 是 ni1的父结点(1≤i≤k),就把n1,n2,…,nk称为一条由n1到nk的路径长度是k-1。(6)祖先、子孙。在树中如果有一条路径从结点M到结点N那么M就称为N的祖先而N称为M的子孙。(7)结点的层数。规定树的根结点的层数为1其余结点的层数等于它的双亲结点的层数加1。(8)树的深度。树中所有结点的最大层数称为树的深度。(9)树的度。树中各结点度的最大值称为该树的度叶子结点的度为0。(10)满二叉树。在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子结点都在同一层上这样的一棵二叉树称作满二叉树。完全二叉树。一棵深度为k的有n个结点的二叉树对树中的结点按从上至下、从左到右的顺序进行编号如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同则这棵二叉树称为完全二叉树。完全二叉树的特点是:叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左部。需要注意的是满二叉树肯定是完全二叉树而完全二叉树不一定是满二叉树。二叉树的基本性质如下所示:性质1:一棵非空二叉树的第i层上最多有2i−12^{i-1}2i−1个结点(i≥1)。性质2:一棵深度为k的二叉树中最多具有2k−12^{k}-12k−1个结点最少有k个结点。性质3:对于一棵非空的二叉树度为0的结点(即叶子结点)总是比度为2的结点多一个即如果叶子结点数为 n0度数为 2的结点数为 n2则有 n0n21。性质4:具有n个结点的完全二叉树的深度为「log2n」1「log_2n」1「log2n」1。性质5:对于具有n个结点的完全二叉树如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号则对于任意的序号为i的结点有: (1)如果i1则序号为i的结点的双亲结点的序号为i/2(“/”表示整除);如果i1则序号为i的结点是根结点,无双亲结点。(2)如果2i≤n,则序号为i的结点的左孩子结点的序号为2i;如果2in,则序号为i的结点无左孩子。(3)如果2i1≤n,则序号为i的结点的右孩子结点的序号为2i1;如果2i1n则序号为i的结点无右孩子。 此外,若对二叉树的根结点从0开始编号,则相应的i号结点的双亲结点的编号为(i-1)/2,左孩子的编号为2i1右孩子的编号为2i2。 二叉树链式存储结构
class BiTNode:def __init__(self):self.data Noneself.lchild Noneself.rchild None二叉树中序遍历
# 用中序遍历的方式打印出二叉树结点的内容
def printTreeMidOrdel(root):if root None:returnif root.lchild!None:printTreeMidOrdel(root.lchild)print(root.data,end )if root.rchild!None:printTreeMidOrdel(root.rchild)二叉树层序遍历
def printTreeLayer(root):if root None:returnqueue deque()queue.append(root)while len(queue)0:p queue.popleft()print(p.data,end )if p.lchild !None:queue.append(p.lchild)if p.rchild !None:queue.append(p.rchild)常见编程题
把一个有序整数数组放到二叉树中 题目把一个有序的整数数组放到二叉树中。实现思路首先取数组的中间结点作为二叉树的根结点,把数组分成左右两部分,然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建,例如,对于左半部分子数组,取中间结点作为树的根结点,再把子数组分成左右两部分。依此类推,就可以完成二叉树的构建。 # 把有序数组转换为二叉树
def array2tree(arr,start,end):root Noneif endstart:root BiTNode()mid (startend1)//2# print(mid)# 树的根结点为数组中间的元素root.data arr[mid]# 递归的用左半部分数组构造 root 的左子树root.lchild array2tree(arr,start,mid-1)# 递归的用右半部分数组构造 root 的右子树root.rchild array2tree(arr,mid1,end)else:root Nonereturn rootif __name__ __main__:arr [1,2,3,4,5,6,7,8,9,10]print(数组:,arr)root array2tree(arr,0,len(arr)-1)print(数组转换成树的中序遍历:,end )printTreeMidOrdel(root) # 只遍历了一次数组时间复杂度为O(N),数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
数组转换成树的中序遍历: 1 2 3 4 5 6 7 8 9 10 只遍历了一次数组,因此,算法的时间复杂度为O(N)。 逐层打印二叉树结点数据 题目给定一棵二叉树,要求逐层打印二叉树结点的数据。实现思路要求在遍历 一个结点的同时记录下它的孩子结点的信息,然后按照这个记录的顺序来访问结点的数据,在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点,从而实现二叉树的层序遍历。 from collections import deque
# 逐层打印二叉树结点数据,层次遍历借助队列
def printTreeLayer(root):if root None:returnqueue deque()# 树根结点进队列queue.append(root)while len(queue)0:p queue.popleft()# 访问当前结点print(p.data,end )# 如果这个结点的左孩子不为空则入队列if p.lchild !None:queue.append(p.lchild)# 如果这个结点的右孩子不为空则入队列if p.rchild !None:queue.append(p.rchild)if __name__ __main__:arr [1,2,3,4,5,6,7,8,9,10]print(数组: ,arr)# 有序数组放到二叉树中root array2tree(arr,0,len(arr)-1)# 层序遍历print(逐层打印二叉树结点数据:,end )printTreeLayer(root)数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
逐层打印二叉树结点数据: 6 3 9 2 5 8 10 1 4 7 在二叉树的层序遍历过程中,对树中的各个结点只进行了一次访问,因此,时间复杂度为O(N),此外,这种方法还使用了队列来保存遍历的中间结点,所使用队列的大小取决于二叉树中每一层 中结点个数的最大值 。具有 N 个结点的完全二叉树的深度为 hlog2N1hlog_2N1hlog2N1 。而深度为 h 的这一层最多的结点个数为 2h−1n/22^{h-1}n/22h−1n/2 。 也就是说队列中可能的最多的结点个数为 N/2 。因此,这种算法的空间复杂度为O(N) 。 求一棵二叉树的最大子树和 题目给定一棵二叉树,它的每个结点都是正整数或负整数,如何找到一棵子树,使得它所有结点的和最大?实现思路针对每棵子树,求出这棵子树中所有结点的和,然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中,如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值,则更新最大值。 # 最大子树和,借助后序遍历
class Test:def __init__(self):self.maxSum -2**31 # 定义一个maxSum用于存储最大和def findMaxSubTree(self,root,maxRoot):if rootNone:return 0# 求 root 左子树所有结点的和lmax self.findMaxSubTree(root.lchild,maxRoot)# 求 root 右子树所有结点的和rmax self.findMaxSubTree(root.rchild,maxRoot)sums lmaxrmaxroot.data# 以 root 为根的子树的和大于前面求出的最大值if sums self.maxSum:self.maxSum sumsmaxRoot.data root.data# 返回以 root 为根结点的子树的所有结点的和return sumsif __name__ __main__:arr [1,2,3,4,5,6,7,8,9,10]print(数组: ,arr)# 有序数组放到二叉树中root array2tree(arr,0,len(arr)-1)# 层序遍历print(逐层打印二叉树结点数据:,end )printTreeLayer(root) print()test Test()maxRoot BiTNode()test.findMaxSubTree(root,maxRoot)print(最大子树和:,test.maxSum)print(最大子树根结点:,maxRoot.data)数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
逐层打印二叉树结点数据: 6 3 9 2 5 8 10 1 4 7
最大子树和: 55
最大子树根结点: 6时间复杂度为O(N),其中, N为二叉树的结点个数。 判断两棵二叉树是否相等 题目两棵二叉树相等是指这两棵二 叉树有着相同的结构 ,并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等?实现思路两棵二叉树 root1 、 root2 相等,那么 root1 与 root2 结点 的值相同,同时它们的左右孩子也有着相同的结构,并且对应位置上结点的值相等,即 root1.dataroot2.data , 并且 root1的左子树与 root2 的左子树相等, root1 的右子树与 root2 的 右子树相等。根据这个条件,可以使用递归算法实现。 ## 判断两颗二叉树是否相等
def isEqual(root1,root2):if root1None and root2None:return Trueif root1!None and root2None:return Falseif root1None and root2!None:return Falseif root1.data root2.data:return isEqual(root1.lchild,root2.lchild) and isEqual(root1.rchild,root2.rchild)else:return Falseif __name__ __main__:arr1 [1,2,3,4,5,6,7,8,9,10]print(数组: ,arr)# 有序数组放到二叉树中root1 array2tree(arr1,0,len(arr1)-1)arr2 [1,2,3,4,5,6,7,8,9,10]# 有序数组放到二叉树中root2 array2tree(arr,0,len(arr2)-1)equalisEqual(root1,root2)if equal:print(两棵树相等)else:print(两棵树不相等)数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
两棵树相等只对两棵树进行了一次遍历,因此 ,时向复杂度为O(N)。此外,这种方法没有申请额外的存储空间 。 把二叉树转换为双向链表 题目输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整结点的指向。实现思路转换后的双向链表 中结点的顺序与二叉树的中序遍历的顺序相同,因此,可以对二叉树的中序遍历算法进行修改,通过在中序遍历的过程中修改结点的指向来转换成一个排序的双向链表。 假设当前遍历的结点为 root , root 的 左子树已经被转换为双向链表,使用两个变量 pHead 与 pEnd 分别指向链表的头结点与尾结点。 那么在遍历 root 结点的时候,只需要将 root 结点的 lchild (左)指 向 pEnd ,把pEnd的 rchild (右)指向 root;此时root 结点就被加入到双向链表里 了,因此, root 变成了双向链表的尾结点。对于所有的结点都可以通过同样的方法来修改结点的指向。因此 ,可以采用递归的方法来求解,在求解的时候需要特别注意递归的结束条件以及边界情况 (例如双向链表为空的时候) 。 # 二叉树转换为双向链表中序遍历
class Test:def __init__(self):self.pHead None # 双向链表头结点self.pEnd None # 双向链表尾结点# 把二叉树转换为双向列表def inOrderBSTree(self,root):if root None:return# 转换 root 的左子树self.inOrderBSTree(root.lchild) root.lchildself.pEnd # 使当前结点的左孩子指向双向链表中最后一个结点if None self.pEnd: # 双向列表为空,当前遍历的结点为双向链表的头结点self.pHeadrootelse: # 使双向链表中最后一个结点的右孩子指向当前结点self.pEnd.rchildrootself.pEndroot # 将当前结点设为双向链表中最后一个结点# #转换 root 的右子树self.inOrderBSTree(root.rchild)if __name____main__:arr [1,2,3,4,5,6,7]print(数组:,arr)testTest()root array2tree(arr,0,len(arr)-1)test.inOrderBSTree(root)print(转换后双向链表正向遍历:,end )cur test.pHeadwhile cur!None:print(cur.data,end )curcur.rchildprint()print(转换后双向链表逆向遍历:,end )cur test.pEndwhile cur!None:print(cur.data,end )curcur.lchild数组: [1, 2, 3, 4, 5, 6, 7]
转换后双向链表正向遍历: 1 2 3 4 5 6 7
转换后双向链表逆向遍历: 7 6 5 4 3 2 1 二叉树的中序遍历有着相同的时间复杂度 O(N)。此外,这种方法只用了两个额外的变量 pHead 与 pEnd 来记录双向链表的首尾结点,因此,空间复杂度为 0(1)。 判断一个数组是否是二元查找树后序遍历的序列 题目输入一个整数数组,判断该数组是否是某二元查找树的后序遍历的结果。如果是,那么返回 true ,否则返回 false 。实现思路二元查找树的特点是:对于任意一个结点,它的左子树上所有结点的值都小于这个结点的值,它的右子树上所有结点的值都大于这个结点的值。根据这个特点以及二元查找树后序遍历的特点,可以看出,这个序列的最后一个元素一定是树的根结点,然后在数组中找到第一个大于根结点的值,那么第一个大于根结点的结点之前的序列对应的结点一定位于根结点的左子树上,第一个大于根结点的结点(包含这个结点〉后面的序列一定位于根结点的右子树上,因此,可以通过递归方法来实现。 # 判断是否二元查找树的后序遍历
def IsAfterOrder(arr,start,end):if arrNone:return False# 数组的最后一个结点必定是根结点root arr[end]# 找到第一个大于 root 的值,那么前面所有的结点都位于 root 的左子树上istartwhile iend:if arr[i]root:breaki1# 如果序列是后续遍历的序列 , 那么从 i 开始的所有值都严该大于根结点 root 的值jiwhile jend:if arr[j]root:return Falsej1left_IsAfterOrderTrueright_IsAfterOrderTrue# 判断小于 root 值的序列是否是某一二元查找树的后续遍历if istart:left_IsAfterOrderIsAfterOrder(arr,start,i-1)# 判断大于 root 值的序列是否是某一二元查找树的后续遍历if jend:right_IsAfterOrderIsAfterOrder(arr,i,end)return left_IsAfterOrder and right_IsAfterOrderif __name____main__:
# arr [1,2,3,4,5,6,7]arr [1,3,2,5,7,6,4]print(数组:,arr)res IsAfterOrder(arr,0,len(arr)-1)if res:print(是二元查找树的后序遍历)else:print(不是二元查找树的后序遍历)
数组: [1, 3, 2, 5, 7, 6, 4]
是二元查找树的后序遍历只对数组进行了一次遍历,因此,时间复杂度O(N)。 找出排序二叉树上任意两个结点的最近共同父结点 题目对于一棵给定的排序二叉树, 求两个结点 的共同父结点。实现思路对于一棵二叉树的两个结点, 如果知道了从根结点到这两个结点的路径, 就可以很容易地找出它们最近的 公共父结点 。因此, 可以首先分别找出从根结点到这两个结点的路径然后遍历这两条路径,只要是相等的结点都是它们的父结点,找到最后一个相等的结点即为离它们最近的共同父结点。 # 任意两个结点的最近共同父结点
class stack:# 初始栈def __init__(self):self.items []# 判断校是否为空def isEmpty(self):return len(self.items)0# 返回校的大小def size(self):return len(self.items)# 返回栈顶元素def peek(self):if not self.isEmpty():return self.items[len(self.items)-1]else:return None# 出栈def pop(self):if len(self.items)0:return self.items.pop()else:print(栈为空)return None# 入栈def push(self,item):self.items.append(item)# 获取二叉树从根结点 root 到 node 结点的路径
def getPathFromRoot(root,node,stack):if rootNone:return Falseif root node:stack.push(root)return True# 如果 node 结点在 root 结点的左子树或右子树上,那么 root 就是 node 的祖先结点,把它加到校里if getPathFromRoot(root.lchild,node,stack) or getPathFromRoot(root.rchild,node,stack):stack.push(root)return Truereturn False# 查找二叉树中两个结点最近的共同父结点
def FindParentNode(root,node1,node2):stack1 stack() # 保存从 root 到 node1 的路径stack2 stack() # 保存从 root 到 node2 的路径getPathFromRoot(root,node1,stack1) # 获取从 root 到 node !的路径getPathFromRoot(root,node2,stack2) # 获取从 root 到 node2 的路径commomParent Noneprint(stack1:,[i.data for i in stack1.items])print(stack2:,[i.data for i in stack2.items])# 获取最近 node1 和 node2 的父结点while stack1.peek()stack2.peek():commomParent stack1.peek()stack1.pop()stack2.pop()return commomParentif __name____main__:arr [1,2,3,4,5,6,7,8,9,10]print(数组:,arr)root array2tree(arr,0,len(arr)-1)node1root.lchild.lchild.lchildnode2 root.lchild.rchildres NoneresFindParentNode(root, node1, node2)if res!None:print(str(node1.data)和str(node2.data)的最近公共父结点为:str(res.data))else:print(没有公共父结点)数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
stack1: [1, 2, 3, 6]
stack2: [5, 3, 6]
1和5的最近公共父结点为:3当获取二叉树从根结点 root 到 node 结点的路径时,最坏的情况就是把树中所有结点都遍历了一遍,这个操作的时间复杂度为O(N),再分别找出从根结点到两个结点的路径后,找它们最近的公共父结点的 时间 复杂度也为O(N),因此,这种方法的时间复杂度为O(N)。此外,这种方法用战保存了从根结点到特定结点的路径,在最坏的情况下,这个路径包含了树中所有的结点,因此,空间复杂度也为O(N)。 复制二叉树 题目给定一个二叉树根结点,复制该树,返回新建树的根结点 。实现思路用给定的二叉树的根结点 root 来构造新的 二叉树的方法为:首先创建新的结点 dupTree,然后根据 root 结点来构造 dupTree 结点(dupTree.dataroot.data), 最后分别用 root 的左右子树来构造 dupTree 的左右子树 。 根据这个思路可以使用递归方式实现二叉树的复制。 # 复制二叉树
# 任意两个结点的最近共同父结点
def createDupTree(root):if rootNone:return NonedupTree BiTNode()dupTree.dataroot.data# 复制左子树dupTree.lchildcreateDupTree(root.lchild)# 复制左子树dupTree.rchildcreateDupTree(root.rchild)return dupTreeif __name____main__:arr [1,2,3,4,5,6,7,8,9,10]print(数组:,arr)root1 array2tree(arr,0,len(arr)-1)# root2 root1root2 createDupTree(root1)print(原始二叉树中序遍历:,end )printTreeMidOrdel(root1)print()print(复制二叉树中序遍历:,end )printTreeMidOrdel(root2)数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
原始二叉树中序遍历: 1 2 3 4 5 6 7 8 9 10
复制二叉树中序遍历: 1 2 3 4 5 6 7 8 9 10 对给定的二叉树进行了一次遍历,因此,时间复杂度为0(N),此外,这种方法需要申请N个额外的存储空间来存储新的二叉树 。 二叉树进行镜像反转 题目二叉树的镜像就是二叉树对称的二叉树就是交换每一个非叶子结点的左子树指针和右子树指针。注意 : 请勿对该树做任何假设,它不一定是平衡树 ,也不一定有序。实现思路要实现二叉树的镜像反转,只需交换二叉树中所有结点的左右孩子即可。由于对所有的结点都做了同样的操作,因此,可以用递归的方法来实现。 # 二叉树镜像反转
def reverseTree(root):if root None:returnreverseTree(root.lchild)reverseTree(root.rchild)tmp root.lchildroot.lchildroot.rchildroot.rchild tmpif __name__ __main__:arr [1,2,3,4,5,6,7]print(数组: ,arr)# 有序数组放到二叉树中root array2tree(arr,0,len(arr)-1)# 层序遍历print(原始二叉树层序遍历:,end )printTreeLayer(root)reverseTree(root)print()print(翻转二叉树层序遍历:,end )printTreeLayer(root)数组: [1, 2, 3, 4, 5, 6, 7]
原始二叉树层序遍历: 4 2 6 1 3 5 7
翻转二叉树层序遍历: 4 6 2 7 5 3 1 对二叉树进行了一次遍历, 因此,时间复杂度为O(N)。 在二叉排序树中找出第一个大于中间值的结点 题目对于一棵二叉排序树 , 令mid(最大值最小值)/2 , 设计一个算法,找出距离mid值最近、大于mid值的结点 。实现思路首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是:对于任意一个结点 ,它的左子树上所有结点的值都小于这个结点的值,它的右子树上所有结点的值都大于这个结点的值。因此,在二叉排序树中,最小值一定是最左下的结点,最大值一定是最右下的结点。根据最大值与最小值很容易就可以求出mid的值。接着对二叉树进行中序遍历。如果当前结点的值小于mid,那么在这个结点的右子树中接着遍历,否则遍历这个结点的左子树。 # 查找值最小的 结点
def getMinNode(root):if rootNone:return rootwhile root.lchild!None:rootroot.lchildreturn root# 查找值最大的结点
def getMaxNode(root):if rootNone:return rootwhile root.rchild!None:rootroot.rchildreturn rootdef getNode(root):maxNodegetMaxNode(root)minNodegetMinNode(root)mid(maxNode.dataminNode.data)/2res Nonewhile root!None:# 当前结点的值不大于mid则在右子树上找if root.datamid:rootroot.rchildelse: # 在左子树上找res rootrootroot.lchildreturn resif __name__ __main__:arr [1,2,3,4,5,6,7]print(数组: ,arr)# 有序数组放到二叉树中root array2tree(arr,0,len(arr)-1)print(第一个大于中间值的结点,getNode(root).data)数组: [1, 2, 3, 4, 5, 6, 7]
第一个大于中间值的结点 5在查找最大结点与最小结点时的时间复杂度为O(h), h为二叉树的高度 ,对于有N个结点的二叉排序树,最大的高度为O(N),最小的高度为 O(log2N)O(log_2N)O(log2N)。同理,在查找满足条件的结点的时候,时间复杂度也是O(h)。综上所述,这种方法的时间复杂度在最好的情况下是O(logN),最坏的情况下为O(N) 。 更多精彩内容可点击进入数据结构与算法专栏或我的个人主页查看
