二叉树的分类
完全二叉树与满二叉树
image.png
二叉搜索树BST
image.png
平衡二叉搜索树BBST
因为二叉搜索树有可能退化为链表,降低查询效率,所以有了平衡二叉搜索树
经典的常见平衡二叉搜索树
AVL
Window NT内核中广泛使用
红黑树
java的TreeMap,HashMap
Linux的进程调度
Ngnix的timer管理
AVL树
image.png
B树
image.png
二叉树的遍历
前序遍历
image.png
image.png
递归版本代码
public class _二叉树的前序遍历递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("前序遍历递归");
preOrderRecur(treeNode);
}
public static void preOrderRecur(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " -> ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
}
非递归版本代码
public class _二叉树的前序遍历非递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("前序遍历非递归");
preOrderNoCycle(treeNode);
}
private static void preOrderNoCycle(TreeNode root) {
if (root == null){
return;
}
TreeNode current;
//把LinkedList当栈使用
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
s.addFirst(root);
while (!s.isEmpty()) {
current = s.removeFirst();
System.out.print(current.val + " -> ");
if (current.right != null){
s.addFirst(current.right);
}
if (current.left != null){
s.addFirst(current.left);
}
}
}
}
中序遍历
image.png
image.png
递归版本代码
public class _二叉树的中序遍历递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("中序遍历递归");
midOrderRecur(treeNode);
}
public static void midOrderRecur(TreeNode root) {
if (root == null) {
return;
}
midOrderRecur(root.left);
System.out.print(root.val + " -> ");
midOrderRecur(root.right);
}
}
非递归版本
public class _二叉树的中序遍历非递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("中序遍历非递归");
midOrderNoCycle(treeNode);
}
public static void midOrderNoCycle(TreeNode root) {
if (root == null) {
return;
}
//把LinkedList作为栈使用
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
TreeNode current=root;
while (current != null || !s.isEmpty()) {
while (current != null) {
s.addFirst(current);
current = current.left;
}
if (!s.isEmpty()) {
current = s.removeFirst();
System.out.print(current.val + " -> ");
current = current.right;
}
}
}
}
后续遍历
image.png
image.png
后序遍历递归代码
public class _二叉树的后序遍历递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("后序遍历递归");
afterOrderRecur(treeNode);
}
public static void afterOrderRecur(TreeNode root) {
if (root == null) {
return;
}
afterOrderRecur(root.left);
afterOrderRecur(root.right);
System.out.print(root.val + " -> ");
}
}
后序遍历非递归代码
public class _二叉树的后序遍历非递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("后序遍历非递归");
afterOrderRecur(treeNode);
}
//后序遍历的方法：先左子树，后右子树，再最后根节点
//如果反过来，顺序就变成了：先根节点，后右子树，再左子树，和先序遍历有点像
//因此，后序遍历可以变为：先遍历根节点，后遍历右子树，再遍历左子树结果的逆序
public static void afterOrderRecur(TreeNode root) {
Stack<Integer> result = new Stack<>();
if (root == null) {
return;
}
TreeNode current;
LinkedList<TreeNode> stack = new LinkedList<>();
stack.addFirst(root);
while (!stack.isEmpty()) {
current = stack.removeFirst();
result.push(current.val);
if (current.left != null) {
stack.addFirst(current.left);
}
if (current.right != null) {
stack.addFirst(current.right);
}
}
while (!result.isEmpty()){
System.out.print(result.pop()+"->");
}
}
}
层序遍历
image.png
层序遍历非递归代码
public class _二叉树的层序遍历非递归 {
public static void main(String[] args) {
final TreeNode treeNode = TreeCommon.genTree();
System.out.println("层遍历非递归");
levelOrder(treeNode);
}
/*层序遍历，就是按照每一层的顺序，一层一层的访问*/
//根据层次遍历的特点，我们很容易想到应该使用队列
//利用广度优先遍历的方式，进行遍历
public static List<List<Integer>> levelOrder(TreeNode root){
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> lists = new ArrayList<>();
List<Integer> arrays = new ArrayList<>();
TreeNode temp = null;
while(!queue.isEmpty()){
int n = queue.size();
//这里通过读取队列的元素，获取这一层有多少个元素
for(int i = 0; i < n; i++){
temp = queue.poll();
arrays.add(temp.val);
if(temp.left != null){
queue.add(temp.left);
}
if(temp.right != null){
queue.add(temp.right);
}
}
//将每一层的数据都放入链表中
lists.add(new ArrayList<>(arrays));
arrays.clear();
}
for (List<Integer> list : lists) {
for (Integer integer : list) {
System.out.print(integer+"->");
}
}
return lists;
}
}
公共部分代码
TreeCommon
public class TreeCommon {
public static TreeNode genTree(){
final TreeNode rootNode = new TreeNode(3);
rootNode.left = new TreeNode(4);
rootNode.right = new TreeNode(5);
rootNode.left.left = new TreeNode(6);
rootNode.left.right = new TreeNode(7);
rootNode.left.right.left = new TreeNode(9);
rootNode.left.right.right = new TreeNode(12);
rootNode.right.right = new TreeNode(8);
BinaryTrees.println(new BinaryTreeInfo() {
@Override
public Object root() {
return rootNode;
}
@Override
public Object left(Object node) {
return ((TreeNode) node).left;
}
@Override
public Object right(Object node) {
return ((TreeNode) node).right;
}
@Override
public Object string(Object node) {
return ((TreeNode) node).val;
}
});
return rootNode;
}
}
BinaryTrees
public final class BinaryTrees {
private BinaryTrees() {
}
public static void print(BinaryTreeInfo tree) {
print(tree, null);
}
public static void println(BinaryTreeInfo tree) {
println(tree, null);
}
public static void print(BinaryTreeInfo tree, PrintStyle style) {
if (tree == null || tree.root() == null) return;
printer(tree, style).print();
}
public static void println(BinaryTreeInfo tree, PrintStyle style) {
if (tree == null || tree.root() == null) return;
printer(tree, style).println();
}
public static String printString(BinaryTreeInfo tree) {
return printString(tree, null);
}
public static String printString(BinaryTreeInfo tree, PrintStyle style) {
if (tree == null || tree.root() == null) return null;
return printer(tree, style).printString();
}
private static Printer printer(BinaryTreeInfo tree, PrintStyle style) {
if (style == PrintStyle.INORDER) return new InorderPrinter(tree);
return new LevelOrderPrinter(tree);
}
public enum PrintStyle {
LEVEL_ORDER, INORDER
}
}
BinaryTreeInfo
public interface BinaryTreeInfo {
/**
* who is the root node
*/
Object root();
/**
* how to get the left child of the node
*/
Object left(Object node);
/**
* how to get the right child of the node
*/
Object right(Object node);
/**
* how to print the node
*/
Object string(Object node);
}
TreeNode
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Printer
public abstract class Printer {
/**
* 二叉树的基本信息
*/
protected BinaryTreeInfo tree;
public Printer(BinaryTreeInfo tree) {
this.tree = tree;
}
/**
* 生成打印的字符串
*/
public abstract String printString();
/**
* 打印后换行
*/
public void println() {
print();
System.out.println();
}
/**
* 打印
*/
public void print() {
System.out.print(printString());
}
}
InorderPrinter
public class InorderPrinter extends Printer {
private static String rightAppend;
private static String leftAppend;
private static String blankAppend;
private static String lineAppend;
static {
int length = 2;
rightAppend = "┌" + Strings.repeat("─", length);
leftAppend = "└" + Strings.repeat("─", length);
blankAppend = Strings.blank(length + 1);
lineAppend = "│" + Strings.blank(length);
}
public InorderPrinter(BinaryTreeInfo tree) {
super(tree);
}
@Override
public String printString() {
StringBuilder string = new StringBuilder(
printString(tree.root(), "", "", ""));
string.deleteCharAt(string.length() - 1);
return string.toString();
}
/**
* 生成node节点的字符串
* @param nodePrefix node那一行的前缀字符串
* @param leftPrefix node整棵左子树的前缀字符串
* @param rightPrefix node整棵右子树的前缀字符串
* @return
*/
private String printString(
Object node,
String nodePrefix,
String leftPrefix,
String rightPrefix) {
Object left = tree.left(node);
Object right = tree.right(node);
String string = tree.string(node).toString();
int length = string.length();
if (length % 2 == 0) {
length--;
}
length >>= 1;
String nodeString = "";
if (right != null) {
rightPrefix += Strings.blank(length);
nodeString += printString(right,
rightPrefix + rightAppend,
rightPrefix + lineAppend,
rightPrefix + blankAppend);
}
nodeString += nodePrefix + string + "\n";
if (left != null) {
leftPrefix += Strings.blank(length);
nodeString += printString(left,
leftPrefix + leftAppend,
leftPrefix + blankAppend,
leftPrefix + lineAppend);
}
return nodeString;
}
}
LevelOrderPrinter
public class LevelOrderPrinter extends Printer {
/**
* 节点之间允许的最小间距（最小只能填1）
*/
private static final int MIN_SPACE = 1;
private Node root;
private int minX;
private int maxWidth;
public LevelOrderPrinter(BinaryTreeInfo tree) {
super(tree);
root = new Node(tree.root(), tree);
maxWidth = root.width;
}
@Override
public String printString() {
// nodes用来存放所有的节点
List<List<Node>> nodes = new ArrayList<>();
fillNodes(nodes);
cleanNodes(nodes);
compressNodes(nodes);
addLineNodes(nodes);
int rowCount = nodes.size();
// 构建字符串
StringBuilder string = new StringBuilder();
for (int i = 0; i < rowCount; i++) {
if (i != 0) {
string.append("\n");
}
List<Node> rowNodes = nodes.get(i);
StringBuilder rowSb = new StringBuilder();
for (Node node : rowNodes) {
int leftSpace = node.x - rowSb.length() - minX;
rowSb.append(Strings.blank(leftSpace));
rowSb.append(node.string);
}
string.append(rowSb);
}
return string.toString();
}
/**
* 添加一个元素节点
*/
private Node addNode(List<Node> nodes, Object btNode) {
Node node = null;
if (btNode != null) {
node = new Node(btNode, tree);
maxWidth = Math.max(maxWidth, node.width);
nodes.add(node);
} else {
nodes.add(null);
}
return node;
}
/**
* 以满二叉树的形式填充节点
*/
private void fillNodes(List<List<Node>> nodes) {
if (nodes == null) return;
// 第一行
List<Node> firstRowNodes = new ArrayList<>();
firstRowNodes.add(root);
nodes.add(firstRowNodes);
// 其他行
while (true) {
List<Node> preRowNodes = nodes.get(nodes.size() - 1);
List<Node> rowNodes = new ArrayList<>();
boolean notNull = false;
for (Node node : preRowNodes) {
if (node == null) {
rowNodes.add(null);
rowNodes.add(null);
} else {
Node left = addNode(rowNodes, tree.left(node.btNode));
if (left != null) {
node.left = left;
left.parent = node;
notNull = true;
}
Node right = addNode(rowNodes, tree.right(node.btNode));
if (right != null) {
node.right = right;
right.parent = node;
notNull = true;
}
}
}
// 全是null，就退出
if (!notNull) break;
nodes.add(rowNodes);
}
}
/**
* 删除全部null、更新节点的坐标
*/
private void cleanNodes(List<List<Node>> nodes) {
if (nodes == null) return;
int rowCount = nodes.size();
if (rowCount < 2) return;
// 最后一行的节点数量
int lastRowNodeCount = nodes.get(rowCount - 1).size();
// 每个节点之间的间距
int nodeSpace = maxWidth + 2;
// 最后一行的长度
int lastRowLength = lastRowNodeCount * maxWidth
+ nodeSpace * (lastRowNodeCount - 1);
// 空集合
Collection<Object> nullSet = Collections.singleton(null);
for (int i = 0; i < rowCount; i++) {
List<Node> rowNodes = nodes.get(i);
int rowNodeCount = rowNodes.size();
// 节点左右两边的间距
int allSpace = lastRowLength - (rowNodeCount - 1) * nodeSpace;
int cornerSpace = allSpace / rowNodeCount - maxWidth;
cornerSpace >>= 1;
int rowLength = 0;
for (int j = 0; j < rowNodeCount; j++) {
if (j != 0) {
// 每个节点之间的间距
rowLength += nodeSpace;
}
rowLength += cornerSpace;
Node node = rowNodes.get(j);
if (node != null) {
// 居中（由于奇偶数的问题，可能有1个符号的误差）
int deltaX = (maxWidth - node.width) >> 1;
node.x = rowLength + deltaX;
node.y = i;
}
rowLength += maxWidth;
rowLength += cornerSpace;
}
// 删除所有的null
rowNodes.removeAll(nullSet);
}
}
/**
* 压缩空格
*/
private void compressNodes(List<List<Node>> nodes) {
if (nodes == null) return;
int rowCount = nodes.size();
if (rowCount < 2) return;
for (int i = rowCount - 2; i >= 0; i--) {
List<Node> rowNodes = nodes.get(i);
for (Node node : rowNodes) {
Node left = node.left;
Node right = node.right;
if (left == null && right == null) continue;
if (left != null && right != null) {
// 让左右节点对称
node.balance(left, right);
// left和right之间可以挪动的最小间距
int leftEmpty = node.leftBoundEmptyLength();
int rightEmpty = node.rightBoundEmptyLength();
int empty = Math.min(leftEmpty, rightEmpty);
empty = Math.min(empty, (right.x - left.rightX()) >> 1);
// left、right的子节点之间可以挪动的最小间距
int space = left.minLevelSpaceToRight(right) - MIN_SPACE;
space = Math.min(space >> 1, empty);
// left、right往中间挪动
if (space > 0) {
left.translateX(space);
right.translateX(-space);
}
// 继续挪动
space = left.minLevelSpaceToRight(right) - MIN_SPACE;
if (space < 1) continue;
// 可以继续挪动的间距
leftEmpty = node.leftBoundEmptyLength();
rightEmpty = node.rightBoundEmptyLength();
if (leftEmpty < 1 && rightEmpty < 1) continue;
if (leftEmpty > rightEmpty) {
left.translateX(Math.min(leftEmpty, space));
} else {
right.translateX(-Math.min(rightEmpty, space));
}
} else if (left != null) {
left.translateX(node.leftBoundEmptyLength());
} else { // right != null
right.translateX(-node.rightBoundEmptyLength());
}
}
}
}
private void addXLineNode(List<Node> curRow, Node parent, int x) {
Node line = new Node("─");
line.x = x;
line.y = parent.y;
curRow.add(line);
}
private Node addLineNode(List<Node> curRow, List<Node> nextRow, Node parent, Node child) {
if (child == null) return null;
Node top = null;
int topX = child.topLineX();
if (child == parent.left) {
top = new Node("┌");
curRow.add(top);
for (int x = topX + 1; x < parent.x; x++) {
addXLineNode(curRow, parent, x);
}
} else {
for (int x = parent.rightX(); x < topX; x++) {
addXLineNode(curRow, parent, x);
}
top = new Node("┐");
curRow.add(top);
}
// 坐标
top.x = topX;
top.y = parent.y;
child.y = parent.y + 2;
minX = Math.min(minX, child.x);
// 竖线
Node bottom = new Node("│");
bottom.x = topX;
bottom.y = parent.y + 1;
nextRow.add(bottom);
return top;
}
private void addLineNodes(List<List<Node>> nodes) {
List<List<Node>> newNodes = new ArrayList<>();
int rowCount = nodes.size();
if (rowCount < 2) return;
minX = root.x;
for (int i = 0; i < rowCount; i++) {
List<Node> rowNodes = nodes.get(i);
if (i == rowCount - 1) {
newNodes.add(rowNodes);
continue;
}
List<Node> newRowNodes = new ArrayList<>();
newNodes.add(newRowNodes);
List<Node> lineNodes = new ArrayList<>();
newNodes.add(lineNodes);
for (Node node : rowNodes) {
addLineNode(newRowNodes, lineNodes, node, node.left);
newRowNodes.add(node);
addLineNode(newRowNodes, lineNodes, node, node.right);
}
}
nodes.clear();
nodes.addAll(newNodes);
}
private static class Node {
/**
* 顶部符号距离父节点的最小距离（最小能填0）
*/
private static final int TOP_LINE_SPACE = 1;
Object btNode;
Node left;
Node right;
Node parent;
/**
* 首字符的位置
*/
int x;
int y;
int treeHeight;
String string;
int width;
private void init(String string) {
string = (string == null) ? "null" : string;
string = string.isEmpty() ? " " : string;
width = string.length();
this.string = string;
}
public Node(String string) {
init(string);
}
public Node(Object btNode, BinaryTreeInfo opetaion) {
init(opetaion.string(btNode).toString());
this.btNode = btNode;
}
/**
* 顶部方向字符的X（极其重要）
*
* @return
*/
private int topLineX() {
// 宽度的一半
int delta = width;
if (delta % 2 == 0) {
delta--;
}
delta >>= 1;
if (parent != null && this == parent.left) {
return rightX() - 1 - delta;
} else {
return x + delta;
}
}
/**
* 右边界的位置（rightX 或者 右子节点topLineX的下一个位置）（极其重要）
*/
private int rightBound() {
if (right == null) return rightX();
return right.topLineX() + 1;
}
/**
* 左边界的位置（x 或者 左子节点topLineX）（极其重要）
*/
private int leftBound() {
if (left == null) return x;
return left.topLineX();
}
/**
* x ~ 左边界之间的长度（包括左边界字符）
*
* @return
*/
private int leftBoundLength() {
return x - leftBound();
}
/**
* rightX ~ 右边界之间的长度（包括右边界字符）
*
* @return
*/
private int rightBoundLength() {
return rightBound() - rightX();
}
/**
* 左边界可以清空的长度
*
* @return
*/
private int leftBoundEmptyLength() {
return leftBoundLength() - 1 - TOP_LINE_SPACE;
}
/**
* 右边界可以清空的长度
*
* @return
*/
private int rightBoundEmptyLength() {
return rightBoundLength() - 1 - TOP_LINE_SPACE;
}
/**
* 让left和right基于this对称
*/
private void balance(Node left, Node right) {
if (left == null || right == null)
return;
// 【left的尾字符】与【this的首字符】之间的间距
int deltaLeft = x - left.rightX();
// 【this的尾字符】与【this的首字符】之间的间距
int deltaRight = right.x - rightX();
int delta = Math.max(deltaLeft, deltaRight);
int newRightX = rightX() + delta;
right.translateX(newRightX - right.x);
int newLeftX = x - delta - left.width;
left.translateX(newLeftX - left.x);
}
private int treeHeight(Node node) {
if (node == null) return 0;
if (node.treeHeight != 0) return node.treeHeight;
node.treeHeight = 1 + Math.max(
treeHeight(node.left), treeHeight(node.right));
return node.treeHeight;
}
/**
* 和右节点之间的最小层级距离
*/
private int minLevelSpaceToRight(Node right) {
int thisHeight = treeHeight(this);
int rightHeight = treeHeight(right);
int minSpace = Integer.MAX_VALUE;
for (int i = 0; i < thisHeight && i < rightHeight; i++) {
int space = right.levelInfo(i).leftX
- this.levelInfo(i).rightX;
minSpace = Math.min(minSpace, space);
}
return minSpace;
}
private LevelInfo levelInfo(int level) {
if (level < 0) return null;
int levelY = y + level;
if (level >= treeHeight(this)) return null;
List<Node> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(this);
// 层序遍历找出第level行的所有节点
while (!queue.isEmpty()) {
Node node = queue.poll();
if (levelY == node.y) {
list.add(node);
} else if (node.y > levelY) break;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
Node left = list.get(0);
Node right = list.get(list.size() - 1);
return new LevelInfo(left, right);
}
/**
* 尾字符的下一个位置
*/
public int rightX() {
return x + width;
}
public void translateX(int deltaX) {
if (deltaX == 0) return;
x += deltaX;
// 如果是LineNode
if (btNode == null) return;
if (left != null) {
left.translateX(deltaX);
}
if (right != null) {
right.translateX(deltaX);
}
}
}
private static class LevelInfo {
int leftX;
int rightX;
public LevelInfo(Node left, Node right) {
this.leftX = left.leftBound();
this.rightX = right.rightBound();
}
}
}
Strings
public class Strings {
public static String repeat(String string, int count) {
if (string == null) return null;
StringBuilder builder = new StringBuilder();
while (count-- > 0) {
builder.append(string);
}
return builder.toString();
}
public static String blank(int length) {
if (length < 0) return null;
if (length == 0) return "";
return String.format("%" + length + "s", "");
}
}
Asserts
public class Asserts {
public static void test(boolean v) {
if (v) return;
System.err.println(new RuntimeException().getStackTrace()[1]);
}
}
网友评论