Jolie impression d'un arbre binaire - Conversion de C++ Java

Question

Quelqu'un peut-il s'il vous plaît aider à mettre en œuvre le code this website en Java en fonction de la classe suivante comme la classe Node:

public class Node<A extends Comparable<A>> { 
Node<A> left, right; 
A data; 

public Node(A data){ 
    this.data = data; 
} 
} 

Le code est pour à peu l'impression d'arbres binaires :

#include <fstream> 
#include <iostream> 
#include <deque> 
#include <iomanip> 
#include <sstream> 
#include <string> 
#include <cmath> 
using namespace std; 

struct BinaryTree { 
    BinaryTree *left, *right; 
    int data; 
    BinaryTree(int val) : left(NULL), right(NULL), data(val) { } 
}; 

// Find the maximum height of the binary tree 
int maxHeight(BinaryTree *p) { 
    if (!p) return 0; 
    int leftHeight = maxHeight(p->left); 
    int rightHeight = maxHeight(p->right); 
    return (leftHeight > rightHeight) ? leftHeight + 1: rightHeight + 1; 
} 

// Convert an integer value to string 
string intToString(int val) { 
    ostringstream ss; 
    ss << val; 
    return ss.str(); 
} 

// Print the arm branches (eg,/ \) on a line 
void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { 
    deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); 
    for (int i = 0; i < nodesInThisLevel/2; i++) { 
    out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " "); 
    out << setw(2*branchLen+2) << "" << ((*iter++) ? "\\" : " "); 
    } 
    out << endl; 
} 

// Print the branches and node (eg, ___10___) 
void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { 
    deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); 
    for (int i = 0; i < nodesInThisLevel; i++, iter++) { 
    out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' ')); 
    out << setw(branchLen+2) << ((*iter) ? intToString((*iter)->data) : ""); 
    out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' '); 
    } 
    out << endl; 
} 

// Print the leaves only (just for the bottom row) 
void printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) { 
    deque<BinaryTree*>::const_iterator iter = nodesQueue.begin(); 
    for (int i = 0; i < nodesInThisLevel; i++, iter++) { 
    out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) << ((*iter) ? intToString((*iter)->data) : ""); 
    } 
    out << endl; 
} 

// Pretty formatting of a binary tree to the output stream 
// @ param 
// level Control how wide you want the tree to sparse (eg, level 1 has the minimum space between nodes, while level 2 has a larger space between nodes) 
// indentSpace Change this to add some indent space to the left (eg, indentSpace of 0 means the lowest level of the left node will stick to the left margin) 
void printPretty(BinaryTree *root, int level, int indentSpace, ostream& out) { 
    int h = maxHeight(root); 
    int nodesInThisLevel = 1; 

    int branchLen = 2*((int)pow(2.0,h)-1) - (3-level)*(int)pow(2.0,h-1); // eq of the length of branch for each node of each level 
    int nodeSpaceLen = 2 + (level+1)*(int)pow(2.0,h); // distance between left neighbor node's right arm and right neighbor node's left arm 
    int startLen = branchLen + (3-level) + indentSpace; // starting space to the first node to print of each level (for the left most node of each level only) 

    deque<BinaryTree*> nodesQueue; 
    nodesQueue.push_back(root); 
    for (int r = 1; r < h; r++) { 
    printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 
    branchLen = branchLen/2 - 1; 
    nodeSpaceLen = nodeSpaceLen/2 + 1; 
    startLen = branchLen + (3-level) + indentSpace; 
    printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 

    for (int i = 0; i < nodesInThisLevel; i++) { 
     BinaryTree *currNode = nodesQueue.front(); 
     nodesQueue.pop_front(); 
     if (currNode) { 
      nodesQueue.push_back(currNode->left); 
      nodesQueue.push_back(currNode->right); 
     } else { 
     nodesQueue.push_back(NULL); 
     nodesQueue.push_back(NULL); 
     } 
    } 
    nodesInThisLevel *= 2; 
    } 
    printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 
    printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out); 
} 

