A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
Terminologies
- Root - the top most node in a tree.
- Parent - node that has a child.
- Siblings - nodes with the same parent.
- Leaves - nodes with no children.
- Internal nodes - nodes with at least one child.
- Degree - number of sub trees of a node.
- Edge - connection between one node to another.
- Height - The level of a node is defined by initially letting the root be at level 1.
- Forest - A forest is a set of n ≥ 0 disjoint trees.
Binary Tree
The simplest form of tree is a binary tree. A binary tree consists of a node (called the root node) and left and right sub-trees.
The nodes at the lowest levels of the tree (the ones with no sub-trees) are called leaves.
In an ordered binary tree:
- the keys of all the nodes in the left sub-tree are less than that of the root,
- the keys of all the nodes in the right sub-tree are greater than that of the root,
- the left and right sub-trees are themselves ordered binary trees.
Basic Tree Operations
The Binary Tree element is represented in BinaryTreeNode private class and Binary Tree functionalities are represented in BinaryTree class.
public class BinaryTree {
private class BinaryTreeNode {
private Integer data;
private boolean visited;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(Integer data) {
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
}
// Root node pointer. Will be null for an empty tree
private BinaryTreeNode root;
// Creates an empty binary tree -- a null root pointer
public BinaryTree() {
root = null;
}
}
insert
// Inserts the given data into the binary tree
public void insert(Integer data) {
if (data == null) {
return;
}
root = insert(root, data);
}
// Recursive insert -- given a node pointer, recur down and insert the given
// data into the tree.
private BinaryTreeNode insert(BinaryTreeNode node, Integer data) {
if (node == null) {
node = new BinaryTreeNode(data);
} else {
if (data <= node.getData()) {
node.setLeft(insert(node.getLeft(), data));
} else {
node.setRight(insert(node.getRight(), data));
}
}
return node;
}
lookup
// Returns true if the given target is in the binary tree
public boolean lookup(Integer data) {
return lookup(root, data);
}
// Recursive lookup -- given a node, recur down searching for the given
// data.
private boolean lookup(BinaryTreeNode node, Integer data) {
if (data == null || node == null) {
return false;
} else if (data == node.getData()) {
return true;
} else if (data < node.getData()) {
return lookup(node.getLeft(), data);
} else if (data > node.getData()) {
return lookup(node.getRight(), data);
}
return false;
}
Breadth-first search
// Breadth-first search
public List<Integer> BFS(Integer to) {
resetVerticesVisibility();
List<Integer> BFSPath = new ArrayList<Integer>();
Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
queue.enqueue(this.root);
BFSPath.add(this.root.getData());
this.root.setVisited(true);
while (!queue.isEmpty()) {
BinaryTreeNode middle = queue.dequeue();
if (middle.getData() == to) {
break;
}
if (middle.getLeft() != null && !middle.getLeft().isVisited()) {
BFSPath.add(middle.getLeft().getData());
middle.getLeft().setVisited(true);
queue.enqueue(middle.getLeft());
}
if (middle.getRight() != null && !middle.getRight().isVisited()) {
BFSPath.add(middle.getRight().getData());
middle.getRight().setVisited(true);
queue.enqueue(middle.getRight());
}
}
return BFSPath;
}
Depth-first search
// Depth-first search
public List<Integer> DFS(Integer to) {
resetVerticesVisibility();
List<Integer> DFSPath = new ArrayList<Integer>();
DFS(this.root, to, DFSPath);
if (DFSPath.isEmpty()) {
return null;
} else {
return DFSPath;
}
}
private void DFS(BinaryTreeNode node, Integer to, List<Integer> DFSPath) {
DFSPath.add(node.getData());
node.setVisited(true);
if (node.getData().equals(to)) {
return;
}
if (node.getLeft() != null && !node.getLeft().isVisited()) {
DFS(node.getLeft(), to, DFSPath);
}
if (node.getRight() != null && !node.getRight().isVisited()) {
DFS(node.getRight(), to, DFSPath);
}
}
resetVerticesVisibility
private void resetVerticesVisibility() {
resetVerticesVisibility(this.root);
if (this.root.getLeft() != null) {
resetVerticesVisibility(this.root.getLeft());
}
if (this.root.getRight() != null) {
resetVerticesVisibility(this.root.getRight());
}
}
private void resetVerticesVisibility(BinaryTreeNode node) {
node.setVisited(false);
if (node.getLeft() != null) {
resetVerticesVisibility(node.getLeft());
}
if (node.getRight() != null) {
resetVerticesVisibility(node.getRight());
}
}
maxDepth
// Returns the max root-to-leaf depth of the tree.
public int maxDepth() {
return maxDepth(root);
}
private int maxDepth(BinaryTreeNode node) {
if (node == null) {
return 0;
} else {
int leftDepth = maxDepth(node.getLeft());
int rightDepth = maxDepth(node.getRight());
return Math.max(leftDepth, rightDepth) + 1;
}
}
minValue
// Returns the min value in a non-empty binary search tree
public int minValue() {
return minValue(root);
}
private int minValue(BinaryTreeNode node) {
BinaryTreeNode current = node;
while (current.getLeft() != null) {
current = current.getLeft();
}
return current.getData();
}
maxValue
// Returns the max value in a non-empty binary search tree
public int maxValue() {
return maxValue(root);
}
private int maxValue(BinaryTreeNode node) {
BinaryTreeNode current = node;
while (current.getRight() != null) {
current = current.getRight();
}
return current.getData();
}
hasPathSum
// Given a tree and a sum, returns true if there is a path from the root
// down to a leaf, such that adding up all the values along the path equals
// the given sum.
public boolean hasPathSum(int sum) {
return hasPathSum(root, sum);
}
private boolean hasPathSum(BinaryTreeNode node, int sum) {
if (node == null) {
return (sum == 0);
}
sum = sum - node.getData();
return hasPathSum(node.getLeft(), sum)
|| hasPathSum(node.getRight(), sum);
}
printPaths
// Given a binary tree, prints out all of its root-to-leaf paths, one per
// line
public void printPaths() {
List<Integer> paths = new ArrayList<Integer>();
printPaths(root, paths);
}
private void printPaths(BinaryTreeNode node, List<Integer> paths) {
if (node == null) {
return;
}
paths.add(node.getData());
if (node.getLeft() == null && node.getRight() == null) {
printArray(paths);
// One path is printed so remove that path but do not remove the
// root node
paths.subList(1, paths.size()).clear();
} else {
printPaths(node.getLeft(), paths);
printPaths(node.getRight(), paths);
}
}
private void printArray(List<Integer> paths) {
for (Integer path : paths) {
System.out.print(path + " ");
}
System.out.println();
}
mirror
// Changes the tree into its mirror image
public void mirror() {
mirror(root);
}
private void mirror(BinaryTreeNode node) {
if (node != null) {
mirror(node.getLeft());
mirror(node.getRight());
BinaryTreeNode temp = node.getLeft();
node.setLeft(node.getRight());
node.setRight(temp);
}
}
sameTree
// Compares the receiver to another tree to see if they are structurally
// identical
public boolean sameTree(BinaryTree other) {
return sameTree(root, other.root);
}
private boolean sameTree(BinaryTreeNode nodeA, BinaryTreeNode nodeB) {
if (nodeA == null && nodeB == null) {
return true;
} else if (nodeA != null && nodeB != null) {
return nodeA.getData() == nodeB.getData()
&& sameTree(nodeA.getLeft(), nodeB.getLeft())
&& sameTree(nodeA.getRight(), nodeB.getRight());
}
return false;
}
isBST
// Tests if a tree meets the conditions to be a binary search tree (BST).
public boolean isBST() {
return isBST(root);
}
private boolean isBST(BinaryTreeNode node) {
if (node == null) {
return true;
}
if (node.getLeft() != null && maxValue(node.getLeft()) > node.getData()) {
return false;
}
if (node.getRight() != null
&& minValue(node.getRight()) <= node.getData()) {
return false;
}
return isBST(node.getLeft()) && isBST(node.getRight());
}
printInorder
// Prints the node values in the "inorder" order
public void printInorder() {
printInorder(root);
System.out.println();
}
// inorder: left, node itself, right
private void printInorder(BinaryTreeNode node) {
if (node == null) {
return;
}
printInorder(node.getLeft());
System.out.print(node.getData() + " ");
printInorder(node.getRight());
}
printPostorder
// Prints the node values in the "postorder" order
public void printPostorder() {
printPostorder(root);
System.out.println();
}
// postorder: first recur on both subtrees; then deal with the node
private void printPostorder(BinaryTreeNode node) {
if (node == null) {
return;
}
printInorder(node.getLeft());
printInorder(node.getRight());
System.out.println(node.getData());
}
Evaluation
Complexity Analysis
BSTs support insert, min, delete, rank, etc. in O(h) time, where h = height of tree (= height of root).
h is between log(n) and n.
| Functionality | Complexity |
|---|---|
| Search | Average: O(log n) Worst Case: O(n) |
| Insert | Average: O(log n) Worst Case: O(n) |
| Delete | Average: O(log n) Worst Case: O(n) |
Advantages
- The main advantage of binary search trees is that it remains ordered, which provides quicker search times than many other data structures.
- Another major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
- Binary Search Tree is fast in insertion and deletion etc when balanced.
- Very efficient and its code is easier than other data structures.
- Stores keys in the nodes in a way that searching, insertion and deletion can be done efficiently.
- Implementation is very simple in Binary Search Trees.
- Nodes in tree are dynamic in nature.
Disadvantages
- The shape of the binary search tree totally depends on the order of insertions, and it can be degenerated.
- When inserting or searching for an element in binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found, i.e., it takes a long time to search an element in a binary search tree.
- The keys in the binary search tree may be long and the run time may increase.
Source Code
import java.util.ArrayList;
import java.util.List;
import uk.ac.soton.ecs.datastructure.queue.Queue;
public class BinaryTree {
private class BinaryTreeNode {
private Integer data;
private boolean visited;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(Integer data) {
this.data = data;
this.left = null;
this.right = null;
this.visited = false;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
}
// Root node pointer. Will be null for an empty tree
private BinaryTreeNode root;
// Creates an empty binary tree -- a null root pointer
public BinaryTree() {
root = null;
}
// Inserts the given data into the binary tree
public void insert(Integer data) {
if (data == null) {
return;
}
root = insert(root, data);
}
// Recursive insert -- given a node pointer, recur down and insert the given
// data into the tree.
private BinaryTreeNode insert(BinaryTreeNode node, Integer data) {
if (node == null) {
node = new BinaryTreeNode(data);
} else {
if (data <= node.getData()) {
node.setLeft(insert(node.getLeft(), data));
} else {
node.setRight(insert(node.getRight(), data));
}
}
return node;
}
public List<Integer> BFS(Integer to) {
resetVerticesVisibility();
List<Integer> BFSPath = new ArrayList<Integer>();
Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
queue.enqueue(this.root);
BFSPath.add(this.root.getData());
this.root.setVisited(true);
while (!queue.isEmpty()) {
BinaryTreeNode middle = queue.dequeue();
if (middle.getData() == to) {
break;
}
if (middle.getLeft() != null && !middle.getLeft().isVisited()) {
BFSPath.add(middle.getLeft().getData());
middle.getLeft().setVisited(true);
queue.enqueue(middle.getLeft());
}
if (middle.getRight() != null && !middle.getRight().isVisited()) {
BFSPath.add(middle.getRight().getData());
middle.getRight().setVisited(true);
queue.enqueue(middle.getRight());
}
}
return BFSPath;
}
public List<Integer> DFS(Integer to) {
resetVerticesVisibility();
List<Integer> DFSPath = new ArrayList<Integer>();
DFS(this.root, to, DFSPath);
if (DFSPath.isEmpty()) {
return null;
} else {
return DFSPath;
}
}
private void DFS(BinaryTreeNode node, Integer to, List<Integer> DFSPath) {
DFSPath.add(node.getData());
node.setVisited(true);
if (node.getData().equals(to)) {
return;
}
if (node.getLeft() != null && !node.getLeft().isVisited()) {
DFS(node.getLeft(), to, DFSPath);
}
if (node.getRight() != null && !node.getRight().isVisited()) {
DFS(node.getRight(), to, DFSPath);
}
}
private void resetVerticesVisibility() {
resetVerticesVisibility(this.root);
if (this.root.getLeft() != null) {
resetVerticesVisibility(this.root.getLeft());
}
if (this.root.getRight() != null) {
resetVerticesVisibility(this.root.getRight());
}
}
private void resetVerticesVisibility(BinaryTreeNode node) {
node.setVisited(false);
if (node.getLeft() != null) {
resetVerticesVisibility(node.getLeft());
}
if (node.getRight() != null) {
resetVerticesVisibility(node.getRight());
}
}
// Returns true if the given target is in the binary tree
public boolean lookup(Integer data) {
return lookup(root, data);
}
// Recursive lookup -- given a node, recur down searching for the given
// data.
private boolean lookup(BinaryTreeNode node, Integer data) {
if (data == null || node == null) {
return false;
} else if (data == node.getData()) {
return true;
} else if (data < node.getData()) {
return lookup(node.getLeft(), data);
} else if (data > node.getData()) {
return lookup(node.getRight(), data);
}
return false;
}
// Returns the number of nodes in the tree
public int size() {
return size(root);
}
private int size(BinaryTreeNode node) {
if (node == null) {
return 0;
}
return size(node.getLeft()) + 1 + size(node.getRight());
}
// Returns the max root-to-leaf depth of the tree.
public int maxDepth() {
return maxDepth(root);
}
private int maxDepth(BinaryTreeNode node) {
if (node == null) {
return 0;
} else {
int leftDepth = maxDepth(node.getLeft());
int rightDepth = maxDepth(node.getRight());
return Math.max(leftDepth, rightDepth) + 1;
}
}
// Returns the min value in a non-empty binary search tree
public int minValue() {
return minValue(root);
}
private int minValue(BinaryTreeNode node) {
BinaryTreeNode current = node;
while (current.getLeft() != null) {
current = current.getLeft();
}
return current.getData();
}
// Returns the max value in a non-empty binary search tree
public int maxValue() {
return maxValue(root);
}
private int maxValue(BinaryTreeNode node) {
BinaryTreeNode current = node;
while (current.getRight() != null) {
current = current.getRight();
}
return current.getData();
}
// Given a tree and a sum, returns true if there is a path from the root
// down to a leaf, such that adding up all the values along the path equals
// the given sum.
public boolean hasPathSum(int sum) {
return hasPathSum(root, sum);
}
private boolean hasPathSum(BinaryTreeNode node, int sum) {
if (node == null) {
return (sum == 0);
}
sum = sum - node.getData();
return hasPathSum(node.getLeft(), sum)
|| hasPathSum(node.getRight(), sum);
}
// Given a binary tree, prints out all of its root-to-leaf paths, one per
// line
public void printPaths() {
List<Integer> paths = new ArrayList<Integer>();
printPaths(root, paths);
}
private void printPaths(BinaryTreeNode node, List<Integer> paths) {
if (node == null) {
return;
}
paths.add(node.getData());
if (node.getLeft() == null && node.getRight() == null) {
printArray(paths);
// One path is printed so remove that path but do not remove the
// root node
paths.subList(1, paths.size()).clear();
} else {
printPaths(node.getLeft(), paths);
printPaths(node.getRight(), paths);
}
}
private void printArray(List<Integer> paths) {
for (Integer path : paths) {
System.out.print(path + " ");
}
System.out.println();
}
// Changes the tree into its mirror image
public void mirror() {
mirror(root);
}
private void mirror(BinaryTreeNode node) {
if (node != null) {
mirror(node.getLeft());
mirror(node.getRight());
BinaryTreeNode temp = node.getLeft();
node.setLeft(node.getRight());
node.setRight(temp);
}
}
// Compares the receiver to another tree to see if they are structurally
// identical
public boolean sameTree(BinaryTree other) {
return sameTree(root, other.root);
}
private boolean sameTree(BinaryTreeNode nodeA, BinaryTreeNode nodeB) {
if (nodeA == null && nodeB == null) {
return true;
} else if (nodeA != null && nodeB != null) {
return nodeA.getData() == nodeB.getData()
&& sameTree(nodeA.getLeft(), nodeB.getLeft())
&& sameTree(nodeA.getRight(), nodeB.getRight());
}
return false;
}
// Tests if a tree meets the conditions to be a binary search tree (BST).
public boolean isBST() {
return isBST(root);
}
private boolean isBST(BinaryTreeNode node) {
if (node == null) {
return true;
}
if (node.getLeft() != null && maxValue(node.getLeft()) > node.getData()) {
return false;
}
if (node.getRight() != null
&& minValue(node.getRight()) <= node.getData()) {
return false;
}
return isBST(node.getLeft()) && isBST(node.getRight());
}
// Prints the node values in the "inorder" order
public void printInorder() {
printInorder(root);
System.out.println();
}
// inorder: left, node itself, right
private void printInorder(BinaryTreeNode node) {
if (node == null) {
return;
}
printInorder(node.getLeft());
System.out.print(node.getData() + " ");
printInorder(node.getRight());
}
// Prints the node values in the "postorder" order
public void printPostorder() {
printPostorder(root);
System.out.println();
}
// postorder: first recur on both subtrees; then deal with the node
private void printPostorder(BinaryTreeNode node) {
if (node == null) {
return;
}
printInorder(node.getLeft());
printInorder(node.getRight());
System.out.println(node.getData());
}
}
JUnit Test
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.List;
import org.junit.Test;
public class BinaryTreeTest {
@Test
public void testBinaryTree() {
BinaryTree binaryTree = new BinaryTree();
assertEquals(0, binaryTree.size());
}
@Test
public void testInsert() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertEquals(6, binaryTree.size());
}
@Test
public void testBFS() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(0);
binaryTree.insert(-1);
binaryTree.insert(-2);
binaryTree.insert(10);
List<Integer> bfs = binaryTree.BFS(10);
System.out.println("BFS:");
for (Integer node : bfs) {
System.out.print(node + "->");
}
System.out.println();
}
@Test
public void testDFS() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(0);
binaryTree.insert(-1);
binaryTree.insert(-2);
binaryTree.insert(10);
binaryTree.insert(4);
List<Integer> dfs = binaryTree.DFS(10);
System.out.println("DFS:");
for (Integer node : dfs) {
System.out.print(node + "->");
}
System.out.println();
}
@Test
public void testLookup() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertTrue(binaryTree.lookup(2));
assertFalse(binaryTree.lookup(5));
}
@Test
public void testSize() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertEquals(6, binaryTree.size());
}
@Test
public void testMaxDepth() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertTrue(4 == binaryTree.maxDepth());
}
@Test
public void testMinValue() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertTrue(1 == binaryTree.minValue());
}
@Test
public void testMaxValue() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertTrue(3 == binaryTree.maxValue());
}
@Test
public void testHasPathSum() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
assertFalse(binaryTree.hasPathSum(50));
assertFalse(binaryTree.hasPathSum(3));
assertTrue(binaryTree.hasPathSum(4));
assertTrue(binaryTree.hasPathSum(5));
assertTrue(binaryTree.hasPathSum(6));
assertTrue(binaryTree.hasPathSum(8));
}
@Test
public void testPrintPaths() {
System.out.println("testPrintPaths");
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.printPaths();
System.out.println("**********************");
}
@Test
public void testMirror() {
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.mirror();
}
@Test
public void testSameTree() {
BinaryTree binaryTree1 = new BinaryTree();
binaryTree1.insert(2);
binaryTree1.insert(2);
binaryTree1.insert(3);
binaryTree1.insert(1);
binaryTree1.insert(3);
binaryTree1.insert(1);
BinaryTree binaryTree2 = new BinaryTree();
binaryTree2.insert(2);
binaryTree2.insert(2);
binaryTree2.insert(3);
binaryTree2.insert(1);
binaryTree2.insert(3);
binaryTree2.insert(1);
BinaryTree binaryTree3 = new BinaryTree();
binaryTree3.insert(2);
binaryTree3.insert(2);
binaryTree3.insert(3);
binaryTree3.insert(1);
binaryTree3.insert(3);
assertTrue(binaryTree1.sameTree(binaryTree2));
assertFalse(binaryTree2.sameTree(binaryTree3));
}
@Test
public void testIsBST() {
BinaryTree binaryTree1 = new BinaryTree();
binaryTree1.insert(2);
binaryTree1.insert(2);
binaryTree1.insert(3);
binaryTree1.insert(1);
binaryTree1.insert(3);
binaryTree1.insert(1);
assertTrue(binaryTree1.isBST());
}
@Test
public void testPrintInorder() {
System.out.println("testPrintInorder");
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.printInorder();
System.out.println("**********************");
}
@Test
public void testPrintPostorder() {
System.out.println("testPrintPostorder");
BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(2);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.insert(3);
binaryTree.insert(1);
binaryTree.printPostorder();
System.out.println("**********************");
}
}
No comments:
Post a Comment