Data Trees

    Data Trees are a type of structure to store information in, and we learned about these in class. You can view them visually like this:

    A tree is a series of nodes that have a very strict pattern structure. But first, here are some terms:
Parent: A node that points to another node, and  (Nodes 3, 5, 1, 9, and 7 above are parents.)
Siblings: Nodes with the same parent. (Nodes 5 and 1 are siblings.)
Root: A node with no parents. (Node 3 is a root.)
Leaf: A node with no children, and isn't actually considered a node. (3, 2, and 8 are leaves)
Internal node: A term that includes nodes and roots. Every part of a tree is either an internal node or a leaf.
Arity: A property of a tree that determines the maximum amount of children nodes in the tree may have. (The arity of the tree above is 2.)
Path: A path of nodes that are connected by the arrows (3, 1, 7, 2 is a path)
Tree Length: A property for a tree determined by the length of the longest path. (3, 1, 7, 2 is one of the longest paths in the tree, it's path length is 3 so the tree length is 3.)

Here are some rules:
- Every non-root node has exactly one parent.
- No cycles. A path on a tree cannot lead to an earlier node.

    Thanks to these rules, you can isolate an internal node and all of it's paths, and you have another tree that follows the same rules! This new tree is called a subtree. I wouldn't know for sure, but I think this is might be a very valuable trait for trees and this is why we learn about them.

    There are also different ways to traverse (read all of the internal nodes and leafs) a tree, including pre-order traversal, in-order traversal, and post-order traversal. They are all difficult to understand at first, so I started by studying the recursive-style definitions for each one that were given in the slides in class:

pre-order traversal: Visit root, then pre-order left subtree, then pre-order right subtree.
in-order traversal: Visit in-order left subtree, then root, then in-order right subtree.
post-order traversal: Visit post-order left subtree, then post-order right subtree, then root.

This is pre-order traversal. It goes 3, 5, 6, 9, 4, 1, 7, 2, 8. I'll remember it quickly by taking note of the following:

Pre-order traversal:
1) root
2) left (in pre-order)
3) right (in pre-order)

This is in-order traversal. It goes 6, 5, 4, 9, 3, 1, 2, 7, 8. Notice the unnecessary detours in the blue line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

In-order traversal:
1) left (in in-order)
2) root
3) right (in in-order)

This is post-order traversal. It goes 6, 4, 9, 5, 2, 8, 7, 1, 3. Notice the unnecessary detours in the purple line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

Post-order traversal:
1) left (in post-order)
2) right (in post-order)
3) root

You can also write recursive functions in python for all of these traversals when trees are defined as a list of [int, tree or none, tree or none]. the int in place 0 is the node, the tree in place 1 is the left child, and the tree in place 2 is the right child. If there is None instead of the tree, than there is no child.