int main() { 
    BinaryTree *root = new BinaryTree(30); 
    root->left = new BinaryTree(20); 
    root->right = new BinaryTree(40); 
    root->left->left = new BinaryTree(10); 
    root->left->right = new BinaryTree(25); 
    root->right->left = new BinaryTree(35); 
    root->right->right = new BinaryTree(50); 
    root->left->left->left = new BinaryTree(5); 
    root->left->left->right = new BinaryTree(15); 
    root->left->right->right = new BinaryTree(28); 
    root->right->right->left = new BinaryTree(41); 

    cout << "Tree pretty print with level=1 and indentSpace=0\n\n"; 
    // Output to console 
    printPretty(root, 1, 0, cout); 

    cout << "\n\nTree pretty print with level=5 and indentSpace=3,\noutput to file \"tree_pretty.txt\".\n\n"; 
    // Create a file and output to that file 
    ofstream fout("tree_pretty.txt"); 
    // Now print a tree that's more spread out to the file 
    printPretty(root, 5, 0, fout); 

    return 0; 
} 

http://www.ihas1337code.com/2010/09/how-to-pretty-print-binary-tree.html

Answer 1

Il n'y a pas un remplacement direct pour les méthodes de setw et setfill en Java. Cependant, vous pouvez créer un nouvel objet qui enveloppe un PrintStream et ajoute le remplissage requis lorsque vous écrivez une sortie. Par exemple:

import java.io.PrintStream; 
import java.util.Arrays; 

public class PaddedWriter { 
    private int width = 0; 
    private char fillChar = ' '; 
    private final PrintStream writer; 
    public PaddedWriter(PrintStream writer) { 
     this.writer = writer; 
    } 
    void setw(int i) { 
     width = i; 
    } 
    void setfill(char c) { 
     fillChar = c; 
    } 
    void write(String str) { 
     write(str.toCharArray()); 
    } 
    void write(char[] buf) { 
     if (buf.length < width) { 
      char[] pad = new char[width - buf.length]; 
      Arrays.fill(pad, fillChar); 
      writer.print(pad); 
     } 
     writer.print(buf); 
     setw(0); 
    } 
    void write() { 
     char[] pad = new char[width]; 
     Arrays.fill(pad, fillChar); 
     writer.print(pad); 
     setw(0); 
    } 
    void endl() { 
     writer.println(); 
     setw(0); 
    } 
} 

Utilisation de la classe PaddedWriter il est possible de ré-écrire le code de http://www.ihas1337code.com/2010/09/how-to-pretty-print-binary-tree.html comme suit:

import java.util.Deque; 
import java.util.Iterator; 
import java.util.LinkedList; 


public class BinaryTree<T> { 
    final T data; 
    BinaryTree<T> left; 
    BinaryTree<T> right; 
    public BinaryTree(T t) { 
     data = t; 
    } 

    public void setLeft(BinaryTree<T> t) { 
     left = t; 
    } 
    public void setRight(BinaryTree<T> t) { 
     right = t; 
    } 

    public BinaryTree<T> getLeft() { 
     return left; 
    } 
    public BinaryTree<T> getRight() { 
     return right; 
    } 
    @Override 
    public String toString() { 
     if (data == null) { 
      return "null"; 
     } else { 
      return data.toString(); 
     } 
    } 


    // Search for the deepest part of the tree 
    private static <T>int maxHeight(BinaryTree<T> t) { 
     if (t == null) return 0; 
     int leftHeight = maxHeight(t.getLeft()); 
     int rightHeight = maxHeight(t.getRight()); 
     return (leftHeight > rightHeight) ? leftHeight+1: rightHeight+1; 
    } 

