「bst判定java」BST是啥意思
本篇文章给大家谈谈bst判定java，以及BST是啥意思对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、二叉排序树（BST） Java实现
- 2、java 判断两个时间段是不是有交集
- 3、Java中CompareTo()方法的问题
- 4、java判断一个二叉树是不是合法的二分查找树
- 5、java数据结构二叉树引文试题求解
二叉排序树（BST） Java实现
public class NodeE {
int key; // data used as key value
E data; // other data
NodeE leftChild; // this node's left child
NodeE rightChild; // this node's right child
public Node(int key, E o) {
this.key = key;
this.data = o;
}
public void displayNode() {
System.out.printf("%d, %s\n", key, data.toString());
}
}
===============================================================
package net.acoder.adt.tree;
public class TreeE {
private NodeE root;
public Tree(NodeE root) {
if (root == null) {
throw new NullPointerException("root can't be null");
}
this.root = root;
}
public Tree(int key, E o) {
this(new NodeE(key, o));
}
public NodeE getRoot() {
return root;
}
/**
* find a node by its key
*
* @param key
* @return
*/
public NodeE find(int key) {
NodeE current = root;
while (current.key != key) {
if (key current.key) {
current = root.leftChild;
} else {
current = root.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
/**
* insert a node to this tree
*
* @param key
* @param o
*/
public void insert(int key, E o) {
NodeE aNode = new NodeE(key, o);
if (root == null) {
this.root = aNode;
return;
}
NodeE current = root;
NodeE parent = root;
while (true) {
parent = current;
if (key parent.key) {
current = parent.leftChild;
if (current == null) {
parent.leftChild = aNode;
return;
}
} else {
current = parent.rightChild;
if (current == null) {
parent.rightChild = aNode;
return;
}
}
}
}
public boolean delete(int key) {
NodeE current = root;
NodeE parent = root;
boolean isLeftChild = true;
// search for node
while (current.key != key) {
parent = current;
if (key current.key) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
// if no children, simply delete it
if (current.leftChild == null current.rightChild == null) {
if (current == parent) {
root = null;
} else if (isLeftChild == true) {
parent.leftChild = null;
} else if (isLeftChild == false) {
parent.rightChild = null;
}
return true;
}
// if no left children, replace with right subtree
if (current.leftChild == null) {
if (current == root) {
root = current.rightChild;
} else if (isLeftChild) {
parent.leftChild = current.rightChild;
} else if (!isLeftChild) {
parent.leftChild = current.rightChild;
}
return true;
}
// if no right children, replace with left subtree
if (current.rightChild == null) {
if (current == root) {
root = current.leftChild;
} else if (isLeftChild) {
parent.leftChild = current.leftChild;
} else if (!isLeftChild) {
parent.leftChild = current.leftChild;
}
return true;
}
// get successor of node to delete
NodeE successor = getSuccessor(current);
if (current == root) {
current = successor;
} else if (isLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
return true;
}
private NodeE getSuccessor(NodeE delNode) {
NodeE successorParent = delNode;
NodeE successor = delNode;
NodeE current = delNode.rightChild;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public void inOrder(NodeE aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
aNode.displayNode();
inOrder(aNode.rightChild);
}
}
public void preOrder(NodeE aNode) {
if (aNode != null) {
aNode.displayNode();
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
}
}
public void backOrder(NodeE aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
aNode.displayNode();
}
}
public NodeE minimum() {
NodeE current = this.root;
NodeE result = null;
while (current != null) {
result = current;
current = current.leftChild;
}
return result;
}
public NodeE maximum() {
NodeE current = this.root;
NodeE result = null;
while (current != null) {
result = current;
current = current.rightChild;
}
return result;
}
}
以前的代码, 记得没写完, 好像就是BST
java 判断两个时间段是不是有交集
public class DateKit{
/**
时间段的比较处理 , 如果包含了传来的 时段 了, 就说明 时间冲突了
* @return
*/
public static boolean isContain(Date[] a, Date[] b) {
long astatr = a[0].getTime();
long aend = a[1].getTime();
long bstatr = b[0].getTime();
long bend = b[1].getTime();
// a0 包在了 b0 ~ b1 之间
if( astatr=bstatr astatr=bend ) return true;
// b0 包在了 a0 ~ a1 之间
if( astatr=bstatr aend=bstatr ) return true;
return false;
}
/**
时间段的比较处理 , 如果包含了传来的 时段 了, 就说明 时间冲突了 , (允许首尾相等而不包含的情况)
* @return
*/
public static boolean isContainEnd(Date[] a, Date[] b) {
long astatr = a[0].getTime();
long aend = a[1].getTime();
long bstatr = b[0].getTime();
long bend = b[1].getTime();
// a0 包在了 b0 ~ b1 之间
if( astatr=bstatr astatrbend ) return true;
// b0 包在了 a0 ~ a1 之间
if( astatr=bstatr aendbstatr ) return true;
// 相等
if( astatr==bstatr aend==bend ) return true;
return false;
}
// 功能 工具 扩展
public static boolean isContain(String astatr,String aend, String bstatr,String bend) {
return isContain(new String[]{astatr , aend}, new String[]{bstatr , bend});
}
public static boolean isContain(String[] aStr, String[] bStr) {
return isContain(aStr, bStr, "yyyy-MM-dd HH:mm:ss");
}
public static boolean isContain(String[] aStr, String[] bStr, String pattern) {
final SimpleDateFormat SF = new SimpleDateFormat(pattern);
try {
return isContain(new Date[]{SF.parse(aStr[0]), SF.parse(aStr[1])} , new Date[]{SF.parse(bStr[0]), SF.parse(bStr[1])});
} catch (Exception e) {
e.printStackTrace();
}
return false;
}
public static boolean isContainEnd(String astatr,String aend, String bstatr,String bend) {
return isContainEnd(new String[]{astatr , aend}, new String[]{bstatr , bend});
}
public static boolean isContainEnd(String[] aStr, String[] bStr) {
return isContainEnd(aStr, bStr, "yyyy-MM-dd HH:mm:ss");
}
public static boolean isContainEnd(String[] aStr, String[] bStr, String pattern) {
final SimpleDateFormat SF = new SimpleDateFormat(pattern);
try {
return isContainEnd(new Date[]{SF.parse(aStr[0]), SF.parse(aStr[1])} , new Date[]{SF.parse(bStr[0]), SF.parse(bStr[1])});
} catch (Exception e) {
e.printStackTrace();
}
return false;
}
}
测试:
public static void main(String[] args) throws ParseException {
final SimpleDateFormat SF = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date[] a = {SF.parse("2017-07-06 11:53:00"), SF.parse("2017-07-06 14:52:00")};
Date[] b = {SF.parse("2017-07-06 14:52:00"), SF.parse("2017-07-06 16:52:00")};
System.out.println("您好, 智能的电脑! 请问:");
for (Date date : a) {
System.out.print(date.toString() + " ~ ");
}
System.out.println("包含:");
for (Date date : b) {
System.out.print(date.toString() + " ~ ");
}
System.out.println("吗?");
boolean ret = DateKit.isContain(a, b);
System.out.println("o(∩_∩)o 哈哈 ~ 我猜是: " + ret);
ret = DateKit.isContainEnd(a, b);
System.out.println("o(∩_∩)o 哈哈 ~ 允许首尾相等 我猜是: " + ret);
}
找了半天, 没见写的好的. 自己动手写个, 问题是 两个时段,, 大部分人给的是 两个时间点..
Java中CompareTo()方法的问题
楼上正解，应为um.getUserId（）内容已经实现compareTo 接口功能
Java.lang.String API中有定义
compareTo
public int compareTo(String anotherString)按字典顺序比较两个字符串。该比较基于字符串中各个字符的 Unicode 值。将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。如果按字典顺序此 String 对象在参数字符串之前，则比较结果为一个负整数。如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。如果这两个字符串相等，则结果为 0；compareTo 只有在方法 equals(Object) 返回 true 时才返回 0。
java判断一个二叉树是不是合法的二分查找树
java判断一个二叉树是不是合法的二分查找树
/* 判断一个二叉树是不是合法的二分查找树的简单的递给方法，学习
* 采用自顶向下的遍历方式，对于每个节点，检查顶部传来的范围要求，
* 要求是指：对于左子树，父节点的值就是最大值，对于右子树，父节点的值就是最小值
*/
public boolean isValidBST(TreeNode root) {
//初始的时候，对根节点没有范围要求
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
//检查是否满足根节点的范围要求
if (root.val = maxVal || root.val = minVal)
return false;
//修改对子节点的要求，对于左子树，本节点的值就是最大值，对于右子树，本节点的值就是最小值
return isValidBST(root.left, minVal, root.val) isValidBST(root.right, root.val, maxVal);
java数据结构二叉树引文试题求解
a)从根结点开始循环调用rightSubtree，直到isEmpty为true，此时得到的结点为最大植。
b)先序遍历整个BST，将所有leftSubtree和rightSubtree为empty的结点进行记数，最后可以得到所有叶子结点数。
做作业还是要自己动手好。
bst判定java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于BST是啥意思、bst判定java的信息别忘了在本站进行查找喔。
发布于：2022-11-28，除非注明，否则均为原创文章，转载请注明出处。