Tree: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
A Tree | A Tree is a connected (there is a path between every vertices) and acyclic graph. If one edge is added to the tree, it will form a cycle and if one edge is removed from the tree, it will become disconnected. | ||
In a binary tree, nodes have at most two children. | A Tree has (only one) designated root node and has child nodes. A leaf node has no child. | ||
In a binary tree, nodes have at most two children. A perfect binary tree of n levels has 2<sup>k</sup>-1 nodes. | |||
A complete binary tree is a tree where all nodes have 2 children except nodes at the last level on the far right of the tree. | |||
There are 4 ways to traverse a binary tree: | |||
*In-order: left node, root node, the then right node (the most common) | |||
*Pre-order: the root, the left node, then the right node | |||
*Post-order: the left node, the right node, then the root node | |||
*Level-order: BFS traversal | |||
== Resources == | |||
{| class="wikitable" | |||
! | |||
|- | |||
|https://www.youtube.com/watch?v=oSWTXtMglKE | |||
|} | |||
Latest revision as of 21:07, 4 October 2020
A Tree is a connected (there is a path between every vertices) and acyclic graph. If one edge is added to the tree, it will form a cycle and if one edge is removed from the tree, it will become disconnected.
A Tree has (only one) designated root node and has child nodes. A leaf node has no child.
In a binary tree, nodes have at most two children. A perfect binary tree of n levels has 2k-1 nodes.
A complete binary tree is a tree where all nodes have 2 children except nodes at the last level on the far right of the tree.
There are 4 ways to traverse a binary tree:
- In-order: left node, root node, the then right node (the most common)
- Pre-order: the root, the left node, then the right node
- Post-order: the left node, the right node, then the root node
- Level-order: BFS traversal
Resources
| https://www.youtube.com/watch?v=oSWTXtMglKE |