CSE 331 Lecture Notes - Lecture 2: Kontact, Longest Path Problem, Preorder
Trees As Data Structures
• A tree is a collection of nodes
• Each node has as 1 parent and 0 or more children
• Root node: single node with no parent
• Branch node: a node with one or more children
• Leaf node: a node with no children
• Edge: a pointer from one node to another
• Subtree: a node and all its descendants
• Height: the number of edges contained in the longest path from root node to some leaf
node
o Height of a null tree is -1 (for mathematical purpose)
Traversal
• Pre-order: process root node, then its left then right subtrees (sailboat going on the left
side, call out value)
• In-order: process left subtree, then root node, then right (sailboat going call out middle
side)
• Post-order: process left subtree, then right, then root node (sailboat going call out value
on right side)
Public class KBST<K extends Comparable<K>,V> {
Private KNode<K,V> overallRoot;
KBST<K,V>() {
this.overallRoot = null;
}
Public void put(K key, V value) {
this.overallRoot=putHelper(key, value, overall);
}
Private KNode<K,V> putHelper(K key, V value, kNode<K,V> node) {
If (node == null) {
Node = new kNode<K,V>(key, value);
} else {
If (node.key.compareTo(key) < 0) {
Node.right = putHelper(key, value, node.right);
} else if (node.key.compareTo(key)) {
Node.left = putHelper(key, value, node.left);
} else {
// Node.value = value; this is called morphing and is bad style
Node = new KNode<K, V> (key, value, node.left, node.right);
