- 浏览: 277177 次
- 性别:
- 来自: 长沙
文章分类
最新评论
-
CodeLove:
如果包含<,(,)...等特殊字符呢
Python变量名检测 -
zlxzlxzlxzlxzlx:
这不能算是任意进制之间的转换,只能算是 2、8、10、16 几 ...
java实现的任意进制转换 -
mychaoyue2011:
在本地执行了几遍,结果都是:s2开始休眠s1开始休眠s2休眠结 ...
Java线程学习笔记(四)线程join -
chxiaowu:
不错!
Java版的树 -
TenAclock:
这个例子 做不到“学生都交完” 考试结束,只能做到等到考试时间 ...
Java线程学习笔记(十一) DelayQueue的应用
用java实现的树,
先定义一个树的接口,暂时只有两个基本方法,
package com.woxiaoe.collection.tree; /** * 书接口 * @author 小e * * 2010-4-8 下午08:04:09 */ public interface Tree<T> extends Iterable<T> { /** * 深度 * @return */ public int depth(); /** * 叶子节点数 * @return */ public int leafCount(); }
接着定义一个树节点针对二叉树
package com.woxiaoe.collection.tree; /** * 树节点 * @author 小e * * 2010-4-8 下午08:06:04 */ public class Tnode<T>{ private Tnode<T> left; private Tnode<T> right; private T value; public Tnode(T value) { this.value = value; } public Tnode(T value, Tnode<T> left, Tnode<T> right){ this.value = value; this.left = left; this.right = right; } public Tnode<T> getLeft() { return left; } public void setLeft(Tnode<T> left) { this.left = left; } public Tnode<T> getRight() { return right; } public void setRight(Tnode<T> right) { this.right = right; } public T getValue() { return value; } public void setValue(T value) { this.value = value; } }
二叉树
package com.woxiaoe.collection.tree; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack; /** * 二叉树 * @author 小e * * 2010-4-8 下午08:04:53 */ public class BinaryTree<T> implements Tree<T> { private Tnode<T> root;//根结点 public BinaryTree() { root = null; } public BinaryTree(Tnode<T> root){ this.root = root; } public Tnode<T> getRoot() { return root; } public void setRoot(Tnode<T> root) { this.root = root; } @Override public int depth() { return depth(root); } @Override public int leafCount() { return leafCount(root); } private int depth(Tnode<T> node) { if(node == null){ return -1; } int leftHeight = depth(node.getLeft()); int rightHeight = depth(node.getRight()); return 1 + (leftHeight > rightHeight?leftHeight:rightHeight); } private int leafCount(Tnode<T> node){ if(node.getLeft() == null && node.getLeft() == null){ return 1; } return leafCount(node.getLeft()) + leafCount(node.getRight()); } @Override public Iterator<T> iterator() { return new InorderIterator(); } private class InorderIterator implements Iterator<T>{ private Stack<Tnode<T>> s ; Tnode<T> curr; public InorderIterator() { s = new Stack<Tnode<T>>(); curr = getFarLeft(root); } @Override public boolean hasNext() { return curr != null; } @Override public T next() { if(curr == null){ throw new NoSuchElementException("没有节点"); } T value = curr.getValue(); if(curr.getRight() != null){ curr = getFarLeft(curr.getRight()); }else if(!s.isEmpty()){ curr = s.pop(); }else{ curr = null; } return value; } @Override public void remove() { throw new RuntimeException("不支持该方法"); } /** * 得到右子树最远的有节点 * @return */ private Tnode<T> getFarLeft(Tnode<T> node){ if(node == null){ return null; } while(node.getLeft() != null){ s.push(node); node = node.getLeft(); } return node; } } }
以下为测试代码
package com.woxiaoe.collection.tree; import java.util.Iterator; import junit.framework.TestCase; public class TreeTest extends TestCase { BinaryTree tree = new BinaryTree(); @Override protected void setUp() throws Exception { Tnode<String> root = new Tnode<String>("root"); Tnode<String> a = new Tnode<String>("a"); Tnode<String> b = new Tnode<String>("b"); Tnode<String> c = new Tnode<String>("c"); Tnode<String> d = new Tnode<String>("d"); a.setLeft(b); a.setRight(c); root.setLeft(a); root.setRight(d); tree.setRoot(root); } public void testTree(){ System.out.println("tree height:" + tree.depth()); System.out.println("leaf node:" + tree.leafCount()); System.out.println("先序排列"); NLR(tree.getRoot()); System.out.println("中序排列"); LNR(tree.getRoot()); System.out.println("后序排列"); LRN(tree.getRoot()); System.out.println("测试遍历"); for (Iterator iterator = tree.iterator(); iterator.hasNext();) { String nodeValue = (String) iterator.next(); System.out.print(nodeValue + " "); } } /** * 先序排列 * @param node */ public void NLR(Tnode node){ if(node == null){ return; } visit(node); NLR(node.getLeft()); NLR(node.getRight()); } /** * 中序排列 * @param node */ public void LNR(Tnode node){ if(node == null){ return; } LNR(node.getLeft()); visit(node); LNR(node.getRight()); } /** * 后序排列 * @param node */ public void LRN(Tnode node){ if(node == null){ return; } LRN(node.getLeft()); LRN(node.getRight()); visit(node); } public void visit(Tnode node){ System.out.println(node.getValue()); } @SuppressWarnings("unchecked") public void testIterator(){ for (Iterator iterator = tree.iterator(); iterator.hasNext();) { String str = (String) iterator.next(); System.out.print(str + " "); } } }
Output
tree height:2
leaf node:3
先序排列
root
a
b
c
d
中序排列
b
a
c
root
d
后序排列
b
c
a
d
root
测试遍历
b a c root d b a c root d
发表评论
-
Consider the following code: What will be printed?
2010-09-24 20:30 944Consider the following code: Wh ... -
Java 基础复习笔记一
2010-06-04 02:03 1115这两天复习java的基础知识,把一些自己认为比较有用的点记录下 ... -
Java 转义字符
2010-06-03 21:21 980\n 回车(\u000a) \t 水平制表符(\u0009) ... -
生产消费者的模拟
2010-05-27 23:16 1637采用Java 多线程技术,设计实现一个符合生产者和消费者问题的 ... -
Java 控制台下显示文件结构
2010-05-27 00:10 3240题目: 编写一个Java ... -
Java得到类目录
2010-05-26 23:22 1162String path = MainTest.class.ge ... -
Java文件压缩
2010-05-23 21:54 1204package com.woxiaoe.study.io ... -
UDP传输图片的尝试
2010-05-22 18:05 9800UDP是不可靠的,发送的数据不一定会到达,且顺序不一定 ... -
【转载】Java String.Format() 方法及参数说明
2010-05-15 22:18 1306JDK1.5中,String类新增了一个很有用的静态方法S ... -
【转载】String.format函数使用方法介绍
2010-05-15 22:17 1170http://edu.codepub.com/2009/111 ... -
Java线程学习笔记(十一) DelayQueue的应用
2010-05-01 00:34 15597DelayQueue 是一个无界的BlockingQueue ... -
Java线程学习笔记(十)CountDownLatch 和CyclicBarrier
2010-04-30 21:04 2793CountDownLatch : 一个同步辅助类,在完成一组 ... -
Java线程学习笔记(九)生产者消费者问题
2010-04-29 22:27 1699用多线程来模拟生产者消费者问题。用到BlockingQueue ... -
Java线程学习笔记(八)线程之间的协作
2010-04-26 23:13 1762wait()与notifyAll() 调用sleep ... -
Java线程学习笔记(七)java中递增不是原子性
2010-04-24 23:00 2897以下为测试代码,通过一个自增函数得到最新的值,玩Set你存,看 ... -
Java线程学习笔记(六)在其他对象上同步
2010-04-24 22:47 1339package com.woxiaoe.study.threa ... -
Java线程学习笔记(五)资源共享问题
2010-04-24 21:04 1255IncreaseClient 中持有一个base,每次调用起i ... -
Java线程学习笔记(四)线程join
2010-04-24 20:06 1267《Java编程思想》的一个例子,如果某个线程在另一个线程t上调 ... -
基于java的图(四) 强连通组件
2010-04-22 21:06 1527有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一 ... -
基于java的图(三) 图的拓扑排序
2010-04-21 16:14 1860相关: 基于java的图的实现 基于java ...
相关推荐
java 实现系统目录树结构,显示文件夹下的文件。树结构
jsp树,java无限级树,java树。需要的下载了。ssh架构。
java多叉树的实现:节点集合生成多叉树,单个节点添加到多叉树,深度遍历,广度遍历
Java 菜单树的实现,可以很方便的移植到其他程序,方便使用,而且具有代表性.
java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;
关于Java的一个树结构,类似于本论坛左侧的样式,对初学者有一定的帮助
自己写的一个 用java代码复制树形结构数据的方法 很实用 希望对有需求的朋友给予帮助
用JAVa实现 树形目录的显示,有界面
java技能树
java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件java树形控件
Java 动态树 dhtmlxtree,可以隐藏和展开树,得到树根,树枝节点名称。
java 创建树菜单 java 创建树菜单 java 创建树菜单
圣诞树源码|Java圣诞树程序源码下载3种不同的设计用Java创建圣诞树源码程序。
该文档是用java代码编写的winfrom树形菜单。可以当模板用
java的动态树形菜单,和分页的实现,源码加数据库,可直接运行。
java 决策树Demo2
java实现的jsp动态树形菜单功能 简单的一个例子 代码全面 功能完善
Java实现的,将树形层级结构的数据转换成表格,通过打点的方式向表格中插入数据,支持行头表格、列头表格、交叉表格三种形式
java 表格树