Binary Trees and Traversals

You would also learn this on CSE191 @.@

Binary Trees

  • Similar in structure to Linked List
    • Consists of Nodes
    • A Tree is only a reference to the first node (Called the root node)
  • Trees have 2 references to nodes
    • Each node has left and right reference
    • Vocab: These are called its child nodes
    • Vocab: The node is the parent to these children

The Code

1
2
3
class BinaryTreeNode[A](var value: A, var left: BinaryTreeNode[A], var right: BinaryTreeNode[A]) {

}
1
2
3
4
5
6
7
val root = new BinaryTreeNode[Int](5, null, null)
root.left = new BinaryTreeNode[Int](2, null, null)
root.right = new BinaryTreeNode[Int](8, null, null)
root.left.left = new BinaryTreeNode[Int](-3, null, null)
root.left.right = new BinaryTreeNode[Int](4, null, null)
root.right.left = new BinaryTreeNode[Int](7, null, null)
root.right.right = new BinaryTreeNode[Int](14, null, null)
  • Binary Tree Nodes are very similar in structure to Linked List Nodes
  • No simple prepend or append so we’ll manaually build a tree by setting left and right directly

Tree Traversals

  • How do we compute with trees?
    • With linked lists we wrote several methods that recursively visited the next node to visit every value
  • With trees, how do we visit both children of each node?
    • Recursive call on both child nodes
  • We’ll see 3 different approaches
    • Pre-Order Traversal
    • In-Order Traversal
    • Post-Order Traversal

  • Pre-Order Traversal
    • Visit the node’s value
    • Call pre-order on the left child
    • Call pre-order on the right child
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def preOrderTraversal[A](node: BinaryTreeNode[A], f: A => Unit): Unit = {
    if (node != null) {
        f(node.value)
        preOrderTraversal(ndoe.left, f)
        preOrderTraversal(ndoe.right, f)
    }
}

preOrderTraversal(root, println)
/***
5
2
-3
4
8
7
14
***/

  • Post-Order Traversal
    • Call post-order on the left child
    • Call post-order on the right child
    • Visit the node’s value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def postOrderTraversal[A](node: BinaryTreeNode[A], f: A => Unit): Unit = {
    if(node != null) {
        postOrderTraversal(node.left, f)
        postOrderTraversal(node.right, f)
        f(node.value)
    }
}

postOrderTraversal(root, println)
/***
-3
4
2
7
14
8
5
***/

  • In-Order Traversal
    • Call in-order on the left child
    • Visit the node’s value
    • Call in-order on the right child
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def inOrderTraversal[A](node: BinaryTreeNode[A], f: A => Unit): Unit = {
    if (node != null) {
        inOrderTraversal(node.left, f)
        f(node.value)
        inOrderTraversal(node.right, f)
    }
}

inOrderTraversal(root, println)
/***
-3
2
4
5
1
7
8
14
***/

Expression Trees

  • Represent an expression as a binary tree
  • Nodes can be
    • Operands
    • Operators
  • An operand is a literal value
  • An operator is evaluated by using its left and right children as operands
    • Operands can be operators

// 运算符号作为上级，被运算的数字放在它的子项，先算的放在左边子项，最后算的运算符号作为root

Expression Tree Traversals

  • Modified in-order traversal that adds parentheses around each operator
  • Generates a fully parenthesized infix expression
  • ((12-4) - (8+(9/3)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fullyParenthesizedInOrderTraversal[A](node: BinaryTreeNode[A], f: A => Unit): Unit = {
    if (node != null) {
        val operator = List("^", "*", "/", "+", "-").contains(node.value)
        if (operator) {
            print("(")
        }
        fullyParenthesizedInOrderTraversal(node.left, f)
        f(node.value)
        fullyParenthesizedInOrderTraversal(node.right, f)
        if (operator) {
            print(")")
        }
    }
}
  • Unmodified post-order traversal generates a postfix express
1
postOrderTraversal(root, (token: String) => print(token + " "))

Lecture Question

Task:
Evaluate an expression tree (go to example repo) || link

  • In the week8.trees.ExpressionTree object, write a method named evaluateTree that takes the root of an expression tree (BinaryTreeNode[String]) as a parameter and returns the evaluation of the tree as a Double
  • The operators can be “*”, “/“, “+”, and “-“
  • You can assume that all Nodes storing numbers are well- formed (Ie. If a node’s String is not one of the 4 operators, you can call .toDouble on it to convert it to a Double)

Testing:
In a package named “tests” create a class named “TestExpressionTree” as a test suite that tests the functionality above (Only write tests with valid expression trees as input)