ホームページ > バックエンド開発 > Python チュートリアル > Python を使用してさまざまな種類のバイナリ ツリーを判断する方法

Python を使用してさまざまな種類のバイナリ ツリーを判断する方法

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
リリース: 2024-01-23 10:06:06
転載
1228 人が閲覧しました

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

二叉树类型说明 如何使用python判断不同类型二叉树

二叉树的类型

完全二叉树

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

二叉树类型说明 如何使用python判断不同类型二叉树

完全二叉树定理

1、叶数为i+1

2、节点总数为2i+1

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

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

5、节点总数为2l–1

6、内部节点数为l–1

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

Python判断完整二叉树

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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")

ログイン後にコピー

完美二叉树

完美二叉树的每个内部节点都恰好有两个子节点,并且所有叶节点都在同一级别,如下图:

二叉树类型说明 如何使用python判断不同类型二叉树

完美二叉树定理

1、高度为h的完美二叉树有2^(h+1)–1个节点

2、具有n个节点的完美二叉树的高度为log(n+1)–1=Θ(ln(n))。

3、高度为h的完美二叉树具有2^h节点

4、完美二叉树中节点的平均深度为Θ(ln(n))。

Python判断完美二叉树

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

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")

ログイン後にコピー

退化或病态树

退化或病态树只具有左或右单个子节点的二叉树,如下图:

二叉树类型说明 如何使用python判断不同类型二叉树

斜二叉树

倾斜二叉树要么由左节点支配,要么由右节点支配。因此,有左二叉树和右二叉树两种类型,如下图:

二叉树类型说明 如何使用python判断不同类型二叉树

平衡二叉树

平衡二叉树每个节点的左子树和右子树的高度之差为0或1,如下图:

二叉树类型说明 如何使用python判断不同类型二叉树

Python判断平衡二叉树

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

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 を使用してさまざまな種類のバイナリ ツリーを判断する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート