- 浏览: 3435604 次
- 性别:
- 来自: China
文章分类
- 全部博客 (536)
- ajax (1)
- Algorithm (14)
- Android (40)
- CSS/HTML... (2)
- defy (3)
- DesignPattern (2)
- dorado (0)
- Drools (6)
- English/日本語 (7)
- Flex (2)
- Framework (0)
- Google (3)
- hibernate (13)
- homework (3)
- HTML5 (0)
- IDE (29)
- java (45)
- javaee (7)
- Javascript (14)
- java组件 (5)
- jQuery (4)
- jsp (8)
- jsf (2)
- Linux (2)
- lucene (0)
- mysql (6)
- news (3)
- Oracle (8)
- other (4)
- PHP (5)
- Python (0)
- Software Engineering (3)
- spring (7)
- struts1.x (14)
- struts2.x (14)
- strolling in cloud (1)
- subject:javaEnhance (20)
- Tomcat (7)
- validator (3)
- 学习·方法·心得 (8)
- .NET (2)
- vba (6)
- groovy (5)
- grails (2)
- SWT (0)
- big data (1)
- perl (1)
- objective-c (50)
- product (1)
- mac (7)
- ios (188)
- ios-phone (2)
- ios-system (15)
- ios-network (5)
- ios-file (4)
- ios-db (1)
- ios-media (3)
- ios-ui (27)
- ios-openSource (6)
- ios-animation (5)
- ios-drawing (7)
- c (2)
- ios-app (2)
- ios-course (15)
- ios-runtime (14)
- ios-code (8)
- ios-thread (8)
- ios-LBS (2)
- ios-issue (1)
- ios-design (2)
- Jailbreak (2)
- cocos2d (0)
- swift (16)
- ios-framework (4)
- apple watch (4)
- ios-web (1)
- react native (3)
- TVOS (1)
- OpenGL (1)
最新评论
-
xiaobinggg:
...
Session机制详解 -
菜鸟学生会:
Drools规则工作流引擎开发教程网盘地址:http://pa ...
Drools入门-----------环境搭建,分析Helloworld -
wangyudong:
不是很好用,不支持自动化测试RESTful API,也不支持自 ...
Simple REST Client POST使用方法 -
Paul0523:
很棒的一篇文章,感谢楼主分享
Session机制详解 -
啸笑天:
获取原型对象的三种方法<script>functi ...
复习JavaScript面向对象技术
import java.util.*; public class SortedBinTree<T extends Comparable> { static class Node { Object data; Node parent; Node left; Node right; public Node(Object data , Node parent , Node left , Node right) { this.data = data; this.parent = parent; this.left = left; this.right = right; } public String toString() { return "[data=" + data + "]"; } public boolean equals(Object obj) { if (this == obj) { return true; } if (obj.getClass() == Node.class) { Node target = (Node)obj; return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent; } return false; } } private Node root; //两个构造器用于创建排序二叉树 public SortedBinTree() { root = null; } public SortedBinTree(T o) { root = new Node(o , null , null , null); } //添加节点 public void add(T ele) { //如果根节点为null if (root == null) { root = new Node(ele , null , null , null); } else { Node current = root; Node parent = null; int cmp = 0; //搜索合适的叶子节点,以该叶子节点为父节点添加新节点 do { parent = current; cmp = ele.compareTo(current.data); //如果新节点的值大于当前节点的值 if (cmp > 0) { //以右子节点作为当前节点 current = current.right; } //如果新节点的值小于当前节点的值 else { //以左子节点作为当前节点 current = current.left; } } while (current != null); //创建新节点 Node newNode = new Node(ele , parent , null , null); //如果新节点的值大于父节点的值 if (cmp > 0) { //新节点作为父节点的右子节点 parent.right = newNode; } //如果新节点的值小于父节点的值 else { //新节点作为父节点的左子节点 parent.left = newNode; } } } //删除节点,采用的是11. 25图的左边情形 public void remove(T ele) { //获取要删除的节点 Node target = getNode(ele); if (target == null) { return; } //左、右子树为空 if (target.left == null && target.right == null) { //被删除节点是根节点 if (target == root) { root = null; } else { //被删除节点是父节点的左子节点 if (target == target.parent.left) { //将target的父节点的left设为null target.parent.left = null; } else { //将target的父节点的right设为null target.parent.right = null; } target.parent = null; } } //左子树为空,右子树不为空 else if (target.left == null && target.right != null) { //被删除节点是根节点 if (target == root) { root = target.right; } else { //被删除节点是父节点的左子节点 if (target == target.parent.left) { //让target的父节点的left指向target的右子树 target.parent.left = target.right; } else { //让target的父节点的right指向target的右子树 target.parent.right = target.right; } //让target的右子树的parent指向target的parent target.right.parent = target.parent; } } //左子树不为空,右子树为空 else if(target.left != null && target.right == null) { //被删除节点是根节点 if (target == root) { root = target.left; } else { //被删除节点是父节点的左子节点 if (target == target.parent.left) { //让target的父节点的left指向target的左子树 target.parent.left = target.left; } else { //让target的父节点的right指向target的左子树 target.parent.right = target.left; } //让target的左子树的parent指向target的parent target.left.parent = target.parent; } } //左、右子树都不为空 else { //leftMaxNode用于保存target节点的左子树中值最大的节点 Node leftMaxNode = target.left; //搜索target节点的左子树中值最大的节点 while (leftMaxNode.right != null) { leftMaxNode = leftMaxNode.right; } //从原来的子树中删除leftMaxNode节点 leftMaxNode.parent.right = null; //让leftMaxNode的parent指向target的parent leftMaxNode.parent = target.parent; //被删除节点是父节点的左子节点 if (target == target.parent.left) { //让target的父节点的left指向leftMaxNode target.parent.left = leftMaxNode; } else { //让target的父节点的right指向leftMaxNode target.parent.right = leftMaxNode; } leftMaxNode.left = target.left; leftMaxNode.right = target.right; target.parent = target.left = target.right = null;//删除原来的节点 } } //根据给定的值搜索节点 public Node getNode(T ele) { //从根节点开始搜索 Node p = root; while (p != null) { int cmp = ele.compareTo(p.data); //如果搜索的值小于当前p节点的值 if (cmp < 0) { //向左子树搜索 p = p.left; } //如果搜索的值大于当前p节点的值 else if (cmp > 0) { //向右子树搜索 p = p.right; } else { return p; } } return null; } //广度优先遍历 public List<Node> breadthFirst() { Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if( root != null) { //将根元素加入“队列” queue.offer(root); } while(!queue.isEmpty()) { //将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); //如果左子节点不为null,将它加入“队列” if(p.left != null) { queue.offer(p.left); } //如果右子节点不为null,将它加入“队列” if(p.right != null) { queue.offer(p.right); } } return list; } //实现中序遍历 public List<Node> inIterator() { return inIterator(root); } private List<Node> inIterator(Node node) { List<Node> list = new ArrayList<Node>(); //递归处理左子树 if (node.left != null) { list.addAll(inIterator(node.left)); } //处理根节点 list.add(node); //递归处理右子树 if (node.right != null) { list.addAll(inIterator(node.right)); } return list; } public static void main(String[] args) { SortedBinTree<Integer> tree = new SortedBinTree<Integer>(); //添加节点 tree.add(5); tree.add(20); tree.add(10); tree.add(3); tree.add(8); tree.add(15); tree.add(30); System.out.println(tree.breadthFirst()); //删除节点 tree.remove(20); System.out.println(tree.breadthFirst()); } }
发表评论
-
qweqwe
2012-07-11 16:06 1江蛤蟆 一统江湖 -
123123123
2012-07-11 16:04 0<p>法轮</p> -
母牛繁殖问题
2011-12-30 13:08 3833question:农场的母牛寿命是5年,母牛第二年和第四年会繁 ... -
树形显示
2011-07-17 11:26 1638/** 树形结构应用十分广泛。 下面这段代码根据 ... -
求能除尽1至n的最小整数
2011-07-16 02:43 3957为什么1小时有60分钟,而不是100分钟呢?这是历史上的 ... -
java 四则运算 栈的实现
2011-07-15 13:42 13842import java.util.Stack; /* ... -
用1、2、3、3、4、5这六个数字,用java写一个程序,打印出所有不同的排列 要求:"4"不能在第三位,"3"与"5"不能相连。
2011-07-15 12:45 3370用1、2、3、3、4、5这六 ... -
【code】java红黑树
2011-06-28 10:07 3438import java.util.*; publi ... -
【code】java创建哈夫曼树和实现哈夫曼编码
2011-06-27 17:31 12877创建哈夫曼树 主要思想: (1)对List集合中所有节点进 ... -
【code】java实现十种常见内部排序
2011-06-20 19:22 3074常见的内部排序: 下面介绍这十种常见内部排序(都是从 ... -
【code】java二叉树深(先中后)、广遍历
2011-06-19 16:55 1951import java.util.*; publi ... -
【code】java二叉树的实现
2011-06-17 22:50 5848二叉树的顺序存储 public class Array ... -
【code】java树的实现
2011-06-17 22:20 11948树的父节点存储实现 import java.util. ... -
【code】java栈和队列实现
2011-06-16 22:11 4943顺序栈的实现 import java.util.Arrays ... -
【code】java线性表实现
2011-06-16 21:24 3657顺序线性表的实现 import java.util.A ...
相关推荐
java-leet-code 持续更新leet-code题解 容易(92) # 标题 标签 001 数组哈希表 007 细绳 008 字符串数组 014 字符串数组 019 链表 020 堆 021 链表 026 大批 028 字符串数组 035 数组哈希表 036 数组哈希集 048 ...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
请用java写二叉树算法,实现添加数据形成二叉树功能,并以先序的方式打印出来. 119 84.12. 请写一个java程序实现线程连接池功能? 122 84.13. 编一段代码,实现在控制台输入一组数字后,排序后在控制台输出; 122 ...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
请用java写二叉树算法,实现添加数据形成二叉树功能,并以先序的方式打印出来. 43.请写一个java程序实现线程连接池功能? 44.给定一个C语言函数,要求实现在java类中进行调用。 45.如何获得数组的长度? 46....
BinaryTree:二叉树实现源代码: LinkedList:简单的链表实现源代码: 堆栈:基本堆栈实现源代码: 卡片:洗一副卡片。 源代码: 波兰逆向符号:解决问题源代码: 河内塔:解决问题源代码: 排序算法游乐场 ...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 73 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 78 7、写一个Singleton出来。 81 8、递归算法题1 84 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、递归...
5、说明生活中遇到的二叉树,用java实现二叉树 66 6、从类似如下的文本文件中读取出所有的姓名,并打印出重复的姓名和重复的次数,并按重复次数排序: 71 7、写一个Singleton出来。 75 8、递归算法题1 77 9、...
二叉搜索树是一棵二叉树,其节点排序使得对于树中的每个节点 N: 左子树只包含值小于 N 中的值的节点 右子树只包含值大于 N 中的值的节点 这是一个有效的二叉搜索树。 B 树是二叉搜索树的推广,其中每个节点有n 个...
23、java 中实现多态的机制是什么? ......................................................................... 17 24、abstract class 和 interface 有什么区别? ...............................................
Horowitz / Sahni在“数据结构基础”中描述的“ k-Way合并”的实现。 想法是合并k个排序的数组,从而限制比较的次数。 建立一个二叉树,其中包含比较每个数组的头的结果。 最上面的节点始终是最小的条目。 然后,...