+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: How does a single object see all the values inside it? (/thread-21479.html)
How does a single object see all the values inside it? - jenniferruurs - Oct-01-2019
Bellow I have some code, I was wondering how it is possible that the object root looks like if I have list of object (I expect a single object)
I get the values after inorder function:
4
6
8
32
58
59
98
But I expect to get get only 4
since root = insert(root, 4)is overriding the object or am I missing something.
(My goal is to understand how this list of objects is created)
class Node:
def __init__(self, key):
self.key=key
self.left= None
self.right=None
def inorder(root):
if root is not None:
inorder(root.left)
print(root.key)
inorder(root.right)
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right,key)
return node
def minValueNode(node):
current = node
while(current.left is not None):
current = current.left
return current
def deleteNode(root, key):
if root is None:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif(key>root.key):
root.right= deleteNode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
root = None
root = insert(root, 58)
root = insert(root, 32)
root = insert(root, 8)
root = insert(root, 59)
root = insert(root, 98)
root = insert(root, 6)
root = insert(root, 4)
inorder(root)
RE: How does a single object see all the values inside it? - stullis - Oct-01-2019
This is a standard binary tree. Basically, it's a linked list combined with a sorting algorithm.
When inserting a value, insert() determines the current state of the node and evaluates how the new value compares. If the value is None, it creates a node. If the new value is lower, it recurses and evaluates the left child node of the current node and repeats the process. Likewise, if the value is higher, it does the same process to the right child node.
The end result is a data structure of nodes that know about other nodes, their children. Plus, they're all sorted by value. When you use inorder() on this data structure, it asks a question: Who are your children and where do they live? Then, it asks the left child the same question until there are no more children. It prints the value of the last child, then that child's parent, and then it asks the same question to the right child.
Geeks for Geeks has a great series on binary trees and different variants. They have gifs to demonstrate them too.