- 浏览: 604174 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子、右儿子,如果结点不存在,则为NULL。
它或者是一棵空树;或者是具有下列性质的二叉树:
1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉查找树;
显然满足了上面的性质,那么二叉查找树按中序遍历就是按从小到大的顺序遍历,这也就是为什么叫排序树的原因,当然上面的小于和大于都可以根据自己的需求改变的。
二叉查找树的几个常用操作:查找,删除,插入.
例:POJ 1577
大意就是给出一个二叉搜索树,但给出的方式比较奇怪,是先给出最外层的叶子节点,然后揪掉这些叶子,把剩下的结点中变成叶子结点的再给出,这样一直到所有的结点都被揪掉。 最后要求这个二叉搜索树的先序遍历的结果。
样例:
Sample Input
BDHPY
CM
GQ
K
*
AC
B
$
Sample Output
KGCBDHQMPY
BAC
此题就是要求建立一颗二叉树查找树,再进行前序遍历即可得到结果。
它或者是一棵空树;或者是具有下列性质的二叉树:
1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉查找树;
显然满足了上面的性质,那么二叉查找树按中序遍历就是按从小到大的顺序遍历,这也就是为什么叫排序树的原因,当然上面的小于和大于都可以根据自己的需求改变的。
二叉查找树的几个常用操作:查找,删除,插入.
例:POJ 1577
大意就是给出一个二叉搜索树,但给出的方式比较奇怪,是先给出最外层的叶子节点,然后揪掉这些叶子,把剩下的结点中变成叶子结点的再给出,这样一直到所有的结点都被揪掉。 最后要求这个二叉搜索树的先序遍历的结果。
样例:
Sample Input
BDHPY
CM
GQ
K
*
AC
B
$
Sample Output
KGCBDHQMPY
BAC
此题就是要求建立一颗二叉树查找树,再进行前序遍历即可得到结果。
import java.util.*; public class Main { BinarySearchTree< Character> root = new BinarySearchTree< Character>();//二叉查找树 List<String> list; public Main(List<String> list){ this.list=list; } public void go(){ String input=null; for(int i = list.size()-1; i >=0; i--){ input = list.get(i); for(int j = 0; j < input.length(); j++){ root.insert((Character)input.charAt(j)); } } root.printTree(); } public static void main(String[] args){ Scanner in =new Scanner(System.in); boolean stop = false; while(true){ List< String> list = new ArrayList< String>(); while(in.hasNext()){ String input = in.next(); if(input.charAt(0) =='*') break; if(input.charAt(0) == '$'){ stop = true; break; } list.add(input); } Main ma=new Main(list); ma.go(); if(stop){ return; } System.out.println(); } } } class BinaryNode< T extends Comparable<T>> {//二叉查找树节点 BinaryNode< T> left; BinaryNode< T> right; T element; public BinaryNode(T theElement){ this(theElement, null, null); } public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){ element = theElement; left = lt; right = rt; } public T getElement(){ return this.element; } public BinaryNode< T> getLeft(){ return this.left; } public BinaryNode< T> getRight(){ return this.right; } public String toString(){ return element + ""; } } class BinarySearchTree< T extends Comparable<T>>{//二叉搜索树 private BinaryNode< T> root;//根节点 public BinarySearchTree(){//构造函数 root = null; } public BinarySearchTree(BinaryNode< T> t){//构造函数 root = t; } public void makeEmpty(){ root = null; } public boolean isEmpty(){ return root == null; } public T find(T x){ return find(x, root).element; } public void insert(T x){ root = insert(x, root); } public void printTree(){ printTree(root); } private BinaryNode< T> find(T x, BinaryNode< T> t){//查找操作 if(t == null){ return null; } if(x.compareTo(t.element) < 0){ return find(x, t.left); } else if(x.compareTo(t.element) == 0){ return t; } else{ return find(x, t.right); } } private BinaryNode< T> insert(T x, BinaryNode< T> t){//插入操作 if(t == null){ t = new BinaryNode< T>(x, null, null); } else if(x.compareTo(t.element) < 0){ t.left = insert(x, t.left); } else if(x.compareTo(t.element) > 0){ t.right = insert(x, t.right); } else; return t; } private void printTree(BinaryNode< T> t){//前序遍历二叉查找树 if(t != null){ System.out.print(t.element); printTree(t.left); printTree(t.right); } } }
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3775题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1679POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1486POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1936题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1647关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1876关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1895POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1912POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1771POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1664分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2266接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1551关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1845关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1823关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2122POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1359问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2159在http://poj.org/上用JAVA解题一般用 ...
相关推荐
* 静态二叉检索树 + poj2482, poj2352 * 树状树组 + poj1195, poj3321 * RMQ + poj3264, poj3368 * 并查集的高级应用 + poj1703, poj2492 * KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 *...
- **树的应用**:如二叉搜索树、哈夫曼树等。 ### 6. 其他算法类别 除了以上介绍的主要算法类别之外,还存在一些其他的算法分类,例如贪心算法、回溯算法、分治算法等。每一种算法都有其独特的应用场景和解决问题...
红黑树是一种自平衡二叉查找树,它的每个节点都带有红色或黑色,并且遵循一些特定的规则以确保其性能。 描述中提到的“NULL”意味着没有提供具体的题目描述,但通常在POJ(Programming Online Judge)这样的在线...
比如,用二叉搜索树解决排序问题,用哈希表实现快速查找,或者用优先队列处理最小生成树等经典问题。 算法是解决问题的灵魂。排序算法(如冒泡、插入、选择、快速、归并排序)、查找算法(如线性、二分查找)、图论...
- **查找**:二分查找、线性查找和二叉搜索树等提供了高效的查找策略。 - **动态规划**:解决最优化问题的利器,如背包问题、最长公共子序列等。 - **贪心算法**:通过局部最优决策达到全局最优,例如霍夫曼编码...
尽管我们没有具体的信息来界定“POJ12”确切包含哪些题目,但根据POJ的分类习惯,我们可以假设这一类问题可能是关于特定的数据结构,如二叉搜索树、堆排序、或者特定的算法,例如动态规划、贪心算法等。这样的问题集...
对于中级阶段,深入学习 C++ 标准模板库的应用、更复杂的模拟题、差分约束系统、最小费用最大流、双连通分量等复杂图算法、线段树、静态二叉检索树、RMQ 和 KMP 算法等,都是进一步提升算法能力的关键。 总的来说,...
- **深度优先搜索**(DFS):通过Poj2488、Poj3083等题目进行练习。 - **广度优先搜索**(BFS):如Poj3278、Poj1426等。 - **搜索技巧和剪枝**:学习如何减少无效搜索,如Poj2531、Poj1416等。 5. **动态规划**...
4. 数据结构高级应用:线段树、静态二叉检索树、树状数组、RMQ和并查集的更复杂用法。 5. 搜索优化:最优化剪枝、搜索技巧和记忆化搜索。 这些内容构成了一个全面的ACM训练框架,旨在全面提升参赛者的编程思维、...
北京大学的POJ题库是为ACM(国际大学生程序设计竞赛)训练而设立的一个在线编程练习平台,提供了丰富的算法题目供学习者进行实践。本文将详细介绍这个题库中涉及的主要算法类别及其代表性题目,帮助你更好地理解和...
5. POJ 1080 - 1088: 随着编号接近尾声,题目难度可能更大,可能涵盖高级数据结构(如二叉堆、红黑树)或复杂算法(如最小生成树、拓扑排序)。解这些题目需要扎实的理论基础和良好的问题解决能力。 这些源码提供了...
- **示例题目**: 通常这类题目没有特定的POJ编号,但可以通过练习递归和分治的基本题目来掌握。 - **注意事项**: 避免无限递归,并合理设置递归的出口。 **4. 递推** - **定义**: 递推是一种利用前几项的结果来...
4. **树状数组/二叉索引树**(如poj3253):用于高效更新和查询区间和或区间最大值等统计信息,适用于动态数组维护、区间统计问题。 5. **Trie树**(如poj2513):用于存储字符串集合,特别适合前缀搜索和模式匹配,...
6. **数据结构**:如堆(优先队列)、平衡二叉搜索树(AVL、红黑树)、字典树(Trie)等,用于高效地进行查找、插入和删除操作。 7. **模拟**:对于某些问题,可能需要编写程序模拟特定过程,如游戏策略、物理过程...
- **所需知识**: 树的定义、遍历方法、特殊树结构(如二叉查找树、红黑树等)。 #### 2. 字符串处理 - **题目**: 包括`poj3278`、`poj1426`等。 - **所需知识**: 字符串的常见操作、模式匹配算法(如KMP算法)、...
- **定义**: 深度优先遍历是从根节点开始,尽可能深的搜索树的分支;广度优先遍历则先访问根节点,然后从左至右访问根节点的所有相邻节点,再依次对每个相邻节点执行同样的操作。 - **应用场景**: 广泛应用于图的...
2.4.3 二叉搜索树 2.4.4 并查集 2.5 它们其实都是“图” 2.5.1 图是什么 2.5.2 图的表示 2.5.3 图的搜索 2.5.4 最短路问题 2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关...
2. **图论**:包括深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理图遍历、最短路径、最小生成树等问题时非常有用。 3. **排序与查找**:快速排序、归并排序、二分查找等经典算法常常出现在ACM题目中,...
代码可能会使用到C++标准库中的算法,如排序、查找,也可能涉及到高效的数据结构,如动态规划数组或平衡二叉搜索树。此外,为了优化运行时间和内存使用,代码可能还采用了各种技巧,如预处理数据、剪枝、缓存优化等...