Created
September 7, 2017 11:35
-
-
Save deepankarb/4ae7c2a88ed6e9a8a1c636e0c1062f07 to your computer and use it in GitHub Desktop.
Donald Knuth's binary tree drawing algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package org.zg.koch; | |
import android.content.Context; | |
import android.graphics.Canvas; | |
import android.graphics.Paint; | |
import android.graphics.Point; | |
import android.support.annotation.Nullable; | |
import android.util.AttributeSet; | |
import android.view.View; | |
import java.util.ArrayList; | |
import java.util.List; | |
/** | |
* @Author deepankar | |
* @date 6/9/17. | |
*/ | |
public class TreeView extends View { | |
private Node<Integer> tree; | |
public TreeView(Context context) { | |
this(context, null); | |
} | |
public TreeView(Context context, @Nullable AttributeSet attrs) { | |
super(context, attrs); | |
initTree(); | |
} | |
@Override | |
protected void onDraw(Canvas canvas) { | |
super.onDraw(canvas); | |
final float node_size = 10.f; | |
final float scale = 10.0f; | |
final float h = scale * node_size * tree.getDepth(); | |
final int y_offset = (int) ((getHeight() - h) / 2); | |
final int x_offset = (int) node_size; | |
canvas.translate(x_offset, y_offset); | |
canvas.save(); | |
new DrawTree<>(tree, d -> (int) (scale * node_size * d), node_size) | |
.draw(canvas, new Paint()); | |
canvas.restore(); | |
} | |
private void initTree() { | |
tree = new Node<>(0); | |
tree.l = new Node<>(1); | |
tree.r = new Node<>(2); | |
tree.l.l = new Node<>(3); | |
tree.l.l.l = new Node<>(7); | |
tree.l.l.r = new Node<>(8); | |
tree.l.r = new Node<>(4); | |
tree.l.r.l = new Node<>(7); | |
tree.l.r.r = new Node<>(8); | |
tree.r.l = new Node<>(5); | |
tree.r.r = new Node<>(6); | |
tree.r.r.l = new Node<>(7); | |
tree.r.r.r = new Node<>(8); | |
tree.r.l.l = new Node<>(9); | |
tree.r.l.r = new Node<>(10); | |
} | |
static class DrawTree<Data> { | |
public final Node<Data> binTree; | |
private final IntInt grid; | |
private int i; | |
private final float nodeSize; | |
public DrawTree(Node<Data> tree, float nodeSize) { | |
this(tree, y -> 100 * y, nodeSize); | |
} | |
public DrawTree(Node<Data> tree, IntInt grid, float nodeSize) { | |
this.binTree = tree; | |
this.grid = grid; | |
this.nodeSize = nodeSize; | |
} | |
public void draw(Canvas c, Paint p) { | |
i = 0; | |
drawKnuth(c, p, binTree, 0); | |
} | |
private Point drawKnuth(Canvas c, Paint p, Node<Data> binTree, int depth) { | |
Point l_root = null; | |
Point r_root = null; | |
if (binTree.l != null) { | |
l_root = drawKnuth(c, p, binTree.l, depth + 1); | |
} | |
int nx = grid.map(i); | |
int ny = grid.map(depth); | |
c.drawCircle(nx, ny, nodeSize, p); | |
i++; | |
if (binTree.r != null) { | |
r_root = drawKnuth(c, p, binTree.r, depth + 1); | |
} | |
if (binTree.l != null) { | |
c.drawLine(nx, ny, l_root.x, l_root.y, p); | |
} | |
if (binTree.r != null) { | |
c.drawLine(nx, ny, r_root.x, r_root.y, p); | |
} | |
return new Point(nx, ny); | |
} | |
} | |
static class Node<Data> { | |
Node<Data> l; | |
Node<Data> r; | |
public final Data data; | |
public Node(Data d) { | |
data = d; | |
} | |
/** | |
* Flattens a tree in to an list using inorder traversal. | |
* | |
* @return | |
*/ | |
public List<Node<Data>> flatten() { | |
final int depth = getDepth(); | |
ArrayList<Node<Data>> result = new ArrayList<>(2 * depth + 1); | |
if (l != null) | |
result.addAll(l.flatten()); | |
result.add(this); | |
if (r != null) | |
result.addAll(r.flatten()); | |
result.trimToSize(); | |
return result; | |
} | |
public int getDepth() { | |
// Leaf | |
if (l == null && r == null) return 0; | |
if (l == null) return 1 + r.getDepth(); | |
if (r == null) return 1 + l.getDepth(); | |
return 1 + Math.max(l.getDepth(), r.getDepth()); | |
} | |
@Override | |
public String toString() { | |
return String.valueOf(data); | |
} | |
} | |
@FunctionalInterface | |
private interface IntInt { | |
int map(int in); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment