Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trees - Coggle Diagram
Trees
- A tree (more accurately, a free tree) is a connected acyclic graph
- Forest: acyclic graph not necessarily connected
- Rooted tree (root typically on the top)
Applications: implement dictionaries, fault analysis, etc.
-
Terminology for rooted trees
- Parent
- Siblings
- Subtree
- Internal vertices
- Ancestors / descendants (proper)
- Leaf: no children
- Depth/level of v: length of the unique path from the root to v
- Height: length of the longest unique path from the node to a leaf
- m-ary tree: every internal vertex has no more than m children
- Complete m-ary tree: levels filled from top to bottom, left to right
- Full m-ary tree: exactly m children
- m-ary tree, where m = 2: binary tree
- Ordered tree
- Ordered binary tree: binary search tree (BST)
- Balanced tree
-
Binary tree traversals
preorder
- The root is processed before the left and the right subtrees
Algorithm: void preorder(BSTNode rt)
- if rt != NULL then
- ----// do something with rt
- ----preorder(rt.left);
- ----preorder(rt.right);
inorder
- The root is processed after the left subtree, but before the right subtree
- An inorder traversal visits the keys
in a non-decreasing order
Algorithm: void inorder(BSTNode rt)
- if rt != NULL then
- ----inorder(rt.left);
- ----// do something with rt
- ----inorder(rt.right);
posorder
- The root is processed after the left and the right subtrees
Algorithm: void posorder(BSTNode rt)
- if rt != NULL then
- ----posorder(rt.left);
- ----posorder(rt.right);
- ----// do something with rt
-