用Python如何判断不同类型的二叉树

百变鹏仔 1天前 #Python

文章标签不同类型

二叉树是一种树状数据结构，其中每个父节点最多可以有两个子节点。

二叉树的类型

完全二叉树

完全二叉树是一种特殊类型的二叉树，其父节点存在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)

文章推荐