Tree 2

Tree Traversal

• Can be done easily by recursion
• So, order of visit does matter

---

Preorder Traversal

public void preOrderTraversal(Node n)
    {
        if (n == null) return;

        System.out.print(n.value+" ");
        preOrderTraversal(n.left);
        preOrderTraversal(n.right);
    }

Inorder Traversal

public void inOrderTraversal(Node n)
    {
        if (n == null) return;

        inOrderTraversal(n.left);
        System.out.print(n.value+" ");
        inOrderTraversal(n.right);
    }

-> 좌, print, 우로 움직이기 때문에 binary tree에서만 유효.
-> Printing Arithmetic Expressions 응용 가능.

• Print operand or operator when visiting node.
• Print "(" before traversing left subtree.
• Print ")" after traversing right subtree.

  Alg printExpression(v)
  if hasLeft(v)
  	print("(")
  	printExpression(left(v))
  print(v.element())
  if hasRight(v)
  	printExpression(right(v))
      print(")")
      

Postorder Traversal

public  void postOrderTraversal(Node n)
    {
        if (n == null) return;
        
        postOrderTraversal(n.left);
        postOrderTraversal(n.right);
        System.out.print(n.value+" ");
    }

-> Evaluating Arithmetic Expressions

• Recursive method returning the value of a subtree.
• When visiting an internal node, combine the values of the subtrees.

  Alg evalExpr(v)
  if isExternal(v)
  	return v.element()
  else
  	x <- evalExpr(leftChild(v))
      y <- evalExpr(rightChild(v))
      [0] <- operator stored at v
      return x [0] y

---

Binary Search Trees

Properties

1. Key of a node is greater than key of its left child, keys of the nodes of left subtree.
2. Key of a node is smaller than key of its right child, keys of the nodes of right subtree.
3. Inorder Traversal of a binary search tree visits keys in an increasing order.

Search

Alg TreeSearch(k, v)
if T.isExternal(v)
	return null
  if k < key(v)
  	return TreeSearch(k, T.left(v))
  else if k = key(v)
  	return v
  else
  	return TreeSearch(k, T.right(v))

Insert

public void insert(int i) {
        root = recursiveInsert(root, i);
    }

    private Node recursiveInsert(Node n, int i) {
        if (n == null) return new Node(i);

        if (i < n.value) {
            n.left = recursiveInsert(n.left, i);
        } else {
            n.right = recursiveInsert(n.right, i);
        }
        return n;
    }

Delete

[1] Deleting a node with single child
-> Simply connect the parent and the child of v.
[2] Deleting a node with two children
-> we find the node w that follows v in an inorder traversal.
-> than, copy key(w) into node v and remove node w

public void delete(int i) {
        root = recursiveRemove(root, i);
    }

    private Node recursiveRemove(Node n, int i) {
        if (n == null) return null;
        if (i < n.value) {
            n.left = recursiveRemove(n.left, i);
            return n;
        } else if (i > n.value) {
            n.right = recursiveRemove(n.right, i);
            return n;
        } else {
            if (n.left == null && n.right == null) {
                return null;
            } else if (n.left != null && n.right == null) {
                return n.left;
            } else if (n.left == null && n.right != null) {
                return n.right;
            } else {
                Node maxLeft = findMax(n.left);
                recursiveRemove(n.left, maxLeft.value);
                maxLeft.left = n.left;
                maxLeft.right = n.right;
                return maxLeft;
            }
        }
    }

    private Node findMax(Node n) {
        while (n.right != null) {
            n = n.right;
        }
        return n;
    }