APP-Notes

Bomen

Begrippen

• Aantal takken is aantal knopen - 1
• Begin-knoop heet ‘wortel’
• Knopen zonder nieuwe takken, noemen we ‘bladeren’
• Soort nodes:
  • Parent
  • Children
  • Siblings (broer en/of zus). Nodes op hetzelfde niveau met dezelfde parent
• Depth: lengte pad van node tot root
• Height: lengte naar diepste leaf onder de betreffende knoop

Implementaties

Simpele class met value en children-list

zie slides

public class Tree<T> {
    public TreeNode<T> root;
}

public class TreeNode<T> {
    public T value;
    public List<TreeNode<T>> children;
}

First-Child-Next-Sibling

Een node heeft steeds een verwijzing naar een child en een sibling. De onderstaande afbeeldingen representeren dezelfde boom:

Binary Tree

• Iedere node heeft maximaal 2 children
• Kan gebruikt worden voor calculaties

public class BinaryTree<T> {
    public BinaryNode<T> root;
}

public class BinaryNode<T> {
    public T value;
    BinaryNode<T> left;
    BinaryNode<T> right;
}

Doorloop-methodes

• (a) Pre-Order: Current, Left, Right
  • a: + a (* (- b c) d)
• (b) Post-Order: Left, Right, Current
  • b: a ((b c -) d *) +
• (c) In-order: Left, Current, Right
  • c: a + ((b - c) * d)