Skip to content

Latest commit

 

History

History
80 lines (55 loc) · 1.51 KB

tree-adt.md

File metadata and controls

80 lines (55 loc) · 1.51 KB
Raw

← Return to Index

The Tree ADT

Definition

A tree can be empty (nilTree) or an element e that forks between two trees

TYPES
    type tree = nilTree | fork e * (tree e) * (tree e)

Operations

OPERATIONS
    empty : tree e -> boolean
    leaf : tree e -> boolean
    fork : e * tree e * tree e -> tree e
    left : tree e -> tree e
    right: tree e -> tree e
    contents : tree e -> e

Functions

Height

Recursively defined; height equals 1 plus the height of the subtrees below.

height(nilTree) = 0
    | height(fork(e, TL, TR)) = 1 + max(height(TL), height(TR))

Weight

Also recursively defined; weight equals 1 plus the weights of every subtree as it forks.

weight(nilTree) = 0
    | weight(fork(e,TL, TR)) = 1 + weight(TL) + weight(TR)

Preorder Traversal

Root, then left subtree then right subtree

preorder(nilTree) = nil
	| preorder(fork(e,TL,TR)) = print(e), preorder(TL), preorder(TR)

Inorder Traversal

Left subtree, root, then right subtree

inorder(nilTree) = nil
	| inorder(fork(e,TL,TR)) = inorder(TL), print(e), inorder(TR)

Postorder Traversal

Left subtree, right subtree, then root

postorder(nilTree) = nil
	| postorder(fork(e,TL,TR)) = postorder(TL), postorder(TR), print(e)

Breadth-first Traversal

Root is visited, then children, then grandchildren

breadthfirst(nilTree) = nil
	| ; left as exercise