文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-01-23 14:24

关注

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

二叉树的类型

完全二叉树

完全二叉树是一种特殊类型的二叉树,其父节点存在2种情况,要么有2个子节点,要么没有子节点,详情如下图:

完全二叉树定理

1、叶数为i+1

2、节点总数为2i+1

3、内部节点数为(n–1)/2

4、叶数为(n+1)/2

5、节点总数为2l–1

6、内部节点数为l–1

7、叶子的数量最多2^λ-1

Python判断完整二叉树

class Node:
def __init__(self,item):
self.item=item
self.leftChild=None
self.rightChild=None
def isFullTree(root):
if root is None:
return True
if root.leftChild is None and root.rightChild is None:
return True
if root.leftChild is not None and root.rightChild is not None:
return(isFullTree(root.leftChild)and isFullTree(root.rightChild))
return False
root=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=k
self.right=self.left=None
def calculateDepth(node):
d=0
while(node is not None):
d+=1
node=node.left
return d
def is_perfect(root,d,level=0):
if(root is None):
return True
if(root.left is None and root.right is None):
return(d==level+1)
if(root.left is None or root.right is None):
return False
return(is_perfect(root.left,d,level+1)and
is_perfect(root.right,d,level+1))
root=None
root=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=data
self.left=self.right=None
class Height:
def __init__(self):
self.height=0
def isHeightBalanced(root,height):
left_height=Height()
right_height=Height()
if root is None:
return True
l=isHeightBalanced(root.left,left_height)
r=isHeightBalanced(root.right,right_height)
height.height=max(left_height.height,right_height.height)+1
if abs(left_height.height-right_height.height)<=1:
return l and r
return False
height=Height()
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
if isHeightBalanced(root,height):
print('The tree is balanced')
else:
print('The tree is not balanced')

以上就是用Python如何判断不同类型的二叉树的详细内容,更多请关注编程网其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