二叉树是一种树状数据结构，其中每个父节点最多可以有两个子节点。
二叉树的类型
完全二叉树
完全二叉树是一种特殊类型的二叉树，其父节点存在2种情况，要么有2个子节点，要么没有子节点，详情如下图：
完全二叉树定理
1、叶数为i+1
2、节点总数为2i+1
3、内部节点数为(n–1)/2
立即学习“Python免费学习笔记（深入）”；
4、叶数为(n+1)/2
5、节点总数为2l–1
6、内部节点数为l–1
7、叶子的数量最多2^λ-1
Python判断完整二叉树
class Node:def __init__(self,item):self.item=itemself.leftChild=Noneself.rightChild=Nonedef isFullTree(root):if root is None:return Trueif root.leftChild is None and root.rightChild is None:return Trueif root.leftChild is not None and root.rightChild is not None:return(isFullTree(root.leftChild)and isFullTree(root.rightChild))return Falseroot=Node(1)root.rightChild=Node(3)root.leftChild=Node(2)root.leftChild.leftChild=Node(4)root.leftChild.rightChild=Node(5)root.leftChild.rightChild.leftChild=Node(6)root.leftChild.rightChild.rightChild=Node(7)if isFullTree(root):print("The tree is a full binary tree")else:print("The tree is not a full binary tree")
登录后复制
完美二叉树
完美二叉树的每个内部节点都恰好有两个子节点，并且所有叶节点都在同一级别，如下图：
完美二叉树定理
1、高度为h的完美二叉树有2^(h+1)–1个节点
2、具有n个节点的完美二叉树的高度为log(n+1)–1=Θ(ln(n))。
3、高度为h的完美二叉树具有2^h节点
4、完美二叉树中节点的平均深度为Θ(ln(n))。
Python判断完美二叉树
class newNode:def __init__(self,k):self.key=kself.right=self.left=Nonedef calculateDepth(node):d=0while(node is not None):d+=1node=node.leftreturn ddef is_perfect(root,d,level=0):if(root is None):return Trueif(root.left is None and root.right is None):return(d==level+1)if(root.left is None or root.right is None):return Falsereturn(is_perfect(root.left,d,level+1)andis_perfect(root.right,d,level+1))root=Noneroot=newNode(1)root.left=newNode(2)root.right=newNode(3)root.left.left=newNode(4)root.left.right=newNode(5)if(is_perfect(root,calculateDepth(root))):print("The tree is a perfect binary tree")else:print("The tree is not a perfect binary tree")
登录后复制
退化或病态树
退化或病态树只具有左或右单个子节点的二叉树，如下图：
斜二叉树
倾斜二叉树要么由左节点支配，要么由右节点支配。因此，有左二叉树和右二叉树两种类型，如下图：
平衡二叉树
平衡二叉树每个节点的左子树和右子树的高度之差为0或1，如下图：
Python判断平衡二叉树
class Node:def __init__(self,data):self.data=dataself.left=self.right=Noneclass Height:def __init__(self):self.height=0def isHeightBalanced(root,height):left_height=Height()right_height=Height()if root is None:return Truel=isHeightBalanced(root.left,left_height)r=isHeightBalanced(root.right,right_height)height.height=max(left_height.height,right_height.height)+1if abs(left_height.height-right_height.height)
登录后复制
以上就是用Python如何判断不同类型的二叉树的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2212883.html
