策划书的网站,wap网站源代码,惠州网站seo排名优化,设计说明书范文介绍#xff1a;树形结构是应用相当广泛的一种非线性结构#xff0c;建立与应用大多使用链表来处理#xff0c;当然也可用连续的列表来实现常见概念#xff1a;满二叉树#xff1a;如果树高位H#xff0c;树的结点总数为2*H-1#xff0c;H0,称为满二叉树完全二叉树树形结构是应用相当广泛的一种非线性结构建立与应用大多使用链表来处理当然也可用连续的列表来实现常见概念满二叉树如果树高位H树的结点总数为2*H-1H0,称为满二叉树完全二叉树高度为H节点数小于2*H-1但节点的编号方式与满二叉树一致斜二叉树当一个二叉树完全没有左节点或者右节点的时候称为左斜二叉树或者右斜二叉树严格二叉树每一个非终端的节点均有非空的左右子树1.用数组实现二叉树规则左子树的节点索引值是父节点索引值乘2右子树的节点索引值是父节点索引值乘2加1每一个树根的值大于左子树值小于友子树值创建函数defBetree(betree,data,length):for i in range(1,length):level 1while betree[level] !0:if betree[level] data[i]:level level*2else:level level*21betree[level]data[i]return betree2.链表实现二叉树有点节点的增加和删除容易实现缺点很难找到父节点classtree:def __init__(self):self.data0self.leftNoneself.rightNonedef creat_tree(root,val):newnodetree()newnode.datavalnewnode.leftNonenewnode.rightNoneif rootNone:rootnewnodereturn rootelse:currentrootwhile current ! None:backup currentif current.data val:currentcurrent.leftelse:currentcurrent.rightif backup.data val:backup.left newnodeelse:backup.right newnode3.二叉树遍历三种遍历方法#中序遍历definorder(ptr):if ptr !None:inorder(ptr.left)print(%4d%ptr.data,end)inorder(ptr.right)print()#后序遍历defpostorder(ptr):if ptr !None:postorder(ptr.left)postorder(ptr.right)print(%4d%ptr.data,end)print()#前序遍历defpreorder(ptr):if ptr !None:print(%4d%ptr.data,end)preorder(ptr.left)preorder(ptr.right)4.二叉树节点查找原则从树根出发进行比较如果小于树根左子树查找大于树根右子树查找找到要查找的值defsearch(ptr,val):whileTrue:if ptr None:returnNoneif ptr.data val:returnptrelse:if ptr.data val:ptrptr.leftelse:ptr ptr.right5.二叉树节点的删除a.删除的节点位叶子只需将与其相连的父节点指向Noneb.删除节点只有一棵子树将其子树移到该节点的父节点指向c.删除节点有左右两个子树将左右子树中值较大的子树移到该结点处
