how2j.cn

本视频是解读性视频,所以希望您已经看过了本知识点的内容,并且编写了相应的代码之后,带着疑问来观看,这样收获才多。 不建议一开始就观看视频



29分53秒
本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)



示例 1 : 二叉树概念   
示例 2 : 二叉树排序-插入数据   
示例 3 : 二叉树排序-遍历   
示例 4 : 练习-英雄二叉树   
示例 5 : 答案-英雄二叉树   
示例 6 : 练习-比较冒泡法,选择法以及二叉树排序的性能区别   
示例 7 : 答案-比较冒泡法,选择法以及二叉树排序的性能区别   

示例 1 :

二叉树概念

二叉树由各种节点组成
二叉树特点:
每个节点都可以有左子节点,右子节点
每一个节点都有一个
二叉树概念
package collection; public class Node { // 左子节点 public Node leftNode; // 右子节点 public Node rightNode; // 值 public Object value; }
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的左节点。
...
...
9. 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()); } }
示例 4 :

练习-英雄二叉树

Or  姿势不对,事倍功半! 点击查看做练习的正确姿势
根据上面的学习和理解,设计一个Hero二叉树,HeroNode.
可以向这个英雄二叉树插入不同的Hero对象,并且按照Hero的血量倒排序

随机生成10个Hero对象,每个Hero对象都有不同的血量值,插入这个HeroNode后,把排序结果打印出来。
练习-英雄二叉树
示例 5 :

答案-英雄二叉树

在查看答案前,尽量先自己完成,碰到问题再来查看答案,收获会更多
本视频是解读性视频,所以希望您已经看过了本答案的内容,带着疑问来观看,这样收获才多。 不建议一开始就观看视频

3分17秒 本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)


为了方便打印效果,重写了Hero的toString()方法
答案-英雄二叉树
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); } }
package charactor; public class Hero { public String name; public float hp; public int damage; public Hero() { } public Hero(String name) { this.name = name; } public String toString() { return String.format("[name:%s hp:%.0f]%n", name,hp); } }
示例 6 :

练习-比较冒泡法,选择法以及二叉树排序的性能区别

Or  姿势不对,事倍功半! 点击查看做练习的正确姿势
创建4万个随机数,然后用分别用冒泡法选择法二叉树3种排序算法进行排序,比较哪种更快
示例 7 :

答案-比较冒泡法,选择法以及二叉树排序的性能区别

在查看答案前,尽量先自己完成,碰到问题再来查看答案,收获会更多
本视频是解读性视频,所以希望您已经看过了本答案的内容,带着疑问来观看,这样收获才多。 不建议一开始就观看视频

9分34秒 本视频采用html5方式播放,如无法正常播放,请将浏览器升级至最新版本,推荐火狐,chrome,360浏览器 如果装有迅雷,播放视频呈现直接下载状态,请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)


