Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trees, State-space trees, Traversals, is a connected acyclic graph, A…
-
-
-
- is a connected acyclic graph
- A graph that has no cycles but is not necessarily connected
- each of its connected components is a tree
- The number of edges in a tree is always one less than the number of its vertices
|E| = |V| -1
- For every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other
- is usually depicted by placing its root on the top (level 0 of the tree), the vertices adjacent to the root below ir (level 1), and so on
- For any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ancestors
-
-
- leaf: vertex with no vertices
- parental: a vertex with at least one child
-
- All the vertices for which a vertex v is an ancestor are said to be descendants
- A Subtree is all the descendants of a vertex v with all the edges connecting them
- depth: is the length of the simple Plath from the root to the chosen vertex
- height: is the length of the longest simple path from the root to a leaf
- is a rooted tree in which all the children of each vertex are ordered
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
- trees where a number assigned to each parental vertex is larger than the numbers in its left subtree and smaller than all the number in its right subtree
-
- if the tree is empty, the search ends in failure
- if the tree is not empty, 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 don't, we continue with the search in the left subtree of the root If v < K(r) ant in the right subtree if v > K(r)
- preorder traversal: the root is visited before the left and right subtrees are visited
- inorder traversal: the root is visited after visiting its left subtree but before visiting the right subtree
- postorder traversal: the root is visited after visiting the left and tight subtrees
-