序言
最近在学习算法相关的东西，有一些树形结构的数据需要打印出来开对不对，比如二分搜索树，于是我就写了一个工具类。希望能帮到大家
效果
这里写图片描述
源码
BST(二分搜索树)
package com.zgh.algorithm.search;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import com.zgh.algorithm.search.TreePrintUtil.TreeNode;
/**
* 二分搜索树
*
* @author zhuguohui
*
*/
public class BST<K extends Comparable<K>, V> {
private int count;
private Node<K, V> root;
private int maxLevel;
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
public void insert(K k, V v) {
Node<K, V> node = new Node<>(k, v);
if (insertToNode(root, node, 0)) {
// 如果是插入则将count+1
count++;
}
}
public Node getRoot() {
return root;
}
/**
*
* @param parint
* @param node
* @return 如果新增返回true，如果只是更新返回false
*/
private boolean insertToNode(Node<K, V> parent, Node<K, V> node, int level) {
if (root == null) {
root = node;
maxLevel = 1;
return true;
}
if (parent.k.compareTo(node.k) == 0) {
// key相同则更新
parent.v = node.v;
return false;
} else if (parent.k.compareTo(node.k) < 0) {
// 如果node比parent大，则插入到右子树
if (parent.right == null) {
parent.right = node;
if (level + 1 > maxLevel) {
maxLevel = level + 1;
}
return true;
}
return insertToNode(parent.right, node, level + 1);
} else {
// 如果node比parent小，则插入左字数
if (parent.left == null) {
parent.left = node;
if (level + 1 > maxLevel) {
maxLevel = level + 1;
}
return true;
}
return insertToNode(parent.left, node, level + 1);
}
}
private static class Node<K extends Comparable<K>, V> implements TreeNode {
K k;
V v;
Node left, right;
public Node(K k, V v) {
this.k = k;
this.v = v;
}
@Override
public String toString() {
return "[" + k + "]";
}
@Override
public String getPrintInfo() {
return toString();
}
@Override
public TreeNode getLeftChild() {
// TODO Auto-generated method stub
return left;
}
@Override
public TreeNode getRightChild() {
// TODO Auto-generated method stub
return right;
}
}
}
TreePrintUtil(打印树形结构工具类)
package com.zgh.algorithm.search;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class TreePrintUtil {
public static void pirnt(TreeNode root) {
// 找到左边的最大偏移量
int maxLeftOffset = findMaxOffset(root, 0, true);
int maxRightOffset = findMaxOffset(root, 0, false);
int offset = Math.max(maxLeftOffset, maxRightOffset);
// 计算最大偏移量
Map<Integer, PrintLine> lineMap = new HashMap();
calculateLines(root, offset, lineMap, 0, true);
Iterator<Integer> lineNumbers = lineMap.keySet().iterator();
int maxLine = 0;
while (lineNumbers.hasNext()) {
int lineNumber = lineNumbers.next();
if (lineNumber > maxLine) {
maxLine = lineNumber;
}
}
for (int i = 0; i <= maxLine; i++) {
PrintLine line = lineMap.get(i);
if (line != null) {
System.out.println(line.getLineString());
}
}
}
private static void calculateLines(TreeNode parent, int offset, Map<Integer, PrintLine> lineMap, int level,
boolean right) {
if (parent == null) {
return;
}
int nameoffset = parent.toString().length() / 2;
PrintLine line = lineMap.get(level);
if (line == null) {
line = new PrintLine();
lineMap.put(level, line);
}
line.putString(right ? offset : (offset - nameoffset), parent.toString());
// 判断有没有下一级
if (parent.getLeftChild() == null && parent.getRightChild() == null) {
return;
}
// 如果有，添加分割线即/\
PrintLine separateLine = lineMap.get(level + 1);
if (separateLine == null) {
separateLine = new PrintLine();
lineMap.put(level + 1, separateLine);
}
if (parent.getLeftChild() != null) {
separateLine.putString(offset - 1, "/");
calculateLines(parent.getLeftChild(), offset - nameoffset - 1, lineMap, level + 2, false);
}
if (parent.getRightChild() != null) {
separateLine.putString(offset + nameoffset + 1, "\\");
calculateLines(parent.getRightChild(), offset + nameoffset + 1, lineMap, level + 2, true);
}
}
/**
* 需要打印的某一行
*
* @author zhuguohui
*
*/
private static class PrintLine {
/**
* 记录了offset和String的map
*/
Map<Integer, String> printItemsMap = new HashMap<>();
int maxOffset = 0;
public void putString(int offset, String info) {
printItemsMap.put(offset, info);
if (offset > maxOffset) {
maxOffset = offset;
}
}
public String getLineString() {
StringBuffer buffer = new StringBuffer();
for (int i = 0; i <= maxOffset; i++) {
String info = printItemsMap.get(i);
if (info == null) {
buffer.append(" ");
} else {
buffer.append(info);
i += info.length();
}
}
return buffer.toString();
}
}
private static int findMaxOffset(TreeNode parent, int offset, boolean findLeft) {
if (parent != null) {
offset += parent.toString().length();
}
if (findLeft && parent.getLeftChild() != null) {
offset += 1;
return findMaxOffset(parent.getLeftChild(), offset, findLeft);
}
if (!findLeft && parent.getRightChild() != null) {
return findMaxOffset(parent.getRightChild(), offset, findLeft);
}
return offset;
}
public interface TreeNode {
String getPrintInfo();
TreeNode getLeftChild();
TreeNode getRightChild();
}
}
使用
要实现打印需要有两步，
第一步
让你的Node类实现TreePrintUtil中的TreeNode接口
public interface TreeNode {
/**
* 需要打印的信息
* @return
*/
String getPrintInfo();
TreeNode getLeftChild();
TreeNode getRightChild();
}
实现如下
private static class Node<K extends Comparable<K>, V> implements TreeNode {
K k;
V v;
Node left, right;
public Node(K k, V v) {
this.k = k;
this.v = v;
}
@Override
public String toString() {
return "[" + k + "]";
}
@Override
public String getPrintInfo() {
return toString();
}
@Override
public TreeNode getLeftChild() {
// TODO Auto-generated method stub
return left;
}
@Override
public TreeNode getRightChild() {
// TODO Auto-generated method stub
return right;
}
}
第二步
返回根元素
public Node getRoot() {
return root;
}
使用如下
package com.zgh.algorithm.search;
public class Demo2 {
public static void main(String[] args) {
BST<Integer, String> bst = new BST<>();
bst.insert(10, "a");
bst.insert(12, "b");
bst.insert(3, "d");
bst.insert(9, "cdd");
bst.insert(33, "cff");
bst.insert(38, "ceee");
bst.insert(1, "aaaa");
bst.insert(0, "dddd");
bst.insert(99, "dddd");
bst.insert(100, "dddd");
bst.insert(7, "dddd");
bst.insert(1, "dddd");
//从根开始打印
TreePrintUtil.pirnt(bst.getRoot());
}
}
