Binary Search Tree - storing reference to parent node
-
17-05-2021 - |
Question
I hope someone can help me, I'm not a programming professional, but am using Python to learn and experiment with binary trees.
Below is the code I have, and have attempted to try and store a reference to a node's parent in it's node, the storing of it's parent node, won't work for leaf nodes though. Is there a way of doing this during the process of building the tree?
I'd also like to know for a given node, whether is's a 'Left or 'Right' node. I thought seeing as the node is stored in an instance of TreeNode.left or TreeNode.right, I might be able to get a reference to this in Python, as in n._name_ or something like that. Could you tell me the correct way to find whether a node is left or right?
My ultimate goal will be to visualise my tree through a level order traversal.
class TreeNode:
left, right, data = None, None, 0
def __init__(self,nodeData, left = None, right = None, parent = None):
self.nodeData = nodeData
self.left = left
self.right = right
self.parent = self
class Tree:
def __init__(self):
self.root = None
def addNode(self, inputData):
return TreeNode(inputData)
def insertNode(self, parent, root, inputData):
if root == None:
return self.addNode(inputData)
else:
root.parent = parent
if inputData <= root.nodeData:
root.left = self.insertNode(root, root.left, inputData)
else:
root.right = self.insertNode(root, root.right, inputData)
return root
Solution
There are many, many things wrong with this. Since it's homework, I'll supply one hint.
def __init__(self,nodeData, left = None, right = None, parent = None):
self.nodeData = nodeData
self.left = left
self.right = right
self.parent = self
Why isn't self.parent
set to parent
?