468,783 Members | 1,593 Online

# Need help with BinaryTree

28
I need to write the definition of the method leavesCount that takes as a parameter a reference of the root node of a binary tree and returns the numbers of leaves in the binary tree. This what i get so far

Expand|Select|Wrap|Line Numbers
1. public class BinaryTree
2. {
3.
4.          //Definition of the node
5.     protected class BinaryTreeNode
6.     {
7.         DataElement info;
10.     }
11.
12.     protected BinaryTreeNode root;
13.
14.        //default constructor
15.        //Postcondition: root = null;
16.     public BinaryTree()
17.     {
18.          root = null;
19.     }
20.
21.        //copy constructor
22.     public BinaryTree(BinaryTree otherTree)
23.     {
24.          if(otherTree.root == null) //otherTree is empty
25.             root = null;
26.          else
27.             root = copy(otherTree.root);
28.     }
29.
30.        //Method to determine whether the binary tree is empty.
31.        //Postcondition: Returns true if the binary tree is empty;
32.        //               otherwise, returns false.
33.     public boolean isEmpty()
34.     {
35.          return (root == null);
36.     }
37.
38.        //Method to do an inorder traversal of the binary tree.
39.        //Postcondition: The nodes of the binary tree are output
40.        //               in the inorder sequence.
41.     public void inorderTraversal()
42.     {
43.          inorder(root);
44.     }
45.
46.        //Method to do a preorder traversal of the binary tree.
47.        //Postcondition: The nodes of the binary tree are output
48.        //               in the preorder sequence.
49.     public void preorderTraversal()
50.     {
51.          preorder(root);
52.     }
53.
54.        //Method to do a postorder traversal of the binary tree.
55.        //Postcondition: The nodes of the binary tree are output
56.        //               in the postorder sequence.
57.     public void postorderTraversal()
58.     {
59.          postorder(root);
60.     }
61.
62.        //Method to determine the height of the binary tree.
63.        //Postcondition: The height of the binary tree is returned.
64.     public int treeHeight()
65.     {
66.          return height(root);
67.     }
68.
69.        //Method to determine the number of nodes in the
70.        //binary tree.
71.        //Postcondition: The number of nodes in the binary tree
72.        //               is returned.
73.     public int treeNodeCount()
74.     {
75.          return nodeCount(root);
76.     }
77.
78.        //Method to determine the number of leaves in the
79.        //binary tree.
80.        //Postcondition: The number of leaves in the binary tree
81.        //               is returned.
82.     public int treeLeavesCount()
83.     {
84.          return leavesCount(root);
85.     }
86.
87.        //Method to destroy the binary tree.
88.        //Postcondition: root = null
89.     public void destroyTree()
90.     {
91.         root = null;
92.     }
93.
94.         //Method to make a copy of the binary tree
95.        //specified by otherTree points.
96.        //Postcondition: A copy of otherTree is assigned to
97.        //               this binary tree.
98.     public void copyTree(BinaryTree otherTree)
99.     {
100.
101.          if(this != otherTree) //avoid self-copy
102.          {
103.             root = null;
104.
105.             if(otherTree.root != null) //otherTree is nonempty
106.                root = copy(otherTree.root);
107.          }
108.
109.     }
110.
111.         //Method to make a copy of the binary tree to
112.         //which otherTreeRoot points.
113.         //Postcondition: A copy of the binary tree to which
114.         //               otherTreeRoot is created and the reference of
115.         //               the root node of the copied binary tree
116.         //               is returned.
117.     private BinaryTreeNode copy(BinaryTreeNode otherTreeRoot)
118.     {
119.          BinaryTreeNode temp;
120.
121.          if(otherTreeRoot == null)
122.             temp = null;
123.          else
124.          {
125.             temp = new BinaryTreeNode();
126.             temp.info = otherTreeRoot.info.getCopy();
129.          }
130.
131.          return temp;
132.     }//end copy
133.
134.        //Method to do an inorder traversal of the binary
135.        //tree to which p points.
136.        //Postcondition: The nodes of the binary tree to which p
137.        //               points are output in the inorder sequence.
138.     private void inorder(BinaryTreeNode p)
139.     {
140.          if(p != null)
141.          {
143.             System.out.print(p.info + " ");
145.          }
146.     }
147.
148.        //Method to do a preorder traversal of the binary
149.        //tree to which p points.
150.        //Postcondition: The nodes of the binary tree to which p
151.        //               points are output in the preorder sequence.
152.     private void preorder(BinaryTreeNode p)
153.     {
154.          if(p != null)
155.          {
156.             System.out.print(p.info + " ");
159.          }
160.     }
161.
162.        //Method to do a postorder traversal of the binary
163.        //tree to which p points.
164.        //Postcondition: The nodes of the binary tree to which p
165.        //               points are output in the postorder sequence.
166.     private void postorder(BinaryTreeNode p)
167.     {
168.          if(p != null)
169.          {
172.             System.out.print(p.info + " ");
173.          }
174.     }
175.
176.        //Method to determine the height of the binary tree
177.        //to which p points.
178.        //Postcondition: The height of the binary tree to which p
179.        //               points is returned.
180.     private int height(BinaryTreeNode p)
181.     {
182.          if(p == null)
183.             return 0;
184.          else
186.     }
187.
188.        //Method to determine the larger of x and y.
189.        //Postcondition: The larger of x and y is returned.
190.     private int max(int x, int y)
191.     {
192.          if(x >= y)
193.             return x;
194.          else
195.             return y;
196.     }
197.
198.           }
199.        //Method to determine the number of leaves in the binary
200.        //tree to which p points.
201.        //Postcondition: The number of leaves in the binary tree
202.        //               to which p points is returned.
203.     private int leavesCount(BinaryTreeNode p)
204.     {
205.
206. }
Dec 9 '06 #1
1 4260
Ganon11
3,652 Expert 2GB
OK, what ideas do you have concerning the solution of this problem?

Also, have you looked at some code for preorder/postorder/inorder traversals of a tree?
Dec 9 '06 #2