y*3
2 楼
在网上看到一个，觉得有错误。感觉如果按照他这个做，如果要delete的碰巧是middle
child，而那个middle child又有孩子，结果就不对了。
public TrinaryNode delete(key, node) {
if (node == null) {
throw new RuntimeException();
} else if (key < node.key) {
node.left = delete(key, node.left);
} else if (key > node.key) {
node.right = delete(key, node.right);
} else {
if (node.middle != null) {
node.middle = delete(key, node.middle);
} else if (node.right != null) {
node.key = findMin(node.right).key;
node.right = delete(findMin(node.right).key, node.right);
} else {
node = node.left;
}
}
return node;
}
child，而那个middle child又有孩子，结果就不对了。
public TrinaryNode delete(key, node) {
if (node == null) {
throw new RuntimeException();
} else if (key < node.key) {
node.left = delete(key, node.left);
} else if (key > node.key) {
node.right = delete(key, node.right);
} else {
if (node.middle != null) {
node.middle = delete(key, node.middle);
} else if (node.right != null) {
node.key = findMin(node.right).key;
node.right = delete(findMin(node.right).key, node.right);
} else {
node = node.left;
}
}
return node;
}
g*n
3 楼
记得以前在edas提交paper的时候都有一个plagiarism report
刚才去看了下没找到
网上只有
http://www.ithenticate.com/products/plagiarism-detection-produc
$50 一次
刚才去看了下没找到
网上只有
http://www.ithenticate.com/products/plagiarism-detection-produc
$50 一次
T*e
4 楼
our old friend -- kevin
【在 W*****t 的大作中提到】
: 哎
【在 W*****t 的大作中提到】
: 哎
y*3
5 楼
up
W*t
6 楼
那还不错啊，至少知道是他了
啥时候能知道那个rebation还是啥的网站是谁的啊
【在 T*********e 的大作中提到】
: our old friend -- kevin
啥时候能知道那个rebation还是啥的网站是谁的啊
【在 T*********e 的大作中提到】
: our old friend -- kevin
x*1
7 楼
顶一下！
P*r
8 楼
还是大片。。。
y*3
9 楼
这道题是zillow的筛选assignment两题中的一道，每个candidate都要做的，班上应该
讨论出个标准答案来。
讨论出个标准答案来。
N*t
10 楼
贴代码，如有错误，请私信。
/**
* Implement insert and delete in a trinary tree.
*
*/
public class TrinaryTree {
/**
* define a trinary tree's node
*
*/
static class TreeNode{
public int val; // node's value
public TreeNode left, right, mid; // represent left, right, middle
node
public TreeNode(int v){
this.val = v;
left = null;
right = null;
mid = null;
}
}
TreeNode root;
public TrinaryTree(){
root = null;
}
public void insert(int v){
root = insert(root, v);
}
/**
* insert a node into the tree
* @param node
* @param v
* @return
*/
public TreeNode insert(TreeNode node, int v){
if(node == null){
node = new TreeNode(v);
System.out.println("Insert node "+v);
} else {
if(node.val > v){
node.left = insert(node.left,v);
} else if(node.val < v) {
node.right = insert(node.right,v);
} else {
node.mid = insert(node.mid,v);
}
}
return node;
}
public void delete(int v){
root = delete(root,v);
}
/**
* delete a node from the tree, if there are duplicates, delete the
lowest one
* @param node
* @param v
* @return
*/
public TreeNode delete(TreeNode node, int v){
//can't find the node, return
if(node == null){
System.out.println("Can not find node "+v);
return null;
} else if(node.val > v){
node.left = delete(node.left,v);
} else if(node.val < v){
node.right = delete(node.right,v);
} else {
if(node.mid != null){
node.mid = delete(node.mid,v);
} else if(node.right != null){
node.val = findMin(node.right);
node.right = delete(node.right,node.val);
} else {
System.out.println("Delete node "+node.val);
node = node.left;
}
}
return node;
}
/**
* find the leftmost(minimum) node and delete it
* @param node
* @return
*/
public int findMin(TreeNode node){
if(node.left == null){
int v = node.val;
return v;
} else {
return findMin(node.left);
}
}
public static void main(String[]args){
TrinaryTree tree = new TrinaryTree();
int[] num = {5,4,9,5,7,2,2};
for(int i = 0; i < num.length; i++){
tree.insert(num[i]);
}
//delete a node doesn't exist
tree.delete(1);
//delete one of duplicates
tree.delete(5);
tree.delete(2);
//delete the node has both children
tree.delete(5);
//delete the node only has left child
tree.delete(4);
//delete leaf node
tree.delete(2);
tree.delete(9);
//delete single node
tree.delete(7);
//delete a node from an empty tree
tree.delete(2);
}
}
/**
* Implement insert and delete in a trinary tree.
*
*/
public class TrinaryTree {
/**
* define a trinary tree's node
*
*/
static class TreeNode{
public int val; // node's value
public TreeNode left, right, mid; // represent left, right, middle
node
public TreeNode(int v){
this.val = v;
left = null;
right = null;
mid = null;
}
}
TreeNode root;
public TrinaryTree(){
root = null;
}
public void insert(int v){
root = insert(root, v);
}
/**
* insert a node into the tree
* @param node
* @param v
* @return
*/
public TreeNode insert(TreeNode node, int v){
if(node == null){
node = new TreeNode(v);
System.out.println("Insert node "+v);
} else {
if(node.val > v){
node.left = insert(node.left,v);
} else if(node.val < v) {
node.right = insert(node.right,v);
} else {
node.mid = insert(node.mid,v);
}
}
return node;
}
public void delete(int v){
root = delete(root,v);
}
/**
* delete a node from the tree, if there are duplicates, delete the
lowest one
* @param node
* @param v
* @return
*/
public TreeNode delete(TreeNode node, int v){
//can't find the node, return
if(node == null){
System.out.println("Can not find node "+v);
return null;
} else if(node.val > v){
node.left = delete(node.left,v);
} else if(node.val < v){
node.right = delete(node.right,v);
} else {
if(node.mid != null){
node.mid = delete(node.mid,v);
} else if(node.right != null){
node.val = findMin(node.right);
node.right = delete(node.right,node.val);
} else {
System.out.println("Delete node "+node.val);
node = node.left;
}
}
return node;
}
/**
* find the leftmost(minimum) node and delete it
* @param node
* @return
*/
public int findMin(TreeNode node){
if(node.left == null){
int v = node.val;
return v;
} else {
return findMin(node.left);
}
}
public static void main(String[]args){
TrinaryTree tree = new TrinaryTree();
int[] num = {5,4,9,5,7,2,2};
for(int i = 0; i < num.length; i++){
tree.insert(num[i]);
}
//delete a node doesn't exist
tree.delete(1);
//delete one of duplicates
tree.delete(5);
tree.delete(2);
//delete the node has both children
tree.delete(5);
//delete the node only has left child
tree.delete(4);
//delete leaf node
tree.delete(2);
tree.delete(9);
//delete single node
tree.delete(7);
//delete a node from an empty tree
tree.delete(2);
}
}
相关阅读