Python/data_structures/binary_tree/basic_binary_tree.py at master · TheAlgorithms/Python · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from __future__ importannotations

fromcollections.abcimportIterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
left: Node|None=None
right: Node|None=None

def__iter__(self) ->Iterator[int]:
ifself.left:
yieldfromself.left
yieldself.data
ifself.right:
yieldfromself.right

def__len__(self) ->int:
returnsum(1for_inself)

defis_full(self) ->bool:
ifnotselfor (notself.leftandnotself.right):
returnTrue
ifself.leftandself.right:
returnself.left.is_full() andself.right.is_full()
returnFalse


@dataclass
classBinaryTree:
root: Node

def__iter__(self) ->Iterator[int]:
returniter(self.root)

def__len__(self) ->int:
returnlen(self.root)

@classmethod
defsmall_tree(cls) ->BinaryTree:
"""
 Return a small binary tree with 3 nodes.
 >>> binary_tree = BinaryTree.small_tree()
 >>> len(binary_tree)
 3
 >>> list(binary_tree)
 [1, 2, 3]
 """
binary_tree=BinaryTree(Node(2))
binary_tree.root.left=Node(1)
binary_tree.root.right=Node(3)
returnbinary_tree

@classmethod
defmedium_tree(cls) ->BinaryTree:
"""
 Return a medium binary tree with 3 nodes.
 >>> binary_tree = BinaryTree.medium_tree()
 >>> len(binary_tree)
 7
 >>> list(binary_tree)
 [1, 2, 3, 4, 5, 6, 7]
 """
binary_tree=BinaryTree(Node(4))
binary_tree.root.left=two=Node(2)
two.left=Node(1)
two.right=Node(3)
binary_tree.root.right=five=Node(5)
five.right=six=Node(6)
six.right=Node(7)
returnbinary_tree

defdepth(self) ->int:
"""
 Returns the depth of the tree

 >>> BinaryTree(Node(1)).depth()
 1
 >>> BinaryTree.small_tree().depth()
 2
 >>> BinaryTree.medium_tree().depth()
 4
 """
returnself._depth(self.root)

def_depth(self, node: Node|None) ->int:
ifnotnode:
return0
return1+max(self._depth(node.left), self._depth(node.right))

defis_full(self) ->bool:
"""
 Returns True if the tree is full

 >>> BinaryTree(Node(1)).is_full()
 True
 >>> BinaryTree.small_tree().is_full()
 True
 >>> BinaryTree.medium_tree().is_full()
 False
 """
returnself.root.is_full()


if__name__=="__main__":
importdoctest

doctest.testmod()