Mathematical Tree Notation
27 February 2019 OSU CSE 1
Tree Theory
Copyright By PowCoder代写 加微信 powcoder
• Another mathematical model that we will
use (recall XMLTree) is that of trees
– The arity of these trees is not fixed, as with
binary tree theory (where the arity is 2)
• A tree can be thought of as a structure
comprising zero or more nodes, each with a label of some mathematical type, say T,
called the label type
• We call this math type tree of T
27 February 2019 OSU CSE 2
Recursive Structure • A tree (type tree of T) is either
– the empty tree (empty_tree), which has no nodes at all; or
– a non-empty tree, which consists of:
• A root node (type T)
• A string of the subtrees of the root (type string of tree of T)
• Since a non-empty tree may contain other trees (each of which may contain others), its structure is recursive
27 February 2019 OSU CSE 3
The Empty Tree • The empty tree is denoted by
empty_tree and is shown in our diagrams as
• Unlike the situation with binary trees, where there are always two subtrees for
each node, we need to be explicit about empty trees in diagrams of (general) trees
27 February 2019 OSU CSE 4
Non-Empty Trees
• Every non-empty tree is the result of the
mathematical function compose applied to a value of the label type T and a string of tree of T, which are the root and the subtrees of the resulting tree
• In the diagrams that follow, T is integer 27 February 2019 OSU CSE 5
The compose Function
compose(x, s)
x = 42 s=<,,>
27 February 2019 OSU CSE 6
The compose Function triangles to stand for
Diagrams use color
any tree, including x, s
possibly an empty tree.
x = 42 s=<,,>
compose(x, s)
27 February 2019 OSU CSE 7
The compose Function in this string might be
Any or all of the trees
empty trees, shown x, s
here explicitly.
x = 42 s=<,,>
compose(x, s)
27 February 2019 OSU CSE 8
If the string is an empty
The compose Function
string, then we draw
nothing below the root
x = 42 s=<>
compose(x, s)
27 February 2019 OSU CSE 9
The compose Function What does this tree
look like? (Hint: not
like it is shown so far.)
compose(x, s)
x = 42 s=<,,>
27 February 2019 OSU CSE 10
Size, Height, and Labels
• The size of t, i.e., the total number of
nodes in t, is denoted by |t|
• The height of t, i.e., the number of nodes
on a longest path from the root to a leaf of t, is denoted by ht(t)
• The labels of t, i.e., the set whose elements are exactly the labels of t (i.e.,
the tree’s labels without duplicates and ignoring order) is denoted by labels(t)
27 February 2019 OSU CSE 11
Size, Height, and Labels
• The size of t, i.e., the total number of
nodes in t, is denoted by |t|
• The height of t, i.e., the number of nodes
on a longest path from the root to a leaf of t, is denoted by ht(t)
• The labels of t, i.e., the set whose A leaf is a node that
elements are exactly the labels of t (i.e., has no other nodes
the tree’s labels without duplicates and as children.
ignoring order) is denoted by labels(t) 27 February 2019 OSU CSE 12
1+| |+ ||+||
27 February 2019 OSU CSE 13
1 + max(ht( ), ht( ), ht( ))
27 February 2019 OSU CSE 14
If there are no subtrees,
define the max to be zero,
i.e., the height of a tree with
a root and no children is 1.
1 + max(ht( ), ht( ), ht( ))
27 February 2019 OSU CSE 15
{13} union labels( ) union labels( ) union labels( )
27 February 2019 OSU CSE 16
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com