答案-比较冒泡法,选择法以及二叉树排序的性能区别
package collection; import java.util.Arrays; import java.util.List; public class SortCompare { public static void main(String[] args) { //初始化随机数 int total = 40000; System.out.println("初始化一个长度是"+total+"的随机数字的数组"); int[] originalNumbers = new int[total]; for (int i = 0; i < originalNumbers.length; i++) { originalNumbers[i] = (int)(Math.random()*total); } System.out.println("初始化完毕"); System.out.println("接下来分别用3种算法进行排序"); //从初始化了的随机数组复制过来,以保证,每一种排序算法的目标数组,都是一样的 int[] use4sort; use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length); int[] sortedNumbersBySelection= performance(new SelectionSort(use4sort),"选择法"); use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length); int[] sortedNumbersByBubbling=performance(new BubblingSort(use4sort),"冒泡法"); use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length); int[] sortedNumbersByTree=performance(new TreeSort(use4sort),"二叉树"); System.out.println("查看排序结果,是否是不同的数组对象"); System.out.println(sortedNumbersBySelection); System.out.println(sortedNumbersByBubbling); System.out.println(sortedNumbersByTree); System.out.println("查看排序结果,内容是否相同"); System.out.println("比较 选择法 和 冒泡法 排序结果:"); System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByBubbling)); System.out.println("比较 选择法 和 二叉树 排序结果:"); System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByTree)); } interface Sort{ void sort(); int[] values(); } static class SelectionSort implements Sort{ int numbers[]; SelectionSort(int [] numbers){ this.numbers = numbers; } @Override public void sort() { for (int j = 0; j < numbers.length-1; j++) { for (int i = j+1; i < numbers.length; i++) { if(numbers[i]<numbers[j]){ int temp = numbers[j]; numbers[j] = numbers[i]; numbers[i] = temp; } } } } @Override public int[] values() { // TODO Auto-generated method stub return numbers; } } static class BubblingSort implements Sort{ int numbers[]; BubblingSort(int [] numbers){ this.numbers = numbers; } @Override public void sort() { for (int j = 0; j < numbers.length; j++) { for (int i = 0; i < numbers.length-j-1; i++) { if(numbers[i]>numbers[i+1]){ int temp = numbers[i]; numbers[i] = numbers[i+1]; numbers[i+1] = temp; } } } } @Override public int[] values() { // TODO Auto-generated method stub return numbers; } } static class TreeSort implements Sort{ int numbers[]; Node n; TreeSort(int [] numbers){ n =new Node(); this.numbers = numbers; } @Override public void sort() { for (int i : numbers) { n.add(i); } } @Override public int[] values() { List<Object> list = n.values(); int sortedNumbers[] = new int[list.size()]; for (int i = 0; i < sortedNumbers.length; i++) { sortedNumbers[i] = Integer.parseInt(list.get(i).toString()); } return sortedNumbers; } } private static int[] performance(Sort algorithm, String type) { long start = System.currentTimeMillis(); algorithm.sort(); int sortedNumbers[] = algorithm.values(); long end = System.currentTimeMillis(); System.out.printf("%s排序,一共耗时 %d 毫秒%n",type,end-start); return sortedNumbers; } }


HOW2J公众号,关注后实时获知布最新的教程和优惠活动,谢谢。


问答区域    
2018-07-07 StackOverflowError
一只勤劳的小码农



我就用了二叉树的方式 报了这个错误
public class NumNode {
	//左子节点
	public NumNode leftNode;
	//右子节点
	public NumNode rightNode;
	//值
	public Integer value;
	
	//插入数据
	public void add(Integer v) {
		if(value == null) {
			value = v;
		}
		if(value > v) { 
			if(leftNode == null) {
				leftNode = new NumNode();				
			}
			leftNode.add(v);
		}else {
			if(rightNode == null) {
				rightNode = new NumNode();
			}
			rightNode.add(v);
		}
	}
	
	//遍历
	public List<Integer> getValues(){
		List<Integer> values = new ArrayList<Integer>();
		if(leftNode != null) {
			values.addAll(leftNode.getValues());
		}
		
		values.add(value);
		
		if(rightNode != null) {
			values.addAll(rightNode.getValues());
		}
		
		return values;
	}
	
	public static void main(String[] args) {
		int[] random = new int[5000];
		NumNode num = new NumNode();
		for(int i =0; i < random.length; i++) {
			random[i] = (int) (Math.random() * 40000);
		}
		long start = System.currentTimeMillis();
		for(int i : random) {
			num.add(i);
		}
		long end = System.currentTimeMillis();
		long ss = end - start;
		System.out.println("排序完成用了:"+ss+"毫秒");
	}
}
Exception in thread "main" java.lang.StackOverflowError






答案 或者 代码至少填写一项, 如果是自己有问题,请重新提问,否则站长有可能看不到





2018-07-02 交作业,仅供参考
hzp



比较冒泡法,选择法以及二叉树排序的性能区别
package 二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

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)value <= (Integer)v) {
				if(null == rightNode) {
					rightNode = new Node();
				}
				rightNode.add(v);
			}else {
				if(null == leftNode) {
					leftNode = new Node();
				}
				leftNode.add(v);
			}
		}
	}
	
	
	
	//中序遍历
	public List<Object> values(){
		List<Object> values = new ArrayList<Object>();
		
		if(null != leftNode) {
			values.addAll(leftNode.values());
		}
		
		values.add(value);
		
		if(null != rightNode) {
			values.addAll(rightNode.values());
		}
		return values;
	}

	//冒泡排序
	public static void bubbleSort(int[] value) {
		for(int i = 0; i < value.length; i++) {
			for(int j = i + 1;j < value.length - i; i++) {
				if(value[i] > value[j]) {
					int temp = value[i];
					value[i] = value[j];
					value[j] = temp;
				}
			}
		}
	}
	
	//选择排序
	public static void selectsort(int[] value) {
		for(int i = 0; i < value.length; i++) {
			int minIndex = i;
			for(int j = i+1; j < value.length; j++) {
				if(value[j] < value[minIndex]) {
					minIndex = j;
				}
			}
			int temp = value[minIndex];
			value[minIndex] = value[i];
			value[i] = temp;
		}
	}
	
	
	public static void main(String[] args) {
		Random rand = new Random();
		int[] randoms = new int[40000];
		Node roots = new Node();
		for(int i = 0; i < 40000; i++) {
			randoms[i] = rand.nextInt(40000)+1;
			roots.add(randoms[i]);
//			System.out.print(randoms[i]+" ");
		}
//		System.out.println();
//		System.out.println(roots.values());
		int[] copy1 = Arrays.copyOf(randoms, randoms.length);
		int[] copy2 = Arrays.copyOf(randoms, randoms.length);
		
//		for(int i = 0; i < copy1.length; i++) {
//			System.out.print(copy1[i]+" ");
//		}
//		System.out.println();
		
		long startTime = System.currentTimeMillis();
		roots.values();
		long endTime = System.currentTimeMillis();
		System.out.println("二叉树排序耗时:"+(endTime - startTime)+"毫秒");
		startTime = System.currentTimeMillis();
		bubbleSort(copy1);
		endTime = System.currentTimeMillis();
		System.out.println("冒泡排序耗时:"+(endTime - startTime)+"毫秒");
		startTime = System.currentTimeMillis();
		selectsort(copy2);
		endTime = System.currentTimeMillis();
		System.out.println("选择排序耗时:"+(endTime - startTime)+"毫秒");
	}
	

}

							






答案 或者 代码至少填写一项, 如果是自己有问题,请重新提问,否则站长有可能看不到





2018-07-02 交作业,仅供参考
2018-06-01 站长大大,答案就不能单条购买吗,非要来个全部
2018-05-31 帮我看下为什么我的二叉树排序速度最慢, 数组一多的时候报错
2018-05-31 为何我的二叉树最慢?
2018-05-04 【交作业】比较冒泡法,选择法以及二叉树排序的性能区别
2018-05-03 我使用idea直接复制教程中二叉树插入那段的代码,为何add报错?
2018-04-28 二叉树需要的时间和其他两个差不多
2018-04-19 谁能解决这个问题?!
2018-04-16 leftNode和rightNode是Node类型的引用,不理解为什么可以作为rootNode的属性?
2018-04-11 values 跟values() 真的弄蒙圈了 建议命名区分下吧
2018-03-12 二叉树,恐怖如斯
2017-12-28 我这里怎么是二叉树的排序性能远低于其他两个啊
2017-12-08 好不容易写出了快排的递归形式,给大家参考下
2017-11-28 示例7:StackOverflowError
2017-11-28 实例7:StackOverflowError
2017-11-28 泛型Node类,供参考
2017-11-13 Node中的add方法内,为什么可以调用自身(add方法)?
2017-10-28 方法的名字问题
2017-10-28 字符格式化问题
2017-10-15 Node是哪个包下面的?
2017-09-20 二叉树插入数据,0的位置
2017-09-20 站长能加个深度优先遍历和广度优先遍历吗
2017-09-16 public Object value;
2017-09-13 疑惑
2017-09-12 怎样将list中的Object的属性顺利变为String
2017-08-24 这里的遍历算法我是真的服气
2017-08-24 add() 与 addAll() 区别?
2017-07-29 二叉树排序是怎么回到上一层的
2017-07-27 有一点疑问就是比如public Node rightNode,在null的情况下会一直new创建新的,然后新的对象的引用都是同一个名称,就是对于具体的执行过程不是很了解
2017-07-08 最后一题按着答案来为什么报错Node cannot be resolved to a type
2017-07-07 递归真是有点吃力
2017-06-19 不知道怎么输出值
2017-06-14 二叉树排序性能
2017-05-26 hs是ArrayList类型对象,为什么它可以调用Hero的toString()方法啦?
2017-01-25 在add方法中判断欲插入值位置时为什么判断条件是“(Integer) v -((Integer)value) <= 0”
2016-05-15 addAll是一个什么方法?




提问之前请登陆
关于 JAVA 中级-集合框架-二叉树 的提问

尽量提供截图代码异常信息,有助于分析和解决问题。 也可进本站QQ群交流: 620943819
提问尽量提供完整的代码,环境描述,越是有利于问题的重现,您的问题越能更快得到解答。
对教程中代码有疑问,请提供是哪个步骤,哪一行有疑问,这样便于快速定位问题,提高问题得到解答的速度
在已经存在的几千个提问里,有相当大的比例,是因为使用了和站长不同版本的开发环境导致的,比如 jdk, eclpise, idea, mysql,tomcat 等等软件的版本不一致。
请使用和站长一样的版本,可以节约自己大量的学习时间。 站长把教学中用的软件版本整理了,都统一放在了这里, 方便大家下载: http://how2j.cn/k/helloworld/helloworld-version/1718.html

上传截图