面试时让我手写二叉查找树删除节点函数

找个实习不容易，今天去面试，面试官先问了我JVM的很底层东西，因为看过深入了解JVM这本书答得很顺，结果面试官来劲了，先说 你给我写一个 平衡二叉查找树删除节点的代码，我故意念到 “平衡二叉查找树”，面试官见我认怂说那你写二叉查找吧，我只知道删除节点有三种情况，分为删除节点是否是叶子节点，有一个子节点，有两个子节点，但是当场手写代码还是没有写出来。回来在参考书的帮助下手写了一遍。哎，基础不行。

 

 

package graphic;

public class BinarySearchTree {
  private TreeNode root = null;
/**
 * 中序遍历
 * @param root
 */
public void inOrder_tree_walk(){
	inOrder(root);
}

private void inOrder(TreeNode root){
	if(root==null){return;}
	inOrder(root.left);
	System.out.print(root+" ");
	inOrder(root.right);
}
/**
 * 返回指向key的节点指针
 * @param root
 * @param key
 * @return
 */
public TreeNode treeSearch(int key){
	if(root==null)return null;
	TreeNode cur = root;
	while(cur!=null && cur.value!=key){
		if(cur.value >key){
			cur = cur.left;
		}else{
			cur = cur.right;
		}
	}
	return cur;
}

/**
 * 返回包含最小key的节点指针
 */
public TreeNode treeMinimum(TreeNode root){
	if(root==null)return null;
	TreeNode cur = root;
	while(cur.left!=null){
		cur = cur.left;
	}
	return cur;
}

/**
 * 返回包含最大key的节点指针
 * @param root
 * @return
 */
public TreeNode treeMaximum(TreeNode root){
	if(root==null)return null;
	TreeNode cur = root;
	while(cur.right!=null){
		cur = cur.right;
	}
	return cur;
}

/**
 * 返回node 节点的后继节点
 * @param root
 * @param node
 * @return
 */
public TreeNode treeSuccessor(TreeNode node){
	//rigth branch is not null
	if(node.right!=null)return treeMinimum(node.right);
	
	//if the right branch is null
	TreeNode cur = node.parent;
	while(cur!=null && node == cur.right){
		node = cur;
		cur = cur.parent;
	}
	return cur;
}

/**
 * 返回node 节点的前继节点
 * @param root
 * @param node
 * @return
 */
public TreeNode treePredecessor(TreeNode node){
	if(root.left!=null) return treeMaximum(root.left);
	
	//the left branch is null
	TreeNode cur = node.parent;
	while(cur!=null && node==cur.left){
		node = cur;
		cur = cur.parent;
	}
	return cur;
	
}

/**
 * 插入新节点
 * @param root
 * @param insert
 */
public void treeInsert(TreeNode insert){
	if(root==null){
		root = insert;
		return ;
	}
	TreeNode cur = root;
	TreeNode parent =null;
	while(cur!=null){
		parent = cur;
		if(insert.value >=cur.value){cur = cur.right;}
		else{cur = cur.left;}
	}
	if(insert.value >=parent.value){
		parent.right = insert;
		insert.parent = parent;
	}else{parent.left = insert;insert.parent = parent;}
	
}

/**
 * 删除目标节点
 * @param root
 * @param target
 */
public void delete(TreeNode target){
	//find the node need to be deleted
	TreeNode delNode;
         //只有一个孩子或者是叶子节点
	if(target.left==null || target.right==null){
		delNode = target;
       
	}else{
                //如果有两个孩子就找到后继节点作为删除的节点
		delNode = treeSuccessor(target);
	}
	
	//对于所有情况，要删除的节点最多只有一个孩子
        //这个时候需要找到删除节点的孩子节点和父亲节点，并把父亲节点指向孩子节点，
        //孩子节点的指针也指回新的父亲节点
	TreeNode child;
	if(delNode.left ==null){
		child = delNode.right;
	}else{child = delNode.left;}
	TreeNode parent = delNode.parent;
	if(parent.left == delNode){
		parent.left = child;
	}else{
		parent.right = child;
	}
	if(child!=null){
		child.parent = parent;
	}
	
	//delete the successor
	if(delNode!=target){
		target.value = delNode.value;
	}
	
	freeNode(delNode);
}


/**
 * 删除包含key的第一个节点
 * @param root
 * @param key
 */
public void treeDelete(int key){
	TreeNode searched = treeSearch(key);
	delete(searched);
}

private void freeNode(TreeNode node){
	node.parent =null;
	node.left = null;
	node.right = null;
}
private void addNode(TreeNode node){
	treeInsert(node);
}

private class TreeNode{
	TreeNode parent = null;
	TreeNode left = null;
	TreeNode right = null;
	int value = 0;
	@Override
	public String toString() {
		return value+"";
	}
	
	public TreeNode(int value) {
		this.value = value;
	}
}

	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		TreeNode node =  tree.new TreeNode(15);
		tree.addNode(node);
		
		node =  tree.new TreeNode(6);
		tree.addNode(node);
		
		node =  tree.new TreeNode(18);
		tree.addNode(node);
		
		node =  tree.new TreeNode(3);
		tree.addNode(node);
		node =  tree.new TreeNode(7);
		tree.addNode(node);
		node =  tree.new TreeNode(17);
		tree.addNode(node);
		node =  tree.new TreeNode(20);
		tree.addNode(node);
		
		node =  tree.new TreeNode(2);
		tree.addNode(node);
		node =  tree.new TreeNode(4);
		tree.addNode(node);
		node =  tree.new TreeNode(13);
		TreeNode node13= node;
		tree.addNode(node);
		node =  tree.new TreeNode(9);
		tree.addNode(node);
		
		tree.inOrder_tree_walk();
		System.out.println();
		System.out.println(tree.treeSearch(15).parent);
		System.out.println(tree.treeSuccessor(node13));
		tree.treeDelete(6); 
		tree.inOrder_tree_walk();
		

	}


}

 

 

评论

7 楼 kjmmlzq19851226 2013-06-17  

sunlujing 写道

kjmmlzq19851226 写道

面试嘛就说哈思路就行了，真要写的话10个有9.5个写不出来的

当时我就想对面试官说 你20分钟要是写出平衡二叉树删除节点的代码，我永世不入你们公司。

6 楼 sunlujing 2013-06-14  

kjmmlzq19851226 写道

面试嘛就说哈思路就行了，真要写的话10个有9.5个写不出来的

当时我就想对面试官说 你20分钟要是写出平衡二叉树删除节点的代码，我永世不入你们公司。

5 楼 kjmmlzq19851226 2013-06-14  

面试嘛就说哈思路就行了，真要写的话10个有9.5个写不出来的

4 楼 sunlujing 2013-06-11  

hamber 写道

目测楼主应该很牛逼的样子。

我要是很牛逼就不至于找个实习都老费劲了。哎

3 楼 hamber 2013-06-11  

目测楼主应该很牛逼的样子。

2 楼 sunlujing 2013-06-11  

lvwenwen 写道

深入了解JVM?是哪一本啊

深入理解java虚拟机--周志明，觉得不错。

1 楼 lvwenwen 2013-06-11  

深入了解JVM?是哪一本啊