二叉树

java 代码

这是我写的二叉树和四种遍历方式，请指教。
p.s. 编号是按照满进行编号(location)。



public class BinaryTree {
    private static final int ROOT_LOCATION = 1;

    private BinaryNode root;

    public BinaryTree() {
    }

    public BinaryNode getRoot() {
        return root;
    }

    public void setRoot(BinaryNode root) {
        this.root = root;
        this.root.setLocation(ROOT_LOCATION);
        updateLocation(ROOT_LOCATION, root);
    }

    public BinaryTree(BinaryNode root) {
        this();
        setRoot(root);
    }

    public BinaryTree(BinaryNode root, int location) {
        this();
        this.root = root;
        this.root.setLocation(location);
        updateLocation(location, root);
    }

    public boolean add(BinaryTree aTree, int location) {
        if (this == aTree) {
            return false;
        }
        BinaryNode aRoot = aTree.getRoot();
        return add(aRoot, location);
    }

    public boolean add(BinaryNode node, int location) {
        if (location == ROOT_LOCATION) {
            root = getRoot();
            if (root == null) {
                setRoot(node);
                return true;
            }
            return false;
        }
        BinaryNode parent = getParent(location);
        if (parent == null) {
            return false;
        }
        if (location % 2 == 0) {
            BinaryNode curNode = parent.getL_Child();
            if (curNode != null) {
                return false;
            }
            parent.setL_Child(node);
        } else {
            BinaryNode curNode = parent.getR_Child();
            if (curNode != null) {
                return false;
            }
            parent.setR_Child(node);
        }
        updateLocation(location, node);
        return true;
    }

    public BinaryNode getParent(int location) {
        int parentLoc = location / 2;
        BinaryNode parent = getNode(parentLoc);
        return parent;
    }

    private BinaryNode getNode(int location) {
        GetNodeHandler handler = new GetNodeHandler(location);
        TraverseUtil.traverseByPre(this, handler);
        return handler.getNode();
    }

    public void delete(int location) {
        BinaryNode parent = getParent(location);
        if (parent == null) {
            return;
        }
        if (location % 2 == 0) {
            parent.setL_Child(null);
        } else {
            parent.setR_Child(null);
        }
    }

    public boolean update(Object value, int location) {
        if (value instanceof BinaryNode) {
            return false;
        }
        BinaryNode node = getNode(location);
        if (node == null) {
            return false;
        }
        node.setData(value);
        return true;
    }

    private void updateLocation(int rootLocation, BinaryNode aRoot) {
        UpdateLocationHandler handler = new UpdateLocationHandler(rootLocation,
                aRoot);
        TraverseUtil.traverseByPre(aRoot, handler);
    }

    public int getTreeDepth() {
        MaxLocationHandler handler = new MaxLocationHandler(getRoot());
        TraverseUtil.traverseByPre(this, handler);
        int depth = getDepth(handler.getLocation());
        return depth;
    }

    public int size() {
        SizeHandler handler = new SizeHandler(getRoot());
        TraverseUtil.traverseByPre(this, handler);
        return handler.getSize();
    }

    private int getDepth(int max) {
        ++max;
        int depth = 1;
        while (max > 1) {
            max /= 2;
            ++depth;
        }
        return depth;
    }

    public Object getData(int loc) {
        BinaryNode node = getNode(loc);
        if (node == null) {
            return null;
        }
        return node.getData();
    }

    private class GetNodeHandler extends AbstractNodeHandler {

        public GetNodeHandler(final int location) {
            super(location);
        }

        public boolean handle(BinaryNode node) {
            if (node == null) {
                return false;
            }
            if (node.getLocation() == getLocation()) {
                setNode(node);
                return true;
            }
            return false;
        }
    }

    private class UpdateLocationHandler extends AbstractNodeHandler {

        public UpdateLocationHandler(int location, BinaryNode root) {
            super(location);
            root.setLocation(location);
        }

        public boolean handle(BinaryNode node) {
            if (node == null) {
                return false;
            }

            if (node.isExistL_Child()) {
                BinaryNode l = node.getL_Child();
                l.setLocation(node.getLocation() * 2);
            }

            if (node.isExistR_Child()) {
                BinaryNode r = node.getR_Child();
                r.setLocation(node.getLocation() * 2 + 1);
            }
            return false;
        }
    }

    private class MaxLocationHandler extends AbstractNodeHandler {

        public MaxLocationHandler(BinaryNode root) {
            super(root.getLocation());
        }

        public boolean handle(BinaryNode node) {
            if (node == null) {
                return false;
            }
            int curLoc = node.getLocation();
            if (curLoc > getLocation()) {
                setLocation(curLoc);
            }
            return false;
        }
    }

