Java Reference
In-Depth Information
preorder: 1 2 4 8 9 5 10 11 3 6 12 7
inorder: 8 4 9 2 10 5 11 1 12 6 3 7
postorder: 8 9 4 10 11 5 2 12 6 7 3 1
Here is the complete
IntTree
class:
1 // Simple binary tree class that includes methods to construct a
2 // tree of ints, to print the structure, and to print the data
3 // using a preorder, inorder, or postorder traversal. The trees
4 // built have nodes numbered starting with 1 and numbered
5 // sequentially level by level with no gaps in the tree. The
6 // documentation refers to these as "sequential trees."
7
8
public class
IntTree {
9
private
IntTreeNode overallRoot;
10
11 // pre : max > 0
12 // post: constructs a sequential tree with given number of
13 // nodes
14
public
IntTree(
int
max) {
15
if
(max <= 0) {
16
throw new
IllegalArgumentException("max: " + max);
17 }
18 overallRoot = buildTree(1, max);
19 }
20
21 // post: returns a sequential tree with n as its root unless
22 // n is greater than max, in which case it returns an
23 // empty tree
24
private
IntTreeNode buildTree(
int
n,
int
max) {
25
if
(n > max) {
26
return
null;
27 }
else
{
28
return new
IntTreeNode(n, buildTree(2 * n, max),
29 buildTree(2 * n + 1, max));
30 }
31 }
32
33 // post: prints the tree contents using a preorder traversal
34
public void
printPreorder() {
35 System.out.print("preorder:");
36 printPreorder(overallRoot);
37 System.out.println();
38 }
Search WWH ::
Custom Search