漂亮的打印二进制树 - 从C++转换到Java

Question

是否有人可以帮助实现基于下面的类作为节点类中的Java this website代码：

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

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

的代码是相当打印二叉树：

#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

没有直接替换Java中的运输及工务局局长和setfill方法。但是，您可以创建一个包装PrintStream的新对象，并在编写某些输出时添加所需的填充。例如：

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); 
    } 
} 

使用PaddedWriter类能够从http://www.ihas1337code.com/2010/09/how-to-pretty-print-binary-tree.html重新实现代码如下：

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(); 
    } 

} 

它可以与这个类进行测试：

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)); 
    } 



} 

东西如果使用此代码，则可能需要考虑的因素是在计算间距时不考虑节点的宽度。所以如果你添加一个包含123456789的节点，它将不会很好地打印。