Introduction to Trees - Eishaaya/GMRDataStructuresTest GitHub Wiki
What makes a tree?
A tree is a useful data structure in many programming applications where data needs to be represented in a hierarchical manner. At the top level, the tree consists of a root node with children stemming from the root. These children could have children, and their children could have children, and so on, branching upward or downward into a "tree-like" entity.
Trees are must be acyclic and connected. Acyclic means that if you start traveling from any node in a tree, its children will never loop around back to its respective parents. Acyclic also means that there are no loops in the structure, constructing a type of generational relationship between nodes. In addition, a node connected to itself is considered cyclic and therefore not allowed. Connected means that there must exist a path from the root to every single node. While they are not necessarily defined by it, trees are typically discussed as n-ary trees, n representing the number of children that can follow from any given node (binary is 2, ternary is 3 and so on). We will be discussing binary trees in which the maximum number of child nodes a parent node can have is limited to 2.
It is also important to note the difference between a binary tree and a Binary Search tree. A binary tree is a tree that has up to 2 child nodes. A Binary search tree is a binary tree that is used for sorting, implementing a binary search where if an element is less than the current, it will appear at or following the left child node and if it is greater than it will appear at or following the right child node.
Trees, as well as the nodes that make it up, have a set of useful properties that are worth mentioning. The depth of a node is the number layers one must traverse to get to that node. For example, if the depth of node A is 3, that means node A would be the root node’s great-grandchild. The height of a tree indicates the longest path from the root of the tree to a leaf node or a node that has no children. The degree of a tree is the number of children nodes that follow from it (nodes lower in the hierarchical environment, or rather all sub-nodes). Finally, the parent of a child is the node from which the child is stemmed from, and a sibling of a node is a node with the same parent.
What will this chapter cover?
Trees have many variations with applications to specific problems: binary, binary search, AVL, Red-Black, AA, B, and many more.
Traversing a tree refers to the process of visiting each node exactly once. Traversing a tree can be done in four ways: pre-order, in-order, post-order, and level-order. Interestingly, a level-order traversal uses the Queue data structure, which was discussed in the previous section. As you will see, these are recursive algorithms which work very well with hierarchal tree-like data structures. Pre-order, in-order, and post-order searches can be categorized as depth-first search (DFS), and the level-order search can be categorized as a breadth-first search(BFS). These will be explained later.
<-- Previous | Next -->