The Self-Taught Computer Scientist


Chapter 14 Binary Trees 161


Download 1.48 Mb.
Pdf ko'rish
bet121/147
Sana17.06.2023
Hajmi1.48 Mb.
#1540634
1   ...   117   118   119   120   121   122   123   124   ...   147
Bog'liq
books-library.net-11301817Az7X6

Chapter 14 Binary Trees
161
self.right_child = None
def insert_left(self, value):
if self.left_child == None:
self.left_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.left_child = self.left_child
self.left_child = bin_tree
def insert_right(self, value):
if self.right_child == None:
self.right_child = BinaryTree(value)
else:
bin_tree = BinaryTree(value)
bin_tree.right_child = self.right_child
self.right_child = bin_tree
def invert(self):
current = [self]
next = []
while current:
for node in current:
if node.left_child:
next.append(node.left_child)
if node.right_child:
next.append(node.right_child)
tmp = node.left_child
node.left_child = node.right_child
node.right_child = tmp
current = next
next = []
The code is the same as your breadth- first traversal to search for a number, but instead of checking 
whether a node’s value is 
n
, you swap the right and left child each iteration.
To accomplish this, you have to first save 
node.left_child
in a temporary variable called 
tmp

Then, you set 
node.left_child
to 
node.right_child
and 
node.right_child
to 
tmp
, which swaps 
the two child nodes.
tmp = node.left_child
node.left_child = node.right_child
node.right_child = tmp
When your algorithm finishes, you have successfully inverted your binary tree.
Another, more elegant way to invert a binary tree is to use a depth- first traversal, which you can 
try in the challenges.


Data Structures
162
Vocabulary
tree: A nonlinear abstract data type made up of nodes connected in a hierarchical structure.

Download 1.48 Mb.

Do'stlaringiz bilan baham:
1   ...   117   118   119   120   121   122   123   124   ...   147




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling