Java自学-集合框架 二叉树

2019-11-29 08:43:28来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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);
 
    }
}

原文链接:https://www.cnblogs.com/jeddzd/p/11955731.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:toUpperCase(),toLowerCase()将字符串中的英文转换为全大写或全

下一篇:Docker学习(一)