Tree
- A Tree is a hierarchical collection
- supports one-to-many relationship between elements:
- ONE unique predecessor element
- MANY successor elements
- supports one-to-many relationship between elements:
- Trees are graphs
- Trees can be rooted:
- they have one dediated node that serves as a root
- We will be talking about binary trees for now
m-ary|k-ary|k-way Tree
- An m-ary tree is a rooted tree in which each node has no more than m successors(children).
Binary Tree(m=2 m-ary Tree)
- An binary tree is a rooted tree in which each nodes has no more than TWO successors(children).
Terminology
Nodes and Edges
image-20210325155444594.png
Root/ Internal / Leaf
image-20210325155710904.png
Parent / Child Node
image-20210325155844903.png
Siblings
image-20210325155935742.png
Predecessor / Successor
image-20210325160058778.png
Path / Path Length
image-20210325160219733.png
Ancestor / Descendant
image-20210325160427146.png
Node Depth
- Node depth: length of a path( number of edges it contains) from the root to the node(in some books: number of nodes it contains + root node depth is 1)
image-20210325160729650.png
Node Height
- Node height: length of the longest path(number of edges it contains) from the node to its leaf descendant.( in some books: number of nodes it contains + root node depth is 1)
image-20210325161055249.png
Tree Height
-
Tree height: maximum node depth in the tree OR height of the root.
- Here: tree height H=2
image-20210325161453467.png
Tree Width
-
Tree width: number of nodes in its widest level.
- Here : tree width W=4
image-20210325161756709.png
Subtrees
image-20210325161822194.png
Tree size
-
Tree size: number of all nodes in a tree
- Here: N= 20+ 21+ 22=7(but this is very ”neat“ tree)
image-20210325162226551.png
- Here: N= 20+ 21+ 22=7(but this is very ”neat“ tree)
Trees and Object-Orientation
image-20210325162450755.png
