机关网站建设工作总结,个人简历模板可编辑免费,使用wordpress快速建站视频教程,phpcmsv9中英文网站1#xff0c;利用类来构建结点#xff0c;利用函数递归来构建树2#xff0c;因为左子树的结点编号是父节点的2倍#xff0c;右子树的结点编号是父节点的2倍1#xff0c;所以可以用数组模拟建树的过程构建二叉树第一种构建方式class treenode():#二叉树节点def __init__(se…1利用类来构建结点利用函数递归来构建树2因为左子树的结点编号是父节点的2倍右子树的结点编号是父节点的2倍1所以可以用数组模拟建树的过程构建二叉树第一种构建方式class treenode():#二叉树节点def __init__(self,val,lchildNone,rchildNone):self.valval #二叉树的节点值self.lchildlchild #左孩子self.rchildrchild #右孩子def creat_tree(root,vals):if len(vals)0:#终止条件val用完了return rootif vals[0]!#:#本层需要干的就是构建root、root.lchild、root.rchild三个节点。root treenode(vals[0])vals.pop(0)root.lchild creat_tree(root.lchild,val)root.rchild creat_tree(root.rchild,val)return root#本次递归要返回给上一次的本层构造好的树的根节点else:rootNonevals.pop(0)return root#本次递归要返回给上一次的本层构造好的树的根节点if __name__ __main__:root Nonestrsabc##d##e###前序遍历扩展的二叉树序列vals list(strs)rootscreat_tree(root,vals)#roots就是我们要的二叉树的根节点。第二种构建方式#存储结构的创建
class node:def __init__(self,data):self.datadata#数据域self.leftNone#指向左子树根节点的指针self.rightNone#指向右子树根节点的指针
rootNone#如果根节点不存在l[1,2,None,3,5,2,1]#假设题目给出列表形式的二叉树各节点数据
def newNode(input_list[]):#创建二叉树即二叉树插入if input_list is None or len(input_list)0:#如果列表为空return Nonedatainput_list.pop(0)#取出并删除“当前”列表第一个数据if data is None:#到达空树递归边界return Nonerootnode(data)#将该数据设置为根节点的数据并创建此根节点的存储地址。root.leftnewNode(input_list)#该根节点的左节点为“当前”列表的第二个数据root.rightnewNode(input_list)#该根节点的右节点为“当前”列表的第三个数据#左右节点的递归顺序要根据题目给出的前中后层序排序改变。当前为前序遍历插入#中序遍历插入# root.leftnewNode(input_list)# root node(data)# root.rightnewNode(input_list)#后序遍历插入# root.leftnewNode(input_list)# root.rightnewNode(input_list)# rootnode(data)#层序遍历插入return root
newNode(l)二叉树的四种遍历#二叉树遍历
#前序遍历
#root是构建二叉树后得到的根结点
def preorder(root):if rootNone:return#到达空树递归边界print(root.data)#访问根节点preorder(root.left)#访问左子树preorder(root.right)#访问右子树
#中序遍历
def inorder(root):if rootNone:return#到达空树递归边界inorder(root.left) # 访问左子树print(root.data)#访问根节点inorder(root.right)#访问右子树
#后序遍历
def postorder(root):if rootNone:return#到达空树递归边界postorder(root.left)#访问左子树postorder(root.right)#访问右子树print(root.data) # 访问根节点
#层序遍历
from queue import Queue
def layerorder(root):qQueue()#注意队列里是存地址q.put(root)#将根节点地址入队while not q.empty():newrootq.get()#取出队首元素q.pop()print(newroot.data)#访问队首元素if newroot.left is not None:#左子树非空q.put(newroot.left)if newroot.right is not None:#右子树非空q.put(newroot.right)#二叉树结点的查找,修改
goaldata10#目标数据
newdata11#新的数据
def search(root,goaldata,newdata):#先传进根节点if rootNone:returnif root.datagoaldata:root.datanewdata# 再依次传进左右子节点search(root.left,goaldata,newdata)#往左子树搜索xsearch(root.right,goaldata,newdata)#往右子树搜素x二叉树题目其一已知两种遍历求其他所有遍历结论:中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树而后三者两两搭配或是三个一起上都无法构建唯一的二叉树。原因是先序、后序、层序均是提供根结点,作用是相同的,都必须由中序序列来区分出左右子树。L2-006 树的遍历已知中后求层序class node:def __init__(self,data):self.datadataself.leftNoneself.rightNonenint(input())
l1list(map(int,input().split()))
l2list(map(int,input().split()))def buildTree(inorder,postorder):def helper(in_left,in_right):if in_leftin_right:return Nonedatapostorder.pop()#后序排序从后依次弹出遵循根右左故一开始是根之后一直右然后左如何判断该节点是左右只需看in_leftin_right即可一旦in_leftin_right说明右已经没有开始进行左。rootnode(data)indexidx_map[data]root.right helper(index 1, in_right)#为什么root.right必须放在root.left上面在data是按后序排序逆序弹出#弹出根节点后就弹出右节点这个时候如果先遍历左子树会找不到左子树的根节点root.lefthelper(in_left,index-1)return rootidx_map{val:idx for idx,val in enumerate(inorder)}#将中序列表的值和下标对应return helper(0,len(inorder)-1)
pbuildTree(l2,l1)#得到的是一堆root数据结构的首地址也就是二叉树根节点的地址
# print(p)
q[p]#将首地址放到列表结构中
# print(q.pop(0))
res[]
while(len(q)!0):mq.pop(0)#取出首地址if m!None:res.append(m.data)if m.left!None:q.append(m.left)if m.right!None:q.append(m.right)
print(*res)L2-011 玩转二叉树已知前中镜像翻转后求层前序遍历倒过来就是后序遍历的镜像from queue import Queue
nint(input())
zxlist(map(int,input().split()))
qxlist(map(int,input().split()))class node():def __init__(self,data):self.datadataself.leftNoneself.rightNone
idx_map{val:i for i,val in enumerate(zx)}
def coms(inl,inr):if inlinr:return Nonedataqx.pop(0)#在前序中找到根节点#前序排序从前依次弹出遵循根左右故一开始是根之后一直左然后左如何判断该节点是左右只需看in_leftin_right即可一旦in_leftin_right说明左已经没有开始进行右。indexidx_map[data]#利用根节点的值找到其下标rootnode(data)#建立二叉树#再利用下标将其分开#l.append(data)前序遍历root.left coms(inl, index - 1)#l.append(data)中序遍历root.right coms(index 1, inr)# l.append(data)后序遍历return rootpcoms(0,len(zx)-1)#得到的是一堆root数据结构的首地址也就是二叉树根节点的地址
# print(p)
q[p]#将首地址放到列表结构中
# print(q.pop(0))
res[]
while(len(q)!0):mq.pop(0)#取出首地址if m!None:res.append(m.data)if m.right!None:q.append(m.right)if m.left!None:q.append(m.left)
print(*res)from queue import Queue
nint(input())
zxlist(map(int,input().split()))
qxlist(map(int,input().split()))class node():def __init__(self,data):self.datadataself.leftNoneself.rightNone
idx_map{val:i for i,val in enumerate(zx)}
def coms(inl,inr):if inlinr:return Nonedataqx.pop(0)#在前序中找到根节点indexidx_map[data]#利用根节点的值找到其下标rootnode(data)#建立二叉树#再利用下标将其分开#l.append(data)前序遍历root.left coms(inl, index - 1)#l.append(data)中序遍历root.right coms(index 1, inr)# l.append(data)后序遍历return root
l[]
def level(node):queueQueue()queue.put(node)while not queue.empty():nodequeue.get()l.append(node.data)if node.right is not None:#先加入右节点做镜像翻转queue.put(node.right)if node.left is not None:queue.put(node.left)
level(coms(0,len(zx)-1))
print(*l)L2-035 完全二叉树的层序遍历由于树是递归实现的后序排序符合递归顺序而层序排序的顺序可以为我们提供每一次递归所满足的代数式。nint(input())
llist(map(int,input().split()))
tree[0]*n
def dfs(x):global indexif xn:returndfs(x*2)dfs(x*21)tree[x-1]l[index]index1
index0
dfs(1)
print(*tree)二叉搜素树(BST)二叉查找树一个实用的性质对二叉查找树进行中序遍历遍历的结果是有序的。这是由于二叉查找树本身的定义中就包含了左子树根结点右子树的特点而中序遍历的访问顺序也是左子树→根结点→右子树,因此,所得到的中序遍历序列是有序的。# -*- coding:utf-8 -*-import sysreload(sys)
sys.setdefaultencoding(utf-8)class BSTNode:定义一个二叉树节点类。以讨论算法为主忽略了一些诸如对数据类型进行判断的问题。def __init__(self, data, leftNone, rightNone):初始化:param data: 节点储存的数据:param left: 节点左子树:param right: 节点右子树self.data dataself.left leftself.right rightclass BinarySortTree:基于BSTNode类的二叉排序树。维护一个根节点的指针。def __init__(self):self._root Nonedef is_empty(self):return self._root is Nonedef search(self, key):关键码检索:param key: 关键码:return: 查询节点或Nonebt self._rootwhile bt:entry bt.dataif key entry:bt bt.leftelif key entry:bt bt.rightelse:return entryreturn Nonedef insert(self, key):插入操作:param key:关键码:return: 布尔值if self.is_empty():self._root BSTNode(key)bt self._rootwhile True:entry bt.dataif key entry:if bt.left is None:bt.left BSTNode(key)bt bt.leftelif key entry:if bt.right is None:bt.right BSTNode(key)bt bt.rightelse:bt.data keyreturndef delete(self, key):二叉排序树最复杂的方法:param key: 关键码:return: 布尔值p, q None, self._root # 维持p为q的父节点用于后面的链接操作if not q:print(空树)returnwhile q and q.data ! key:p qif key q.data:q q.leftelse:q q.rightif not q: # 当树中没有关键码key时结束退出。return# 上面已将找到了要删除的节点用q引用。而p则是q的父节点或者Noneq为根节点时。if not q.left:if p is None:self._root q.rightelif q is p.left:p.left q.rightelse:p.right q.rightreturn# 查找节点q的左子树的最右节点将q的右子树链接为该节点的右子树# 该方法可能会增大树的深度效率并不算高。可以设计其它的方法。r q.leftwhile r.right:r r.rightr.right q.rightif p is None:self._root q.leftelif p.left is q:p.left q.leftelse:p.right q.leftdef _pre_order(self, nodeNone):if node is None:node self._rootyield node.dataif node.left is not None:for item in self._pre_order(node.left):yield itemif node.right is not None:for item in self._pre_order(node.right):yield itemdef _mid_order(self, nodeNone):if node is None:node self._rootif node.left is not None:for item in self._mid_order(node.left):yield itemyield node.dataif node.right is not None:for item in self._mid_order(node.right):yield itemdef _mid_order1(self):实现二叉树的中序遍历算法,展示我们创建的二叉排序树.直接使用python内置的列表作为一个栈。:return: datastack []node self._rootwhile node or stack:while node:stack.append(node)node node.leftnode stack.pop()yield node.datanode node.rightdef _post_order(self, nodeNone):if node is None:node self._rootif node.left is not None:for item in self._post_order(node.left):yield itemif node.right is not None:for item in self._post_order(node.right):yield itemyield node.datadef pre_order(self):return list(self._pre_order())def mid_order(self):return list(self._mid_order()) # return list(self._mid_order1())def post_order(self):return list(self._post_order())if __name__ __main__:lis [62, 58, 88, 47, 73, 99, 35, 51, 93, 37]bs_tree BinarySortTree()for i in range(len(lis)):bs_tree.insert(lis[i])print 先序遍历, bs_tree.pre_order()print 中序遍历, bs_tree.mid_order()print 后序遍历, bs_tree.post_order()L3-010 是否完全二叉搜索树因为左子树的结点编号是父节点的2倍右子树的结点编号是父节点的2倍1所以可以用数组模拟建树的过程;最后题目要求层序输出比较简单直接按编号大小输出即可;还有一问是判断该树是否为完全二叉树完全二叉树的定义是若设二叉树的深度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第 h 层所有的结点都连续集中在最左边所以最后的结点编号肯定和n是相等的。
