the following code is taken from the book DSA in python by Goodrich. I understand the theory of the binary tree ADT using linked structure but i am unable to get the proper working of the the code.
class binaryTree(tree):
def left(self, p):
"""returns the position of the left child of p, None if there are not any."""
pass
def right(self, p):
"""returns the right child of p, None if there are not any"""
pass
def sibling(self, p):
parent = self.parent(p)
if parent is None:
return None
else:
if p == self.left(parent):
return self.right(parent)
else:
return self.left(parent)
def children(self, p):
"""generate the iteration of the children of the position p"""
if self.left(p) is not None:
yield self.left(p)
if self.right(p) is not None:
yield self.right(p)
class LinkedBinaryTree(binaryTree):
class node:
# todo pending implementation of the __slots__
def __init__(self, element, parent=None, left=None, right=None):
self.element = element
self.parent = parent
self.left = left
self.right = right
class position(binaryTree.position):
"""an abstraction representing the location of a single element"""
def __init__(self, container, node):
self.container = container
self.node = node
def element(self):
return self.node.element
def __eq__(self, other):
"""returns true if other is a position representing the same location"""
return type(other) is type(self) and other.node is self.node
def validate(self, p):
"""returns the associated node, if the position is valid"""
if not isinstance(p, self.position):
raise TypeError(" p must be proper position type")
if p.container is not self:
raise ValueError("p does not belong to this container")
if p.node.parent is p.node:
raise ValueError("p is no longer valid")
return p.node
def make_position(self, node):
"""return the position instance of the given node"""
return self.position(self, node) if node is not None else None
def __init__(self):
"""create an initially empty binary tree"""
self.root = None
self.size = 0
def __len__(self):
"""returns the total number of elements in a tree"""
return self.size
def root(self):
"""return the position of the root of the tree"""
return self.make_position(self.root)
def parent(self, p):
"""return the position of p's parent """
node = self.validate(p)
return self.make_position(node.parent)
def left(self, p):
"""return the position of p's left child"""
node = self.validate(p)
return self.make_position(node.left)
def right(self, p):
"""return the right child of p"""
node = self.validate(p)
return self.make_position(node.right)
def num_children(self, p):
"""return the total number of children of position p"""
node = self.validate(p)
count = 0
if node.left is not None:
count += 1
if node.right is not None:
count += 1
return count
def add_root(self,e):
"""place element e at the root of the tree and return new position"""
if self.root is not None:
raise ValueError(" root exists")
self.size=1
self.root = self.node(e)
return self.make_position(self.root)
def add_left(self,p,e):
"""create a new left child of the position p storing element e
raise value error if position p is invalid or p already has a left child"""
node = self.validate(p)
if node.left is not None:
raise ValueError("left child exists")
self.size += 1
node.left = self.node(e, node)
return self.make_position(node.left)
def add_right(self, p, e):
"""create ta new child for position p storing the element p"""
node = self.validate(p)
if node.right is not None:
raise ValueError("right child exists")
self.size += 1
node.left = self.node(e, node)
return self.make_position(node.right)
I am unable to understand the working of the nested position class inside the LinkedBinaryTree class. The author quoted that it is borrowed from the positional list ADT code but I looked back and still am unable to get how the code works.
My question is, how am I supposed to assign the position to a node, and how would the tree look like after i did it. I tried to create an instance of the Binary tree but the code ended up showing some errors. It would be great if someone can explain how the code works and drop an example of creating a tree for the same.
Also, is there a better way of implementing the binary tree ADT in python other than this one ( i apologize if i am asking something basic).
question from:
https://stackoverflow.com/questions/65859370/query-about-the-implementation-of-binary-tree-in-python 与恶龙缠斗过久,自身亦成为恶龙；凝视深渊过久,深渊将回以凝视…