    private class SizeHandler extends AbstractNodeHandler {
        private int size;

        public int getSize() {
            return size;
        }

        public SizeHandler(BinaryNode root) {
            super(root.getLocation());
        }

        public boolean handle(BinaryNode node) {
            if (node == null) {
                return false;
            }
            size++;
            return false;
        }
    }
}

public class BinaryNode {
    public final static int SINGLENODE = 0;

    private Object data;

    private int location;

    private BinaryNode l_Child;

    private BinaryNode r_Child;

    public BinaryNode() {
        super();
        this.location = SINGLENODE;
    }

    public BinaryNode(Object data) {
        this();
        this.data = data;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public BinaryNode getL_Child() {
        return l_Child;
    }

    public void setL_Child(BinaryNode child) {
        l_Child = child;
    }

    public BinaryNode getR_Child() {
        return r_Child;
    }

    public void setR_Child(BinaryNode child) {
        r_Child = child;
    }

    public boolean isExistL_Child() {
        if (getL_Child() == null) {
            return false;
        }
        return true;
    }

    public boolean isExistR_Child() {
        if (getR_Child() == null) {
            return false;
        }
        return true;
    }

    public int getLocation() {
        return location;
    }

    public void setLocation(int location) {
        this.location = location;
    }
}

public interface IHandler {
    /**
     * return true indicate stopping traversing, otherwise continuing.
     */
    boolean handle(BinaryNode node);
}

public abstract class AbstractNodeHandler implements IHandler {
    private BinaryNode node;

    private int location;

    public AbstractNodeHandler(final int location) {
        super();
        this.location = location;
    }

    public abstract boolean handle(BinaryNode node);

    public BinaryNode getNode() {
        return node;
    }

    public void setNode(BinaryNode node) {
        this.node = node;
    }

    public int getLocation() {
        return location;
    }

    public void setLocation(int location) {
        this.location = location;
    }

}

import java.util.LinkedList;

public class TraverseUtil {

    private TraverseUtil() {
    }

    public static void traverseByPre(BinaryTree tree, IHandler handler) {
        BinaryNode root = tree.getRoot();
        if (root == null) {
            return;
        }
        traverseByPre(root, handler);
    }

    public static void traverseByPre(BinaryNode node, IHandler handler) {
        boolean isStop = handler.handle(node);
        if (isStop) {
            return;
        }
        if (node.isExistL_Child()) {
            BinaryNode child = node.getL_Child();
            traverseByPre(child, handler);
        }
        if (node.isExistR_Child()) {
            BinaryNode child = node.getR_Child();
            traverseByPre(child, handler);
        }
    }

    public static void traverseByInOrder(BinaryTree tree, IHandler handler) {
        BinaryNode root = tree.getRoot();
        if (root == null) {
            return;
        }
        traverseByInOrder(root, handler);
    }

    public static void traverseByInOrder(BinaryNode node, IHandler handler) {
        if (node.isExistL_Child()) {
            BinaryNode child = node.getL_Child();
            traverseByInOrder(child, handler);
        }

        boolean isStop = handler.handle(node);
        if (isStop) {
            return;
        }

        if (node.isExistR_Child()) {
            BinaryNode child = node.getR_Child();
            traverseByInOrder(child, handler);
        }
    }

    public static void traverseByPost(BinaryTree tree, IHandler handler) {
        BinaryNode root = tree.getRoot();
        if (root == null) {
            return;
        }
        traverseByPost(root, handler);
    }

    public static void traverseByPost(BinaryNode node, IHandler handler) {
        if (node.isExistL_Child()) {
            BinaryNode child = node.getL_Child();
            traverseByPost(child, handler);
        }

        if (node.isExistR_Child()) {
            BinaryNode child = node.getR_Child();
            traverseByPost(child, handler);
        }

        boolean isStop = handler.handle(node);
        if (isStop) {
            return;
        }
    }

    public static void traverseByLevel(BinaryTree tree, IHandler handler) {
        BinaryNode node = tree.getRoot();
        LinkedList<BinaryNode> level = new LinkedList<BinaryNode>();
        level.addLast(node);
        traverseByLevel(handler, level);
    }

    private static void traverseByLevel(IHandler handler,
            LinkedList<BinaryNode> level) {
        if (level.isEmpty()) {
            return;
        }
        BinaryNode node = level.removeFirst();
        boolean isStop = handler.handle(node);
        if (isStop) {
            return;
        }
        if (node.isExistL_Child()) {
            level.addLast(node.getL_Child());
        }
        if (node.isExistR_Child()) {
            level.addLast(node.getR_Child());
        }
        traverseByLevel(handler, level);
    }
}