May-11-2021, 07:58 AM
Quote:Get an error while insert a node to implement tree after insert node values what are missing and where
Error:AttributeError Traceback (most recent call last)
<ipython-input-35-5b7f867f337a> in <module>
228 root = Node(10)
229
--> 230 root.insert(5)
231
232 root.insert(30)
AttributeError: 'Node' object has no attribute 'insert'class Node:
def __init__(self,insert=None, value=None):
self.value = value
self.left = None
self.right = None
def get_value(self):
return self.value
def set_value(self, value):
self.value = value
def has_left_child(self):
return self.left is not None
def get_left_child(self):
return self.left
def set_left_child(self, node):
self.left = node
def has_right_child(self):
return self.right is not None
def get_right_child(self):
return self.right
def set_right_child(self, node):
self.right = node
def _height(self, node, height=0):
if self.root is None:
return 0
return self._height(self.root, 0)
if node is None:
return height
# Increment for this current node.
height += 1
# If this node is a leaf, return the current height.
if not node.has_left_child() and not node.has_right_child():
return height
# To save some steps, we'll only get the child height if there is a child.
left_height = 0
right_height = 0
if node.has_left_child():
left_height = self._height(node.get_left_child(), height)
if node.has_right_child():
right_height = self._height(node.get_right_child(), height)
return max(left_height, right_height)
def _diameter(self, node, diameter=0):
if self.root is None:
return 0
return self._diameter(self.root, 0)
if node is None:
return diameter
left_height = self._height(node.get_left_child())
right_height = self._height(node.get_right_child())
left_diameter = self._diameter(node.get_left_child())
right_diameter = self._diameter(node.get_right_child())
return max(left_height + right_height + 1, max(left_diameter, right_diameter))
tree = Tree()
tree.set_root(9)
tree.get_root().set_left_child(Node(8))
tree.get_root().set_right_child(Node(10))
tree.get_root().get_left_child().set_left_child(Node(7))
tree.get_root().get_right_child().set_right_child(Node(11))
tree.get_root().get_left_child().get_left_child().set_left_child(Node(6))
tree.get_root().get_left_child().get_left_child().set_right_child(Node(5))
tree.get_root().get_left_child().get_left_child().get_right_child().set_right_child(Node(4))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().set_left_child(Node(3))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().set_right_child(Node(2))
tree.get_root().get_left_child().get_left_child().get_right_child().get_right_child().get_right_child().set_right_child(Node(1))
ht = tree.height()
if ht == 7:
print('Yes, the height is 7.')
else:
print('Whoops, wrong height of {}, but should be 7.'.format(ht))
d = tree.diameter()
if d == 9:
print('Yes, the diameter is 9.')
else:
print('Whoops, wrong diameter of {}, but should be 9.'.format(ht))
# depth first seach recurion on BST with some application
class BTree_struct:
def __init__(self, key=None):
self.root = None
self.key = key
self.left = None
self.right = None
def set_root(self, value,key):
self.root = Node(value)
self.key = key
def get_root(self):
return self.root
def diameter(self):
pass
def insert_at_left(self, node):
self.left = node
def insert_at_right(self, node):
self.right = node
def search_elem(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search(key)
return temp
return None
def dfs(self):
print('entering {}...'.format(self.key))
if self.left is not None:
self.left.dfs()
print('at {}...'.format(self.key))
if self.right is not None:
self.right.dfs()
print('leaving {}...'.format(self.key))
btree_instance = None
print('Menu (no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('dfs')
print('quit')
while True:
my_input = input('What would you like to do? ').split()
op = my_input[0].strip().lower()
if op == 'insert':
data = int(my_input[1])
new_node = BTree_struct(data)
sub_op = my_input[2].strip().lower()
if sub_op == 'at':
btree_instance = new_node
else:
position = my_input[3].strip().lower()
key = int(position)
ref_node = None
if btree_instance is not None:
ref_node = btree_instance.search_elem(key)
if ref_node is None:
print('No such key.')
continue
if sub_op == 'left':
ref_node.insert_at_left(node)
elif sub_op == 'right':
ref_node.insert_at_right(node)
elif op == 'dfs':
print('depth-first search traversal:')
if btree_instance is not None:
btree_instance.dfs()
print()
elif op == 'quit':
break
def insert(self, value):
self.value = value
self.left = None
self.right = None
if value == self.value:
return False
if value:
if value < self.value:
if self.left is None:
self.left = Node(value)
else:
self.left.insert(value)
elif value > self.value:
if self.right is None:
self.right = Node(value)
else:
self.right.insert(value)
else:
self.value = value
"""" 10
/ \
5 30
/ \ / \
8 9 20 40
"""
# alternative way insert node leftsubtree as well rightsuntree
root = Node(10)
root.insert(5)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(8)
root.insert(9)