    // Pretty formatting of a binary tree to the output stream 
    public static <T>void printPretty(BinaryTree<T> tree, int level, int indentSpace, PaddedWriter out) { 
     int h = maxHeight(tree); 
     int nodesInThisLevel = 1; 
     int branchLen = 2*((int)Math.pow(2.0, h)-1) - (3-level) *(int)Math.pow(2.0, h-1); 
     int nodeSpaceLen = 2+(level+1)*(int)Math.pow(2.0,h); 
     int startLen = branchLen + (3-level) + indentSpace; 

     Deque<BinaryTree<T>> nodesQueue = new LinkedList<BinaryTree<T>>(); 
     nodesQueue.offerLast(tree); 
     for (int r = 1; r < h; r++) { 
      printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 
      branchLen = branchLen/2 - 1; 
      nodeSpaceLen = nodeSpaceLen/2 + 1; 
      startLen = branchLen + (3-level) + indentSpace; 
      printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 

      for (int i = 0; i < nodesInThisLevel; i++) { 
       BinaryTree<T> currNode = nodesQueue.pollFirst(); 
       if (currNode!=null) { 
        nodesQueue.offerLast(currNode.getLeft()); 
        nodesQueue.offerLast(currNode.getRight()); 
       } else { 
        nodesQueue.offerLast(null); 
        nodesQueue.offerLast(null); 
       } 
      } 
      nodesInThisLevel *= 2; 
     } 
     printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out); 
     printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out); 
    } 

    private static <T>void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque<BinaryTree<T>> nodesQueue, PaddedWriter out) { 
     Iterator<BinaryTree<T>> iterator = nodesQueue.iterator(); 
     for (int i = 0; i < nodesInThisLevel/2; i++) { 
      if (i == 0) { 
       out.setw(startLen-1); 
      } else { 
       out.setw(nodeSpaceLen-2); 
      } 
      out.write(); 
      BinaryTree<T> next = iterator.next(); 
      if (next != null) { 
       out.write("/"); 
      } else { 
       out.write(" "); 
      } 
      out.setw(2*branchLen+2); 
      out.write(); 
      next = iterator.next(); 
      if (next != null) { 
       out.write("\\"); 
      } else { 
       out.write(" "); 
      } 
     } 
     out.endl(); 
    } 

    // Print the branches and node (eg, ___10___) 
    private static <T>void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, Deque<BinaryTree<T>> nodesQueue, PaddedWriter out) { 
     Iterator<BinaryTree<T>> iterator = nodesQueue.iterator(); 
     BinaryTree<T> currentNode; 
     for (int i = 0 ; i < nodesInThisLevel; i++) { 
      currentNode = iterator.next(); 
      if (i == 0) { 
       out.setw(startLen); 
      } else { 
       out.setw(nodeSpaceLen); 
      } 
      out.write(); 
      if (currentNode != null && currentNode.getLeft() != null) { 
       out.setfill('_'); 
      } else { 
       out.setfill(' '); 
      } 
      out.setw(branchLen+2); 
      if (currentNode != null) { 
       out.write(currentNode.toString()); 
      } else { 
       out.write(); 
      } 
      if (currentNode != null && currentNode.getRight() != null) { 
       out.setfill('_'); 
      } else { 
       out.setfill(' '); 
      } 
      out.setw(branchLen); 
      out.write(); 
      out.setfill(' '); 
     } 
     out.endl(); 
    } 

    // Print the leaves only (just for the bottom row) 
    private static <T>void printLeaves(int indentSpace, int level, int nodesInThisLevel, Deque<BinaryTree<T>> nodesQueue, PaddedWriter out) { 
     Iterator<BinaryTree<T>> iterator = nodesQueue.iterator(); 
     BinaryTree<T> currentNode; 
     for (int i = 0; i < nodesInThisLevel; i++) { 
      currentNode = iterator.next(); 
      if (i == 0) { 
       out.setw(indentSpace+2); 
      } else { 
       out.setw(2*level+2); 
      } 
      if (currentNode !=null) { 
       out.write(currentNode.toString()); 
      } else { 
       out.write(); 
      } 
     } 
     out.endl(); 
    } 

} 

Il peut être testé avec cette classe:

public class Tester { 
    public static void main(String[] args) { 

     BinaryTree<Integer> root = new BinaryTree<Integer>(30); 
     root.setLeft(new BinaryTree<Integer>(20)); 
     root.setRight(new BinaryTree<Integer>(40)); 
     root.getLeft().setLeft(new BinaryTree<Integer>(10)); 
     root.getLeft().setRight(new BinaryTree<Integer>(25)); 
     root.getRight().setLeft(new BinaryTree<Integer>(35)); 
     root.getRight().setRight(new BinaryTree<Integer>(50)); 
     root.getLeft().getLeft().setLeft(new BinaryTree<Integer>(5)); 
     root.getLeft().getLeft().setRight(new BinaryTree<Integer>(15)); 
     root.getLeft().getRight().setRight(new BinaryTree<Integer>(28)); 
     root.getRight().getRight().setLeft(new BinaryTree<Integer>(41)); 


     BinaryTree.printPretty(root, 1, 0, new PaddedWriter(System.out)); 
    } 



} 

Quelque chose qui vous pourriez vouloir prendre en compte si vous utilisez ce code, c'est que la largeur du nœud n'est pas prise en compte lors de l'élaboration de l'espacement. Donc, si vous avez ajouté un nœud contenant 123456789, il ne sera pas très bien imprimé.