dsap.trees.linked_binary_tree.LinkedBinaryTree

class documentation

class LinkedBinaryTree(BinaryTree):

Known subclasses: dsap.searchtree.binary_search_tree.TreeMap, dsap.trees.expression_tree.ExpressionTree

Linked representation of a binary tree structure.

Class	`Position`	An abstraction representing the location of a single element.
Method	`__init__`	Create an initially empty binary tree.
Method	`__len__`	Return the total number of elements in the tree.
Method	`left`	Return the Position of p's left child (or None if no left child).
Method	`num_children`	Return the number of children of Position p.
Method	`parent`	Return the Position of p's parent (or None if p is root).
Method	`right`	Return the Position of p's right child (or None if no right child).
Method	`root`	Return the root Position of the tree (or None if tree is empty).
Class	`_Node`	Lightweight, nonpublic class for storing a node.
Method	`_add_left`	Create a new left child for Position p, storing element e.
Method	`_add_right`	Create a new right child for Position p, storing element e.
Method	`_add_root`	Place element e at the root of an empty tree and return new Position.
Method	`_attach`	Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p.
Method	`_delete`	Delete the node at Position p, and replace it with its child, if any.
Method	`_make_position`	Return Position instance for given node (or None if no node).
Method	`_replace`	Replace the element at position p with e, and return old element.
Method	`_validate`	Return associated node, if position is valid.
Instance Variable	`_root`	Undocumented
Instance Variable	`_size`	Undocumented

Inherited from BinaryTree:

Method	`children`	Generate an iteration of Positions representing p's children.
Method	`inorder`	Generate an inorder iteration of positions in the tree.
Method	`positions`	Generate an iteration of the tree's positions.
Method	`sibling`	Return a Position representing p's sibling (or None if no sibling).
Method	`_subtree_inorder`	Generate an inorder iteration of positions in subtree rooted at p.

Inherited from Tree (via BinaryTree):

Method	`__iter__`	Generate an iteration of the tree's elements.
Method	`breadthfirst`	Generate a breadth-first iteration of the positions of the tree.
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	`postorder`	Generate a postorder iteration of positions in the tree.
Method	`preorder`	Generate a preorder iteration of positions in the tree.
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 __init__(self): ¶

overridden in dsap.trees.expression_tree.ExpressionTree

Create an initially empty binary tree.

def __len__(self): ¶

overrides dsap.trees.tree.Tree.__len__

Return the total number of elements in the tree.

def left(self, p): ¶

overrides dsap.trees.binary_tree.BinaryTree.left

Return the Position of p's left child (or None if no left child).

def num_children(self, p): ¶

overrides dsap.trees.tree.Tree.num_children

Return the number of children of Position p.

def parent(self, p): ¶

overrides dsap.trees.tree.Tree.parent

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

def right(self, p): ¶

overrides dsap.trees.binary_tree.BinaryTree.right

Return the Position of p's right child (or None if no right child).

def root(self): ¶

overrides dsap.trees.tree.Tree.root

Return the root Position of the tree (or None if tree is empty).

def _add_left(self, p, e): ¶

Create a new left child for Position p, storing element e.

Return the Position of new node. Raise ValueError if Position p is invalid or p already has a left child.

def _add_right(self, p, e): ¶

Create a new right child for Position p, storing element e.

Return the Position of new node. Raise ValueError if Position p is invalid or p already has a right child.

def _add_root(self, e): ¶

Place element e at the root of an empty tree and return new Position.

Raise ValueError if tree nonempty.

def _attach(self, p, t1, t2): ¶

Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p.

As a side effect, set t1 and t2 to empty. Raise TypeError if trees t1 and t2 do not match type of this tree. Raise ValueError if Position p is invalid or not external.

def _delete(self, p): ¶

Delete the node at Position p, and replace it with its child, if any.

Return the element that had been stored at Position p. Raise ValueError if Position p is invalid or p has two children.

def _make_position(self, node): ¶

Return Position instance for given node (or None if no node).

def _replace(self, p, e): ¶

Replace the element at position p with e, and return old element.

def _validate(self, p): ¶

Return associated node, if position is valid.

_root = ¶

overridden in dsap.searchtree.binary_search_tree.TreeMap

Undocumented

_size: int = ¶

Undocumented