Week 6. Trees

Trees

In computer science, a tree is an abstract model of a non-linear hierarchical structure, it consists of nodes with a parent-child relation.

Each node except for the root, has a parent and zero or more children. Root: node without parent Internal node: node with at least one child External node: node without children Ancestors of a node: parent, grandparent, grand-grandparent Descendant of a node: child, grandchild, grand-grandchild Siblings: children of the same parent

Depth of a node: number of ancestors Height of a tree: maximum depth of any node Sub-tree: tree consisting of a node and its descendants

Formal Tree Definition

Tree $T$ is a set of nodes storing elements such that the nodes have a parent-child relationship, that satisfies the following properties:

• if $T$ is non-empty, it has a special node, called the root of $T$ that has no parent
• each node $v$ of $T$ different from the root has a unique parent node $w$ every node with parent $w$ is a child of $w$

Ordered Tree

Ordered Tree

A tree is ordered if there is a linear ordering defined for the children of each node. We can identify the children of node as being the first, second, third, etc. Ordered trees typically indicate the linear order among siblings by listing them in the correct order.

Link to original

Tree ADT

Tree (ADT)

The Tree ADT stores elements at positions which are defined relative to neighbouring positions.

A tree also similarly provides a Position with the method element() which returns the object stored at the position.

Accessor methods:

• position root(): return the tree’s root; error occurs if tree is empty
• position parent(v): return the parent of $v$; error occurs if $v$ is root
• Iterable children(v): returns an iterable collection containing the children of node $v$

Query methods:

• boolean isInternal(v): test whether node $v$ is internal
• boolean isExternal(v): test whether node $v$ is external
• boolean isRoot(v): test whether node $v$ is a root

Generic methods:

• integer size(): return the number of nodes in the tree
• boolean isEmpty(): test whether the tree has any nodes
• Iterator iterator(): return an iterator of nodes stored in tree
• Iterable positions(): return iterable collection of all nodes in tree
• element replace(v, e): replace element stored at $v$ with $e$ and return it

Link to original

Linked Structure for Trees

A node is represented by an object storing the element, parent node and a sequence of child nodes. Each node object implements the position ADT.

Tree Traversal Algorithms

Traversal of a Tree

A traversal of a tree $T$ is a systematic way of accessing or visiting all the nodes of $T$.

There are different traversal schemes, for DST we need to know:

• Preorder traversal

  Preorder traversal is where a node is visited before its descendants.

  • Parents always come before their children.
  • Running time for a tree with $n$ nodes is $O(n)$.

  def preOrder(T, v):
  	visit(v)
  	for each child w of v in T:
  		preOrder(T, w)

  Link to original

• In-order traversal

  In-order traversal (applies to binary trees) is where a node is visited after its left sub-tree and before the right sub-tree.

  def inOrder(T, v):
  	if hasLeft(v):
  		inOrder(T, left(v))
   
  	visit(v)
   
  	if hasRight(v):
  		inOrder(T, right(v))

  Link to original

• Postorder traversal

  Postorder traversal is where a node is visited after its descendants.

  • Running time for a tree with $n$ nodes is $O(n)$.

  def postOrder(T, v):
  	for each child w of v in T:
  		postOrder(T, w)
  	visit(v)

  Link to original

Link to original

Binary Trees

Binary Tree

A binary tree is an Ordered Tree with the following properties:

• each internal node has at most two children
• each child node is labelled as a left or right child
• a left child precedes a right child in the ordering of children

The sub-tree rooted at a left or right child of an internal node $v$ is called a left or right sub-tree, respectively, of $v$.

A binary tree is proper (full) if each node has either zero or two children. Each internal node has exactly two children.

Link to original

Recursive Definition

A binary tree $T$ is either empty or consists of:

• a node $r$ called the root of $T$ and storing the element
• a binary tree, called the left sub-tree of $T$.
• a binary tree, called the right sub-tree of $T$.

Binary Tree ADT

Binary Tree (ADT)

The binary tree ADT extends the Tree (ADT). It has additional methods:

• position left(v): return the left child of $v$
• position right(v): return the right child of $v$
• boolean hasLeft(v): test whether $v$ has a left child
• boolean hasRight(v): test whether $v$ has a right child

Link to original

Linked Structure for Binary Trees

A node is represented by an object storing:

• the element
• the parent node
• left child node
• right child node

Euler Traversal

can’t tell if required