Java自学-集合框架 二叉树

java集合框架 二叉树

示例 1 : 二叉树概念

二叉树由各种节点组成
二叉树特点：
每个节点都可以有左子节点，右子节点
每一个节点都有一个值

package collection;
 
public class node {
    // 左子节点
    public node leftnode;
    // 右子节点
    public node rightnode;
    // 值
    public object value;
}

示例 2 : 二叉树排序-插入数据

假设通过二叉树对如下10个随机数进行排序
67,7,30,73,10,0,78,81,10,74
排序的第一个步骤是把数据插入到该二叉树中
插入基本逻辑是，小、相同的放左边，大的放右边

1. 67 放在根节点
2. 7 比 67小，放在67的左节点
3. 30 比67 小，找到67的左节点7，30比7大，就放在7的右节点
4. 73 比67大， 放在67的右节点
5. 10 比 67小，找到67的左节点7，10比7大，找到7的右节点30，10比30小，放在30的左节点。
   ...
   ...

6. 10比67小，找到67的左节点7，10比7大，找到7的右节点30，10比30小，找到30的左节点10，10和10一样大，放在左边
   

    package collection;
   
    public class node {
        // 左子节点
        public node leftnode;
        // 右子节点
        public node rightnode;
   
        // 值
        public object value;
   
        // 插入 数据
        public void add(object v) {
            // 如果当前节点没有值，就把数据放在当前节点上
            if (null == value)
                value = v;
   
        // 如果当前节点有值，就进行判断，新增的值与当前值的大小关系
        else {
            // 新增的值，比当前值小或者相同
   
            if ((integer) v -((integer)value) <= 0) {
                if (null == leftnode)
                    leftnode = new node();
                leftnode.add(v);
            }
            // 新增的值，比当前值大
            else {
                if (null == rightnode)
                    rightnode = new node();
                rightnode.add(v);
            }
   
        }
   
    }
   
    public static void main(string[] args) {
   
        int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };
   
        node roots = new node();
        for (int number : randoms) {
            roots.add(number);
        }
   
     }
    }

示例 3 : 二叉树排序-遍历

通过上一个步骤的插入行为，实际上，数据就已经排好序了。 接下来要做的是看，把这些已经排好序的数据，遍历成我们常用的list或者数组的形式

二叉树的遍历分左序，中序，右序
左序即： 中间的数遍历后放在左边
中序即： 中间的数遍历后放在中间
右序即： 中间的数遍历后放在右边
如图所见，我们希望遍历后的结果是从小到大的，所以应该采用中序遍历

package collection;
 
import java.util.arraylist;
import java.util.list;
 
public class node {
    // 左子节点
    public node leftnode;
    // 右子节点
    public node rightnode;
  
    // 值
    public object value;
  
    // 插入数据
    public void add(object v) {
        // 如果当前节点没有值，就把数据放在当前节点上
        if (null == value)
            value = v;
  
        // 如果当前节点有值，就进行判断，新增的值与当前值的大小关系
        else {
            // 新增的值，比当前值小或者相同
             
            if ((integer) v -((integer)value) <= 0) {
                if (null == leftnode)
                    leftnode = new node();
                leftnode.add(v);
            }
            // 新增的值，比当前值大
            else {
                if (null == rightnode)
                    rightnode = new node();
                rightnode.add(v);
            }
  
        }
  
    }
  
 // 中序遍历所有的节点
    public list<object> values() {
        list<object> values = new arraylist<>();
  
        // 左节点的遍历结果
        if (null != leftnode)
            values.addall(leftnode.values());
  
        // 当前节点
        values.add(value);
  
        // 右节点的遍历结果
        if (null != rightnode)
  
            values.addall(rightnode.values());
  
        return values;
    }
  
    public static void main(string[] args) {
  
        int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };
  
        node roots = new node();
        for (int number : randoms) {
            roots.add(number);
        }
  
        system.out.println(roots.values());
  
    }
}

练习：

根据上面的学习和理解，设计一个hero二叉树，heronode.
可以向这个英雄二叉树插入不同的hero对象，并且按照hero的血量倒排序。

随机生成10个hero对象，每个hero对象都有不同的血量值，插入这个heronode后，把排序结果打印出来。

package collection;
 
import java.util.arraylist;
import java.util.list;
 
import charactor.hero;
 
public class heronode {
 
    public heronode lefthero;
 
    public heronode righthero;
 
    // 声明为hero类型
    public hero value;
 
    public void add(hero v) {
 
        if (null == value)
            value = v;
 
        else {
 
            // 如果新英雄血量，比本节点大，就放在左边
            if (v.hp > value.hp) {
                if (null == lefthero)
                    lefthero = new heronode();
                lefthero.add(v);
            }
 
            else {
                if (null == righthero)
                    righthero = new heronode();
                righthero.add(v);
            }
 
        }
 
    }
 
    public list<object> values() {
        list<object> values = new arraylist<>();
 
        if (null != lefthero)
            values.addall(lefthero.values());
 
        values.add(value);
 
        if (null != righthero)
 
            values.addall(righthero.values());
 
        return values;
    }
 
    public static void main(string[] args) {
 
        list<hero> hs = new arraylist<>();
        for (int i = 0; i < 10; i++) {
            hero h = new hero();
            h.name = "hero " + i;
            h.hp = (float) (math.random() * 900 + 100); // 100-1000的随机血量
            hs.add(h);
        }
        system.out.println("初始化10个hero");
        system.out.println(hs);
 
        heronode herotree = new heronode();
        for (hero hero : hs) {
            herotree.add(hero);
        }
        system.out.println("根据血量倒排序后的hero");
        list<object> treesortedheros = herotree.values();
        system.out.println(treesortedheros);
 
    }
}