package com.merrytech;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinarySearchTree implements Comparable {

    private Node root;

    public BinarySearchTree() {
        this.root = null;
    }

    public int compareTo(Object n) {
        Node node = (Node)n;
        return this.root.compareTo(node);
    }

    public void insert(Comparable key) {
        Node newNode = new Node(key);
        if (this.root == null) {
            this.root = newNode;
        } else {
            BinarySearchTree.insertNode(this.root, newNode);
        }
    }

    private static void insertNode(Node node, Node newNode) {
        if (newNode.compareTo(node) < 0) {
            if (node.getLeft() == null) {
                node.setLeft(newNode);
            } else {
                BinarySearchTree.insertNode(node.getLeft(), newNode);
            }
        } else {
            if (node.getRight() == null) {
                node.setRight(newNode);
            } else {
                BinarySearchTree.insertNode(node.getRight(), newNode);
            }
        }
    }

    /**
     * 按层级遍历
     * @param fn Handler
     */
    public void levelTraverse(Handler fn) {
        Queue<Node> q = new LinkedList<>();
        q.add(this.root);
        while (!q.isEmpty()) {
            Node front = q.remove();
            fn.handle(front.getValue());
            if (front.getLeft() != null) {
                q.add(front.getLeft());
            }
            if (front.getRight() != null) {
                q.add(front.getRight());
            }
        }
    }

    public void preOrderTraverse(Handler fn) {
        BinarySearchTree.preOrderReCur(this.root, fn);
        System.out.println();
        BinarySearchTree.preOrderNotRecur(this.root, fn);
        System.out.println();
    }

    private static void preOrderReCur(Node node, Handler fn) {
        if (node != null) {
            fn.handle(node.getValue());
            BinarySearchTree.preOrderReCur(node.getLeft(), fn);
            BinarySearchTree.preOrderReCur(node.getRight(), fn);
        }
    }

    private static void preOrderNotRecur(Node head, Handler fn) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                fn.handle(head.getValue());
                if (head.getRight() != null) {
                    stack.push(head.getRight());
                }
                if (head.getLeft() != null) {
                    stack.push(head.getLeft());
                }
            }
        }
    }

    public void inOrderTraverse(Handler fn) {
        // BinarySearchTree.inOrderRecur(this.root, fn);
        BinarySearchTree.inOrderNotRecur(this.root, fn);
        System.out.println();
    }

    /**
     * 中序遍历
     * @param node Node
     * @param fn Handler
     */
    private static void inOrderRecur(Node node, Handler fn) {
        if (node != null) {
            BinarySearchTree.inOrderRecur(node.getLeft(), fn);
            fn.handle(node.getValue());
            BinarySearchTree.inOrderRecur(node.getRight(), fn);
        }
    }

    private static void inOrderNotRecur(Node head, Handler fn) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.getLeft();
                } else {
                    head = stack.pop();
                    fn.handle(head.getValue());
                    head = head.getRight();
                }
            }
        }
    }

    public void posOrderTraverse(Handler fn) {
        // BinarySearchTree.posOrderRecur(this.root, fn);
        BinarySearchTree.posOrderNotRecur(this.root, fn);
    }

    private static void posOrderRecur(Node node, Handler fn) {
        if (node != null) {
            BinarySearchTree.posOrderRecur(node.getLeft(), fn);
            BinarySearchTree.posOrderRecur(node.getRight(), fn);
            fn.handle(node.getValue());
        }
    }

    private static void posOrderNotRecur(Node head, Handler fn) {
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.getLeft() != null) {
                    s1.push(head.getLeft());
                }
                if (head.getRight() != null) {
                    s1.push(head.getRight());
                }
            }
            while(!s2.isEmpty()) {
                fn.handle(s2.pop().getValue());
            }
        }
    }
}

Handler.java? 遍历节点 操作函数接口

package com.merrytech;

public class Handler {
    public void handle(Object o) {
        System.out.print(o + " ");
    }
}

package com.merrytech;

public class Main {

    public static void main(String[] args) {
        String s = "532148769";
        BinarySearchTree tree = new BinarySearchTree();
        for (int i = 0; i < s.length(); i++) {
            tree.insert(s.charAt(i));
        }
        Handler h = new Handler();
        tree.inOrderTraverse(h);
        tree.levelTraverse(h); // 538247916
        // tree.preOrderTraverse(h);
        // tree.posOrderTraverse(h);
    }
}