- 浏览: 584068 次
- 来自: ...
文章分类
最新评论
-
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 3663题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1527POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2982POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1849题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1594关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1831POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1564分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2174接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1355接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1767关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1674关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1751关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2023POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1285问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2100在http://poj.org/上用JAVA解题一般用 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1733777
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
NULL 博文链接:https://128kj.iteye.com/blog/1746750
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
数算的二叉树的POJ作业,分别有:二叉树1_二叉树的操作;二叉树2_文本二叉树;二叉树3_由中根序列和后根序列重建二叉树;二叉树4_表达式.表达式树....二叉树5_Huffman编码树;二叉树6_二叉搜索树;二叉树7_实现堆结构
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ中级搜索全部练习【解题报告+AC代码】
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1748635
POJ 二叉搜索树 嘻嘻嘻 做的时候是一遍过好开心~~
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
NULL 博文链接:https://128kj.iteye.com/blog/1753387
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
NULL 博文链接:https://128kj.iteye.com/blog/1749213
供初学编程基本算法的人练习使用,在poj.grids.cn上