Root pointer - points to top node (root)

Each node contains:

Left/right pointers - point to subtrees

Data value of Comparable type

Leaf - node with both pointers set to null

Siblings - nodes that come from the same parent node

Depth

Node - number of edges from node to root

Height

Node - number of edges from deepest leaf

Tree - max distance from deepest leaf to root leaf

Level

Node - height

Tree - height of deepest leaf

Parts

Types

Binary Tree Implementation

BinarySearchTree class

private Node root

add(Comparable obj)

find(Comparable obj)

remove(Comparable obj)

print()

Node class

public Comparable data

public Node left, right

addNode(Node newNode)

printNodes()

Left tree values < parent node value

Right tree values > parent node value

add(Comparable obj)

Run time of binary search algorithms

Binary Expression Trees

Shows order the operations must be done

Traversal

Three kinds

**1011010101**

Filled up from left to right

Every node has either two or no pointers

A

B

Which one is the binary search tree?

If you find a non-null node reference

if the value > your value, look to left child

else look to right child

Else replace it with your value

Where would "L" go?

remove(Comparable obj)

One Child

Find the node you want to remove

Make the parent node reference point to the child node

Two Children

Replace the node you want to remove with the node with the next largest value

Look through left nodes until you find the largest one

Delete that node and place its value into the node you want to remove

Inorder

Preorder

Postorder

Parent -> left -> right

Left -> parent -> right

Left -> right -> parent

Balanced Tree

Perfect Tree

Complete Tree

Each node has same number of left and right descendants

If root is not 'null':

Traverse left subtree inorder

Visit root

Traverse right subtree inorder

Using inorder traversal, what is the result of this expression?

find(Comparable obj)

Applications

while node reference is not null

Compare data to obj

if data = obj, return true

if data < obj, compare data of left node

if data < obj, compare data of right node

Work Cited

Barron's AP Computer Science Levels A and AB. 4th ed. Hauppauge: Barron's, 2007. Print.

Horstmann, Cay S., and Cay S. Horstmann. Java Concepts for AP Computer Science. Hoboken, NJ: J. Wiley & Sons, 2008. Print.

http://www.cs.bu.edu/teaching/c/tree/binary/

http://www.geeksforgeeks.org/applications-of-tree-data-structure/

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

What is a binary tree?

Binary Trees are data structures that are hierarchical data structures.

Binary Search Trees

Search application with constantly leaving/entering data (map & set objects in language libraries)

Binary Space Partition

Used in 3D games to determine what objects need to be rendered

Binary Trees

High-width router for storing router tables

Hash Trees

P2P programs and specialized image

Heaps

- heap sort

- implementing Dijkstra's algorithm

- efficient priority queues

- routers

- A*(path finding algorithm for AI app)

Huffman Coding Tree (Chip Uni)

compression algorithms (.jpeg and .mp3)

GGM Trees

Creates trees of pseudo-random numbers in cryptographic applications

Syntax Trees

Used in compilers and calculators for parse expressions

Treap

Randomized data structure used in wireless and network communication

Tree Node Implementation

Implementation of classes

private Object value

private TreeNode left, right

public TreeNode(Object initValue)

public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)

Private Instance Variables

Methods

If root is not 'null':

Visit root

Traverse left subtree preorder

Traverse right subtree preorder

If root is not 'null':

Traverse left subtree postorder

Traverse right subtree postorder

Visit root

Recursive Tree Algorithms

infix : A+B

Prefix : +ab

postfix : AB+

4 * 3 + 2 / 1 - 2 + 6 = 18