Data Structure & Algorithms (Part III: Tree & Heap)

[8bitzz]

Binary Tree

• Each node has at most 2 children
• Binary tree are ordered: distinguished left-child and right-child

Binary Tree Traversal

Depth First

• Proceed as far as possible to the left/ right
• Pre-order: node --> left --> right
• In-order: left --> node --> right

• Post-order: left --> right --> node

  
  class BTNode {
  int data;
  BTNode left, right;
  
  public BTNode(int data) {
      this.data = data;
      left = right = null;
  }
  }

public class BinaryTree { BTNode root;

public BinaryTree() {
    this.root = null;
}

public static void main(String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.root = new BTNode(1);
    tree.root.left = new BTNode(2);
    tree.root.right = new BTNode(3);
    tree.root.left.left = new BTNode(4);
    tree.root.left.right = new BTNode(5);

    tree.traversePreRecursive();
    tree.traverseInRecursive();
    tree.traversePostRecursive();
}

public void traversePreRecursive() {
    System.out.println("\nPre-order traversal:");
    preorder(root);
}
public void traverseInRecursive() {
    System.out.println("\nIn-order traversal:");
    inorder(root);
}
public void traversePostRecursive() {
    System.out.println("\nPost-order traversal:");
    postorder(root);
}

public void preorder(BTNode node){
    if (node != null) {
        System.out.print(" " + node.data);
        preorder(node.left);
        preorder(node.right);
    }
}
public void inorder(BTNode node){
    if (node != null) {
        inorder(node.left);
        System.out.print(" " + node.data);
        inorder(node.right);
    }
}
public void postorder(BTNode node){
    if (node != null) {
        postorder(node.left);
        postorder(node.right);
        System.out.print(" " + node.data);
    }
}

}

#### Breadth First
- Process layer by layer, left to right