Please enable JavaScript.
Coggle requires JavaScript to display documents.
M7 (Trees) - Coggle Diagram
M7
Trees
In comp. science is usually an synonym to rooted trees
Many practical applications
Previous vertex: ancestors (if does not include the original vertex: proper ancestors)
Immediately previous vertex = parent (vertex itself is son)
Same parent = siblings
No sons = leaf
All the descendants of a vertex form a subtree
Depth = distance from vertex to root
Height = longest distance from a root to a leaf
Ordered trees : children of each vertex are ordered
Binary tree
Every vertex has no more than two children (left/right child)
Can be defined recursively; useful to solve many problems
Binary search trees: parental vertex larger than left subtree and smaller than the right subtree
Multiway search trees
Searching and insertion : very similar to what is done in binary search
Can be implemented trough a collection of nodes with two pointers each
Recursively computing of tree height
Traversals: preorder, inorder and postorder
A free tree is a connected acyclic graph
A graph that has no cycles but is not necessarily connected is called a forest
Arbitrarily ordered trees (non binary)
First child-next sibling representation
A=V-1
There's one simple path between any two vertices, thus a root can be picked