<![CDATA[
CSE143 Simple Binary Tree handout #24
Client Code TreeTest.java
-------------------------
// Stuart Reges
// 2/22/06
//
// Short program that demonstrates the use of the Tree class. Constructs
// a tree of height 4 and prints each of the traversals.
public class TreeTest {
public static void main(String[] args) {
Tree t = new Tree(4);
System.out.println("preorder traversal:");
t.printPreorder();
System.out.println("inorder traversal:");
t.printInorder();
System.out.println("postorder traversal:");
t.printPostorder();
}
}
Sample Execution of TreeTest
----------------------------
preorder traversal:
56
1
61
60
90
86
69
10
50
37
98
24
61
8
29
inorder traversal:
60
61
90
1
69
86
10
56
98
37
24
50
8
61
29
postorder traversal:
60
90
61
69
10
86
1
98
24
37
8
29
61
50
56
Class TreeNode.java
-------------------
// TreeNode is a class for storing a single node of a binary tree of ints.
// It has just data fields and constructors.
public class TreeNode {
public int data; // data stored at this TreeNode
public TreeNode left; // reference to left subtree
public TreeNode right; // reference to right subtree
// post: constructs a leaf node with given data
public TreeNode(int data) {
this(data, null, null);
}
// post: constructs a TreeNode with the given data and links
public TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
Class Tree.java
---------------
// Stuart Reges
// 2/22/06
//
// Simple Tree class that constructs a random tree and that includes methods
// to print the data using a preorder, inorder or postorder traversal.
public class Tree {
private TreeNode overallRoot;
// pre : height >= 0
// post: constructs a perfect binary tree of given height with random
// data values between 0 and 99 inclusive
public Tree(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 TreeNode randomTree(int h) {
if (h == 0)
return null;
else {
int n = (int) (Math.random() * 100);
return new TreeNode(n, randomTree(h - 1), randomTree(h - 1));
}
}
// post: prints the data fields of the tree, one per line, following
// a preorder traversal and using indentation to indicate node depth
public void printPreorder() {
printPreorder(overallRoot, 0);
}
// post: prints the data fields of the tree using a preorder traversal
private void printPreorder(TreeNode root, int level) {
if (root != null) {
for (int i = 0; i < level; i++)
System.out.print(" ");
System.out.println(root.data);
printPreorder(root.left, level + 1);
printPreorder(root.right, level + 1);
}
}
// post: prints the data fields of the tree, one per line, following
// an inorder traversal and using indentation to indicate node depth
public void printInorder() {
printInorder(overallRoot, 0);
}
// post: prints the data fields of the tree using a inorder traversal
private void printInorder(TreeNode root, int level) {
if (root != null) {
printInorder(root.left, level + 1);
for (int i = 0; i < level; i++)
System.out.print(" ");
System.out.println(root.data);
printInorder(root.right, level + 1);
}
}
// post: prints the data fields of the tree, one per line, following
// a postorder traversal and using indentation to indicate node depth
public void printPostorder() {
printPostorder(overallRoot, 0);
}
// post: prints the data fields of the tree using a postorder traversal
private void printPostorder(TreeNode root, int level) {
if (root != null) {
printPostorder(root.left, level + 1);
printPostorder(root.right, level + 1);
for (int i = 0; i < level; i++)
System.out.print(" ");
System.out.println(root.data);
}
}
}
]]>