y*****3
发帖数: 451 | 1 在网上看到一个，觉得有错误。感觉如果按照他这个做，如果要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;
} | y*****3
发帖数: 451 | | x*********1
发帖数: 23 | | y*****3
发帖数: 451 | 4 这道题是zillow的筛选assignment两题中的一道，每个candidate都要做的，班上应该
讨论出个标准答案来。 | N******t
发帖数: 43 | 5 贴代码，如有错误，请私信。
/**
* 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);
}
} |
|
