class Node:
def __init__(self,label,left,right):
self.label = label
self.left = left
self.right = right
def __repr__(self):
left = 'None' if self.left is None else self.left.label
right = 'None' if self.right is None else self.right.label
return "Node: (label={0},left_node_label={1},right_node_label={2})".format(self.label,left,right)
def search_children(self,target_label):
if self.label == target_label:
return (True,self)
else:
if self.left is None and self.right is None:
return (False,None)
if self.left is not None:
return self.left.search_children(target_label)
if self.right is not None:
return self.right.search_children(target_label)
# a
# / \
# / \
# b c
# / \ / \
# d e b' f
# /
# c'
# I've created two nodes with labels 'b' and 'c' so that we can
# test whether we are indeed searching depth-first
b_prime = Node('b',None,None)
c_prime = Node('c',None,None)
f = Node('f',None,None)
e = Node('e',None,None)
d = Node('d',c_prime,None)
c = Node('c',b_prime,f)
b = Node('b',d,e)
a = Node('a',b,c)
# simple depth-first search in a binary tree
# a tree has no cycles!
def depth_first_search(root_node, target_label):
return root_node.search_children(target_label)
depth_first_search(a,'a')
(True, Node: (label=a,left_node_label=b,right_node_label=c))
depth_first_search(a,'d')
(True, Node: (label=d,left_node_label=c,right_node_label=None))
# the node with label 'b' on the left subtree will be found first,
# because this is a depth first search
depth_first_search(a,'b')
(True, Node: (label=b,left_node_label=d,right_node_label=e))
# this label was not found
depth_first_search(a,'j')
(False, None)
# the node with label 'c' on the left subtree will be found first,
# because this is a depth first search
depth_first_search(a,'c')
(True, Node: (label=c,left_node_label=None,right_node_label=None))