Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trees - Coggle Diagram
Trees
Definitions
-
-
-
Ancestors: all the vertices on the simple path from the root to a particular vertex, including itself.
-
Descendants: all the vertices for which a vertex v is an ancestor, including v.
-
-
Parent: u, where (u, v) is the last edge of the simple path from root to vertex v. v is u's child.
-
-
-
-
-
Ordered Trees
-
Binary tree: every vertex has no more than two children, and each children is either a left child or a right child.
The binary tree with its root at the left/right child of a vertex is called the left/right subtree of that vertex.
-
Binary Search Tree
A binary tree where 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.
-
First child-next sibling representation: the left pointer points to the first child of the vertex, and the right pointer points to its next sibling.
-
Since a binary tree can be recursively divided into two smaller, disjoint subtrees from its nodes, divide-and-conquer techniques can be used on it to solve some problems, such as height, since a node has 1 more height than the max height among its children.
-