Java自学-集合框架 二叉树
程序员文章站
2022-06-20 08:52:58
Java集合框架 二叉树 示例 1 : 二叉树概念 二叉树由各种 节点 组成 二叉树特点: 每个节点都可以有 左 子节点, 右 子节点 每一个节点都有一个 值 package collection; public class Node { // 左子节点 public Node leftNode; ......
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
排序的第一个步骤是把数据插入到该二叉树中
插入基本逻辑是,小、相同的放左边,大的放右边
- 67 放在根节点
- 7 比 67小,放在67的左节点
- 30 比67 小,找到67的左节点7,30比7大,就放在7的右节点
- 73 比67大, 放在67的右节点
- 10 比 67小,找到67的左节点7,10比7大,找到7的右节点30,10比30小,放在30的左节点。
...
... -
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); } }
上一篇: 快速搭建ssh项目
下一篇: Maven入门【小白千万别点进】