Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trees - Coggle Diagram
Trees
Connected acyclic graph
-
For every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other.
This property makes it possible to select an arbitrary vertex
in a free tree and consider it as the root
Rooted tree
Ordered Trees
Binary Tree
-
A number assigned to each parental vertex is larger than all
the numbers in its left subtree and smaller than all the numbers in its right subtree.
When we need to search for an element of a given value v in such a tree, if the tree is not empty, we compare v with the tree’s root K(r). If they do not match, we continue with the search in the left subtree of the root if v < K(r) and in the right subtree if v > K(r).
Draw a tree’s extension by
replacing the empty subtrees by special nodes. The extra nodes are called external and the original nodes are called internal. The number of external nodes x is always 1 more than the number of internal nodes n
The worst-case efficiency of the search operation fall into 
In the preorder traversal, the root is visited before the left and right subtrees are visited (in that order).
The average-case efficiency turns out to be in
In the inorder traversal, the root is visited after visiting its left subtree but before visiting the right subtree.
In the postorder traversal, the root is visited after visiting the left and right subtrees (in that order)
For any vertex v in a tree T , all the vertices on the simple path from the root to that vertex are called ancestors of v.
. If (u, v) is the last edge of the simple path from the
root to vertex v (and u != v), u is said to be the parent of v and v is called a child of u
-
-
-