By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,798 Members | 1,343 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,798 IT Pros & Developers. It's quick & easy.

Need help with BinaryTree

P: 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;
  8.         BinaryTreeNode llink;
  9.         BinaryTreeNode rlink;
  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();
  127.             temp.llink = copy(otherTreeRoot.llink);
  128.             temp.rlink = copy(otherTreeRoot.rlink);
  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.          {
  142.             inorder(p.llink);
  143.             System.out.print(p.info + " ");
  144.             inorder(p.rlink);
  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 + " ");
  157.             preorder(p.llink);
  158.             preorder(p.rlink);
  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.          {
  170.             postorder(p.llink);
  171.             postorder(p.rlink);
  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
  185.             return 1 + max(height(p.llink), height(p.rlink));
  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
Share this Question
Share on Google+
1 Reply


Ganon11
Expert 2.5K+
P: 3,652
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

Post your reply

Sign in to post your reply or Sign up for a free account.