Please enable JavaScript.
Coggle requires JavaScript to display documents.
M7 (Trees, Binary Tree Traversals and Related Properties, Searching and…
M7
Trees
tree: is a connected acyclic graph
forest: has no cycles but is not necessarily connected
the number of edges in a tree is always one less than the number of its vertices:
Rooted Trees: possible to select an arbitrary vertex
in a free tree and consider it as the root
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. The vertex itself is usually considered its own ancestor
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; vertices that have the same parent are said to be siblings.
A vertex with no
children is called a
leaf
The height of a tree is the length of the longest simple path from the root to a leaf.
An
ordered tree
is a rooted tree in which all the children of each vertex are ordered.
A binary tree can be defined as an ordered tree in which every vertex has no more than two children and each child is designated as either a left child or a right child of its parent
Binary Tree Traversals and Related Properties
Many problems about binary trees can be solved by applying the divide-and-conquer technique
Example: computing the height of a binary tree
ALGORITHM
Height(T )
if T = ∅ return −1
else return max{
Height
(Tleft),
Height
(Tright)} + 1
The extra nodes are called
external
The original nodes are called
internal
The number of external nodes x is always 1 more than the number of internal nodes n -> x = n + 1
Searching and Insertion in a Binary Tree
. If the tree is empty, the search ends in failure. If the tree is not empty, we compare v with the tree’s root K(r). If they match, a desired element is found and the search can be stopped; 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).
