解决方案 »

  1.   


    package FinalBinaryTree;import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Stack;public class BinaryTree<E extends Comparable<E>> extends AbstractTree<E> {
    private TreeNode<E> root = null;
    private int size = 0;

    @Override
    public boolean search(E e) {
    // TODO Auto-generated method stub
    TreeNode<E> current = root;
    while(current != null) {
    if(e.compareTo(current.item) < 0) {
    current = current.left;
    }
    else if(e.compareTo(current.item) > 0) {
    current = current.right;
    }
    else {
    return true;
    }
    }
    return false;
    } @Override
    public boolean delete(E e) {
    // TODO Auto-generated method stub
    TreeNode<E> current = root;
    while(current != null) {
    if(e.compareTo(current.item) < 0) {
    current = current.left;
    }
    else if(e.compareTo(current.item) > 0) {
    current = current.right;
    }
    else {
    break;
    }
    }
    if(current == null) {
    return false;
    }
    if(current.left == null) {
    if(current.parent == null) {
    root = current.right;
    current.right.parent = null;
    }
    else {
    if(e.compareTo(current.parent.item) < 0) {
    current.parent.left = current.right;
    if(current.right != null) {  //必须要这个判断,否则java.lang.NullPointerException
    current.right.parent = current.parent.left;
    }
    //help GC
    current.parent = null;
    current.right = null;
    current = null;
    }
    else {
    current.parent.right = current.right;
    if(current.right != null) {  //必须要这个判断,否则java.lang.NullPointerException
    current.right.parent = current.parent.right;
    }
    //help GC
    current.parent = null;
    current.right = null;
    current = null;
    }
    }
    }
    else {
    TreeNode<E> rm = current.left;
    while(rm.right != null) {
    rm = rm.right;
    }
    current.item = rm.item;
    if(rm.parent.right == rm) {
    rm.parent.right = rm.left;
    if(rm.left != null) {  //必须要这个判断,否则java.lang.NullPointerException
    rm.left.parent = rm.parent;
    }
    //help GC
    rm.item = null;
    rm.left = null;
    rm = null;
    }
    else {
    current.left = rm.left;
    if(rm.left != null) {  //必须要这个判断,否则java.lang.NullPointerException
    rm.left.parent = current;
    }
    //help GC
    rm.item = null;
    rm.left = null;
    rm = null;
    }
    }
    size--;
    return true;
    } @Override
    public boolean insert(E e) {
    // TODO Auto-generated method stub
    if(root == null) {
    root = new TreeNode<E>(e);
    size++;
    }
    else {
    TreeNode<E> parent = null;
    TreeNode<E> current = root;
    while(current != null) {
    if(e.compareTo(current.item) < 0) {
    parent = current;
    current = current.left;
    }
    else if(e.compareTo(current.item) > 0) {
    parent = current;
    current = current.right;
    }
    else {
    return false;
    }
    }
    if(e.compareTo(parent.item) < 0) {
    parent.left = new TreeNode<E>(e);
    parent.left.parent = parent;
    }
    else {
    parent.right = new TreeNode<E>(e);
    parent.right.parent = parent;
    }
    size++;
    }
    return true;
    } @Override
    public void inorder() {
    // TODO Auto-generated method stub
    inorder(root);
    }
    private void inorder(TreeNode<E> root) {
    if(root == null) {
    return ;
    }
    inorder(root.left);
    System.out.print(root.item + " ");
    inorder(root.right);
    } @Override
    public void nrinorder() {
    // TODO Auto-generated method stub
    Stack<TreeNode<E>> stack = new Stack<>();
    TreeNode<E> c = root;
    while(!stack.isEmpty() || c!=null) {
    while(c != null) {
    stack.push(c);
    c = c.left;
    }
    c = stack.pop();
    System.out.print(c.item + " ");
    c = c.right;
    }
    } @Override
    public void preorder() {
    // TODO Auto-generated method stub
    preorder(root);
    }
    private void preorder(TreeNode<E> root) {
    // TODO Auto-generated method stub
    if(root == null) {
    return;
    }
    System.out.print(root.item + " ");
    preorder(root.left);
    preorder(root.right);
    } @Override
    public void nrpreorder() {
    // TODO Auto-generated method stub
    TreeNode<E> current = root;
    Stack<TreeNode<E>> stack = new Stack<>();
    while(!stack.isEmpty() || current!=null) {
    if(current == null) {
    current = stack.pop();
    }
    System.out.print(current.item + " ");
    if(current.right != null) {
    stack.push(current.right);
    }
    current = current.left;
    }
    } @Override
    public void postorder() {
    // TODO Auto-generated method stub
    postorder(root);
    }
    private void postorder(TreeNode<E> root) {
    if(root == null) {
    return;
    }
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.item + " ");
    } @Override
    public void nrpostorder() {
    // TODO Auto-generated method stub
    TreeNode<E> last = null;
    TreeNode<E> current = root;
    Stack<TreeNode<E>> stack = new Stack<>();
    while(!stack.isEmpty() || current!=null) {
    while(current != null) {
    stack.push(current);
    current = current.left;
    }
    current = stack.peek();
    if(current.right==null || current.right==last) {
    System.out.print(current.item + " ");
    last = stack.pop();
    current = null;
    }
    else {
    current = current.right;
    }
    }
    } @Override
    public void breadthorder() {
    // TODO Auto-generated method stub
    LinkedList<TreeNode<E>> list = new LinkedList<>();
    TreeNode<E> current = root;
    list.add(current);
    int index = 0;
    while(index < getSize()) {
    for(int i=0;i<list.size();i++) {
    if(list.get(i) != null) {
    TreeNode<E> temp = list.get(i);
    System.out.print(temp.item + " ");
    list.add(i, temp.left);
    list.add(i+1,temp.right);
    list.remove(temp);
    index++;
    i++;
    }
    }
    }
    } @Override
    public int getSize() {
    // TODO Auto-generated method stub
    return size;
    }
    @Override
    public void clear() {
    // TODO Auto-generated method stub
    clearPreorder(root);
    size = 0;
    }
    private void clearPreorder(TreeNode<E> root) {
    root.parent = null;
    root.item = null;
    clearPreorder(root.left);
    clearPreorder(root.right);
    }

    //获得指定元素的路径,如果二叉树中不存在此元素,则返回null
    public ArrayList<TreeNode<E>> path(E e) {
    if(!search(e)) {
    return null;
    }
    ArrayList<TreeNode<E>> list = new ArrayList<>();
    TreeNode<E> current = root;
    while(current != null) {
    list.add(current);
    if(e.compareTo(current.item) < 0) {
    current = current.left;
    }
    else if(e.compareTo(current.item) > 0) {
    current = current.right;
    }
    else {
    break;
    }
    }
    return list;
    }

    //返回二叉树的高度
    public int height() {
    int len = 0;
    ArrayList<TreeNode<E>> list = new ArrayList<>();
    TreeNode<E> current = root;
    list.add(current);
    int index = 0;
    while(index < getSize()) {
    for(int i=0;i<list.size();i++) {
    if(list.get(i) != null) {
    TreeNode<E> temp = list.get(i);
    list.add(i, temp.left);
    list.add(i+1, temp.right);
    list.remove(temp);
    index++;
    i++;
    }
    }
    len++;
    }
    return len;
    }

    //如果此二叉树为完全二叉树,则返回true
    public boolean isFullBinaryTree() {
    ArrayList<TreeNode<E>> list = new ArrayList<>();
    TreeNode<E> current = root;
    list.add(current);
    int index = 0;
    while(index < getSize()) {
    for(int i=0;i<list.size();i++) {
    if(list.get(i) != null) {
    TreeNode<E> temp = list.get(i);
    list.add(i,temp.left);
    list.add(i+1,temp.right);
    list.remove(temp);
    index++;
    i++;
    }
    else {
    return false;
    }
    }
    }
    return true;
    }

    //返回根节点
    public TreeNode<E> getRoot() {
    return root;
    }

    //返回指定元素的父节点
    public TreeNode<E> getParent(E e) {
    TreeNode<E> current = root;
    while(current != null) {
    if(e.compareTo(current.item) < 0) {
    current = current.left;
    }
    else if(e.compareTo(current.item) > 0) {
    current = current.right;
    }
    else {
    return current.parent;
    }
    }
    return null;
    }

    //返回叶子节点的个数
    public int getNumberOfLeaves() {
    return getNumberOfLeaves(root);
    }
    private int getNumberOfLeaves(TreeNode<E> root) {
    if(root == null) {
    return 0;
    }
    else if(root.right==null && root.left==null) {
    return 1;
    }
    else {
    return getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
    }
    }

    //返回非叶子节点的个数
    public int getNumberOfNonLeaves() {
    return getSize()-getNumberOfLeaves();
    }

    static class TreeNode<E extends Comparable<E>> {
    protected E item;
    protected TreeNode<E> parent;
    protected TreeNode<E> left;
    protected TreeNode<E> right;

    public TreeNode(E item) {
    this.item = item;
    }
    }

    }
    这里包含了二叉树的一般方法,希望对楼主有所帮助
      

  2.   

    用于创建二叉树,运行,效果就出来了。/**
     * 
     * 报表数据存储用 yxy 20091020
     * 
     */
    public class ReportData extends LinkedHashMap {
    private static final Log logger = LogFactory.getLog(ReportData.class); public static void main1(String[] args) {
    ArrayList keys = new ArrayList();
    keys.add("a");
    keys.add("b");
    keys.add("c");
    keys.add("d"); String key = "1";
    String value = "2"; ReportData rData = new ReportData();
    rData.put(keys, key, value); logger.error("=====1=====>" + rData); keys.remove(3);
    logger.error("=====2=====>" + keys);
    rData.put(keys, "a", "4");
    rData.put(keys, "b", "5");
    logger.error("=====3=====>" + rData);
    } public static void main(String[] args) {
    ArrayList path = new ArrayList();
    ReportData rData = new ReportData();
    // 添加笔数
    path.clear();
    path.add("1001");
    path.add("1");
    path.add("0");
    path.add("1");
    rData.put(path, "COUNT", "888"); // 添加金额
    path.clear();
    path.add("1001");
    path.add("1");
    path.add("1");
    path.add("1");
    rData.put(path, "AMOUNT", "999"); // 添加机构ID
    path.clear();
    path.add("1001");
    rData.put(path, "DeptId", "999888"); // 添加机构名称
    path.clear();
    path.add("1001");
    rData.put(path, "DeptName", "上海分行"); // 添加笔数
    path.clear();
    path.add("1002");
    path.add("1");
    path.add("0");
    path.add("1");
    rData.put(path, "COUNT", "777"); // 添加金额
    path.clear();
    path.add("1002");
    path.add("1");
    path.add("1");
    path.add("1");
    rData.put(path, "AMOUNT", "666"); // 添加机构ID
    path.clear();
    path.add("1002");
    rData.put(path, "DeptId", "777666"); // 添加机构名称
    path.clear();
    path.add("1002");
    rData.put(path, "DeptName", "北京分行");
    logger.error("=====666=====>" + rData); logger.error("=====777=====>" + rData.entrySet());
    Set set = rData.entrySet();
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
    Map.Entry entry = (Map.Entry) iterator.next();
    logger.error("=====aaaaaaaaaaaaaaa=====>" + entry);
    logger.error("=====bbbbbbbbbbbbbbb=====>" + entry.getKey());
    logger.error("=====ccccccccccccccc=====>" + ((Map) entry.getValue()));
    logger.error("=====ddddddddddddddd=====>" + ((Map) entry.getValue()).get("DeptName"));
    }
    } public void put(ArrayList keys, Object key, Object value) { ReportData rData = this;
    for (int i = 0; i < keys.size(); i++) { if (rData.containsKey(keys.get(i))) {
    rData = (ReportData) rData.get(keys.get(i));
    } else {
    ReportData nData = new ReportData();
    rData.put(keys.get(i), nData);
    rData = nData;
    }
    }
    rData.put(key, value);
    }}