Java代写:FIT1012 Binary Tree Printing

代写小程序,用字符通过遍历,打印展示一棵树。

Requirement

In this project you will populate a Binary Search Tree (BST) and print out its contents. For example, a tree built from the input: DBACGHJK will produce an output similar to the tree below:

    D         
   / \        
  B    G      
 / \    \     
A     C  H    
          \   
           J  
            \ 
             K

Notice the tree display is not exact , as shown by the placement of the node “C” . The goal of the exercise to produce a reasonable facsimile of the tree. Since we are limited by output to the console line, the actual display can not be a perfect graphical representation of the tree. Three sample inputs and their respective outputs are provided for you to duplicate or improve upon.

Objectives

The goal of this programming project is for you to master (or at least get practice on) the following tasks:

  • understanding recursion and / or iterative calls within a BST
  • debugging and checking results
  • Analyzing a problem to determine the best approach
  • working with existing code

Helpful code

The main class that will call methods the BST class are provided. This class (ProgProject3.java) defines the inputs, creates the BST and calls the print method (which you will write), in order to display the tree. You should use this code “as is”, and put your work into the printTree method of the BinarySearchTree class.

One Approach

Your solution should be able to print all the nodes of the tree, without any collisions (nodes printing over other nodes), and display each node on its appropriate level and traversal order. Some arrows (\ or /) should be included to help read your tree. Arrows do NOT have to start at one node and end at another node. This is not possible within the structure of using the Console line. View the expected outputs below to see the type of output required.

You are welcome to use any approach, however, I provide my approach below to assist you.

Print Tree:

  • 1) Initialize a 2 dimension array that hold the image or your output. You should only need a 100 by 100 array.
  • 2) call PostArray with the root, and some initial positioning information
  • 3) Print the 2D array. In the print loop, ignore blank rows and columns

PostArray

  • 4) Perform some type of traversal (Preorder, Inorder, Postorder) that will visit a left and right subtrees, and the root.
  • 5) For the left and right subtrees, recursively call this method
  • 6) The method adds the root info (the input letter) to the array as well as / \
  • 7) In my approach I passed the row and column for the root of this subtree, and returned the width of the tree for this method. This information was useful in order to maintain where the next node needed to be placed in the 2D array.
  • 8) I viewed the output as a 2D array where every cell was one character to print out.

Expected Results

Tree for input: DBACGHJK

    D         
   / \        
  B    G      
 / \    \     
A     C  H    
          \   
           J  
            \ 
             K

Tree for input: DACBEFMLGHJK

  D        
 / \       
A   E      
 \   \     
  C   F    
 /     \   
B       M  
       /   
      L    
     /     
    G      
     \     
      H    
       \   
        J  
         \ 
          K

Tree for input: JABCDEFISRQPON

  J                     
 / \                    
A                      S
 \                    / 
  B                  R  
   \                /   
    C              Q    
     \            /     
      D          P      
       \        /       
        E      O        
         \    /         
          F  N          
           \            
            I   

Running the program

The zipped java project file, which contains all your source code in your Eclipse project. This code should include all the code in the attached file, with the BST class have the additional printTree method and other supporting methods. Provide the zip file of the entire Java project provided to you. If I need to reconstruct your project because you only provided source files, you will lose 20% of the project points. If this is not clear to you, see me before or after class.

Since you will be using the ProgProject3 class provided, running your program should be produce a series of tree input statement and their representation using the printTree method.

Working on This Assignment

You should start right away! My effort was about 2 hours, and the total lines of code approximately 50. Your solution may be longer, or perhaps shorter. You should plan on spending at least 4-8 hours on the project.

Grading Criteria

  1. Program provide some display of all the nodes

  2. Nodes are displayed in the proper order and level

  3. Results are totally accurate., meaning all nodes are in the right order and shown on the correct level. There are not overlaps of nodes

  4. Display is compact (no large amounts of unnecessary white space). Three of your sample input demonstrating your approach handles many cases. These inputs are additional elements of the inputs array within the ProgProject3 class. All nodes are unique, no duplicate keys.

Remember arrows between nodes DO NOT have to be complete.