16.1. Binary Tree Implementation¶
16.1.1. Nodes in a Binary Tree¶
Much like how we implemented linked lists, we define a BinaryTreeNode class to represent a node in a binary tree.
//Represents a node in a binary tree as a recursive data structure.
public class BinaryTreeNode<T> {
private T value;
private BinaryTreeNode<T> left;
private BinaryTreeNode<T> right;
public BinaryTreeNode(T value) {
this.value = value;
this.left = null;
this.right = null;
}
public T getValue() {
return this.value;
}
public void setValue(T value) {
this.value = value;
}
public BinaryTreeNode<T> getLeft() {
return this.left;
}
public BinaryTreeNode<T> getRight() {
return this.right;
}
public void setLeft(BinaryTreeNode<T> left) {
this.left = left;
}
public void setRight(BinaryTreeNode<T> right) {
this.right = right;
}
// Checks if the node is a leaf node, which means it has no children.
public boolean isLeaf() {
return this.left == null && this.right == null;
}
}
Like our previous node classes, this class has a value instance variable to store the value of the node. Now, we store pointers to the node’s left and right children in left and right instance variables.
There are also the usual getters and setters for the value and left and right instance variables. The one method additional method to note here is isLeaf(), which returns true if the node is a leaf node (i.e. it has no children) and false otherwise:
// Checks if the node is a leaf node, which means it has no children.
public boolean isLeaf() {
return this.left == null && this.right == null;
}
16.1.2. BinaryTree class¶
Carrying over the same idea of our linked list implementations holding a head and tail pointer, our binary tree implementation will hold a root pointer. The root pointer will point to the root node of the binary tree. Below is a partial implementation of the BinaryTree class:
public class BinaryTree<T> {
private BinaryTreeNode<T> root;
public BinaryTree() {
this.root = null;
}
public BinaryTreeNode<T> getRoot() {
return this.root;
}
public void setRoot(BinaryTreeNode<T> root) {
this.root = root;
}
public int size() {
return this.size(this.root);
}
private int size(BinaryTreeNode<T> node) {
if (node == null) {
return 0;
}
return 1 + this.size(node.getLeft()) + this.size(node.getRight());
}
public int height() {
return this.height(this.root);
}
private int height(BinaryTreeNode<T> node) {
// base case: empty node has height 0
if (node == null) {
return 0;
}
// recursive case: height is 1 (for the current node),
// plus the height of the taller subtree
int leftHeight = this.height(node.getLeft());
int rightHeight = this.height(node.getRight());
if (leftHeight > rightHeight) {
return 1 + leftHeight;
} else {
return 1 + rightHeight;
}
}
public boolean isEmpty() {
return this.root == null;
}
}
Note
Notice that the size() and height() methods are defined recursively. We’ll go over their implementations during lecture!
