<![CDATA[
CSE143 Simple Binary Tree handout #24
Client Code IntTreeTest.java
----------------------------
// Short program that demonstrates the use of the IntTree class.
public class IntTreeTest {
public static void main(String[] args) {
IntTree t = new IntTree(4);
System.out.println("Tree structure:");
t.printStructure();
System.out.println();
t.printPreorder();
t.printInorder();
t.printPostorder();
}
}
Sample Execution of TreeTest
----------------------------
Tree structure:
99
52
87
93
42
51
42
13
15
15
0
20
94
72
80
preorder: 13 20 72 80 94 15 0 15 93 51 42 42 52 87 99
inorder: 80 72 94 20 0 15 15 13 42 51 42 93 87 52 99
postorder: 80 94 72 0 15 15 20 42 42 51 87 99 52 93 13
Class IntTreeNode.java
----------------------
// IntTreeNode is a class for storing a single node of a binary tree of ints.
// It has just data fields and constructors.
public class IntTreeNode {
public int data; // data stored at this IntTreeNode
public IntTreeNode left; // reference to left subtree
public IntTreeNode right; // reference to right subtree
// post: constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// post: constructs a IntTreeNode with the given data and links
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
Class IntTree.java
------------------
// Stuart Reges
// 2/22/06
//
// Simple class that includes methods to construct a random tree of ints, to
// print the structure, and to print the data using a preorder, inorder or
// postorder traversal.
public class IntTree {
private IntTreeNode overallRoot;
// pre : height >= 0
// post: constructs a perfect binary tree of given height with random
// data values between 0 and 99 inclusive
public IntTree(int height) {
if (height < 0)
throw new IllegalArgumentException();
overallRoot = randomTree(height);
}
// pre : height >= 0
// post: constructs and returns a reference to a perfect binary tree
// of height h with random data values between 0 and 99 inclusive
private IntTreeNode randomTree(int h) {
if (h == 0)
return null;
else {
int n = (int) (Math.random() * 100);
return new IntTreeNode(n, randomTree(h - 1), randomTree(h - 1));
}
}
// post: prints the data fields of the tree using a preorder traversal
public void printPreorder() {
System.out.print("preorder:");
printPreorder(overallRoot);
System.out.println();
}
// post: prints in preorder the data fields of the tree with given root
private void printPreorder(IntTreeNode root) {
if (root != null) {
System.out.print(" " + root.data);
printPreorder(root.left);
printPreorder(root.right);
}
}
// post: prints the data fields of the tree using an inorder traversal
public void printInorder() {
System.out.print("inorder:");
printInorder(overallRoot);
System.out.println();
}
// post: prints in inorder the data fields of the tree with given root
private void printInorder(IntTreeNode root) {
if (root != null) {
printInorder(root.left);
System.out.print(" " + root.data);
printInorder(root.right);
}
}
// post: prints the data fields of the tree using a postorder traversal
public void printPostorder() {
System.out.print("postorder:");
printPostorder(overallRoot);
System.out.println();
}
// post: prints in postorder the data fields of the tree with given root
private void printPostorder(IntTreeNode root) {
if (root != null) {
printPostorder(root.left);
printPostorder(root.right);
System.out.print(" " + root.data);
}
}
// post: prints the data fields of the tree, one per line, following
// an inorder traversal and using indentation to indicate node depth;
// prints right to left so that it looks correct when the output is
// rotated.
public void printStructure() {
printStructure(overallRoot, 0);
}
// post: prints in preorder the data fields of the given tree indenting
// each line to the given level
private void printStructure(IntTreeNode root, int level) {
if (root != null) {
printStructure(root.right, level + 1);
for (int i = 0; i < level; i++)
System.out.print(" ");
System.out.println(root.data);
printStructure(root.left, level + 1);
}
}
}
]]>