dsap.trees.tree.Tree

class documentation

class Tree:

Known subclasses: dsap.trees.binary_tree.BinaryTree

View In Hierarchy

Abstract base class representing a tree structure.

Class Position An abstraction representing the location of a single element within a tree.
Method __iter__ Generate an iteration of the tree's elements.
Method __len__ Return the total number of elements in the tree.
Method breadthfirst Generate a breadth-first iteration of the positions of the tree.
Method children Generate an iteration of Positions representing p's children.
Method depth Return the number of levels separating Position p from the root.
Method height Return the height of the subtree rooted at Position p.
Method is_empty Return True if the tree is empty.
Method is_leaf Return True if Position p does not have any children.
Method is_root Return True if Position p represents the root of the tree.
Method num_children Return the number of children that Position p has.
Method parent Return Position representing p's parent (or None if p is root).
Method positions Generate an iteration of the tree's positions.
Method postorder Generate a postorder iteration of positions in the tree.
Method preorder Generate a preorder iteration of positions in the tree.
Method root Return Position representing the tree's root (or None if empty).
Method _height_bad Return the height of the tree.
Method _height_good Return the height of the subtree rooted at Position p.
Method _subtree_postorder Generate a postorder iteration of positions in subtree rooted at p.
Method _subtree_preorder Generate a preorder iteration of positions in subtree rooted at p.
def __iter__(self):
overridden in dsap.searchtree.binary_search_tree.TreeMap

Generate an iteration of the tree's elements.

def __len__(self):
overridden in dsap.trees.linked_binary_tree.LinkedBinaryTree

Return the total number of elements in the tree.

def breadthfirst(self):

Generate a breadth-first iteration of the positions of the tree.

def children(self, p):
overridden in dsap.trees.binary_tree.BinaryTree

Generate an iteration of Positions representing p's children.

def depth(self, p):

Return the number of levels separating Position p from the root.

def height(self, p=None):

Return the height of the subtree rooted at Position p.

If p is None, return the height of the entire tree.

def is_empty(self):

Return True if the tree is empty.

def is_leaf(self, p):

Return True if Position p does not have any children.

def is_root(self, p):

Return True if Position p represents the root of the tree.

def num_children(self, p):
overridden in dsap.trees.linked_binary_tree.LinkedBinaryTree

Return the number of children that Position p has.

def parent(self, p):
overridden in dsap.trees.linked_binary_tree.LinkedBinaryTree

Return Position representing p's parent (or None if p is root).

def positions(self):
overridden in dsap.trees.binary_tree.BinaryTree

Generate an iteration of the tree's positions.

def postorder(self):

Generate a postorder iteration of positions in the tree.

def preorder(self):

Generate a preorder iteration of positions in the tree.

def root(self):
overridden in dsap.trees.linked_binary_tree.LinkedBinaryTree

Return Position representing the tree's root (or None if empty).

def _height_bad(self):

Return the height of the tree.

def _height_good(self, p):

Return the height of the subtree rooted at Position p.

def _subtree_postorder(self, p):

Generate a postorder iteration of positions in subtree rooted at p.

def _subtree_preorder(self, p):

Generate a preorder iteration of positions in subtree rooted at p.