当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

名企面试100题_15

发表于: 2012-05-17   作者:EmmaZhao   来源:转载   浏览次数:
摘要: 第15题(树): 题目:输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点。 用递归和循环两种方法完成树的镜像转换。 package cn.emma.interview_15; public class Mirror { public static void getMirror(BinaryTree.T
第15题(树):

题目:输入一颗二元查找树,将该树转换为它的镜像,

即在转换后的二元查找树中,左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。
package cn.emma.interview_15;


public class Mirror {

	public static void getMirror(BinaryTree.TreeNode tree){
		if(tree != null){
			BinaryTree.TreeNode temp = tree.left;
			tree.left = tree.right;
			tree.right = temp;
			getMirror(tree.left);
			getMirror(tree.right);
		}
	}
	public static void main(String[] args) {
		try {  
            BinaryTree bst = new BinaryTree();  
            int[] keys = new int[] {5, 6, 7, 8, 9, 10, 11};  
            for (int key: keys) {  
                bst.insert(key);  
            }  
            bst.inOrderTraverse();
            bst.print();
           getMirror(bst.getRoot());
           	bst.inOrderTraverse();
            bst.print();
        } catch (Exception e) {  
            System.out.println(e.getMessage());  
            e.printStackTrace();  
        }  
        
	}
}


package cn.emma.interview_15;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Emma
 * @param <T>
 */
public class BinaryTree {
	
	private TreeNode root = null;
	private List<TreeNode> nodeList = new ArrayList<BinaryTree.TreeNode>();
	
	public TreeNode getRoot() {
		return root;
	}

	public void setRoot(TreeNode root) {
		this.root = root;
	}

	public List<TreeNode> getNodeList() {
		return nodeList;
	}


	public void setNodeList(List<TreeNode> nodeList) {
		this.nodeList = nodeList;
	}

	public class TreeNode{
		TreeNode parent;
		TreeNode left;
		TreeNode right;
		
		int value;
		
		public TreeNode(TreeNode parent,TreeNode left,TreeNode right,int value) {
			// TODO Auto-generated constructor stub
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.value = value;
		}
		public int getVlaue(){
			return value;
		}
	}
	
	public boolean isEmpty(){
		if(root == null){
			return true;
		}else{
			return false;
		}
	}
	
	
	/**
	 * 给定关键字插入到二叉查找树中
	 * @param value
	 */
	public void insert(int value){
		TreeNode newNode = new TreeNode(null, null, null, value);
		TreeNode pNode;
		TreeNode parentNode = null;
		if(root == null){
			root = newNode;
		}else{
			pNode = root;
			while(pNode != null){
				parentNode = pNode;
				if(pNode.getVlaue() < value){
					pNode = pNode.right;
				}else if(pNode.getVlaue() > value){
					pNode = pNode.left;
				}else{
					System.out.println("Value " + value + " has already existed in the tree.");
				}
			}
			if(value < parentNode.getVlaue()){
				parentNode.left = newNode;
				newNode.parent = parentNode;
			}else if (value > parentNode.getVlaue()) {
				parentNode.right = newNode;
				newNode.parent = parentNode;
			}
		}
	}
	
	/**
	 * 给定关键字,删除二叉查找树的相应节点
	 * @param key
	 */
	public void delete(int key){
		TreeNode node = search(key);
		if(node == null){
			System.out.println("树中不包含此节点");
		}else{
			delete(node);
		}
		
	}
	private void delete(TreeNode node){
		TreeNode parentNode = node.parent;
		if(node.left != null && node.right != null){
			TreeNode p = processor(node);
			TreeNode s = successor(node);
			if(node == parentNode.left){
				p.right = node.right;
				node.right.parent = p;
				parentNode.left = node.left;
				node.left.parent = parentNode;
				node = null;
			}else {
				s.left = node.left;
				node.left.parent = s;
				parentNode.right = node.right;
				node.right.parent = parentNode;
				node = null;
			}
		}else if(node.left != null){
			parentNode.left = node.left;
			node.parent = parentNode;
		}else if(node.right != null){
			parentNode.right = node.right;
			node.right.parent = parentNode;
		}else{
			if(node == parentNode.left){
				parentNode.left = null;
			}else{
				parentNode.right = null;
			}
		}
	}
	
	/**
	 * 搜索值为key的节点
	 * @param key
	 * @return
	 */
	public TreeNode search(int key){
		if(root == null){
			return null;
		}else{
			TreeNode p = root;
			while(p != null){
				if(p.getVlaue() == key){
					return p;
				}else if(p.getVlaue() < key){
					p = p.right;
				}else{
					p = p.left;
				}
			}
			return null;
		}
	}
	
	/**
	 * 获取该树中序遍历下的前驱结点
	 * @param node
	 * @return
	 */
	public TreeNode processor(TreeNode node){
		TreeNode pNode = null;
		if(node == null){
			return null;
		}
		else{
			if(node.left == null){
				return node.parent;
			}else{
				pNode = node.left;
				while(pNode.right != null){
					pNode = pNode.right;
				}
				return pNode;
			}
		}
	}
	
	/**
	 * 获取该书中序遍历的后继结点
	 * @param node
	 * @return
	 */
	public TreeNode successor(TreeNode node){
		TreeNode sNode = null;
		if(node == null){
			return null;
		}else{
			if(node.right == null){
				sNode = node.parent;
			}else {
				sNode = node.right;
				while(sNode.left != null){
					sNode = sNode.left;
				}
			}
			return sNode;
		}
	}
	
	/**
	 * 找出最大的关键字
	 * @return
	 */
	public TreeNode getMaxElement(){
		if(root != null){
			TreeNode p = root;
			while(p.right != null){
				p = p.right;
			}
			return p;
		}
		return null;
	}
	
	/**找出最小的关键字
	 * @return
	 */
	public TreeNode getMinElement(){
		if(root != null){
			TreeNode p = root;
			while(p.left != null){
				p = p.left;
			}
			return p;
		}
		return null;
	}
	
	public void inOrderTraverse(){
		if(nodeList != null){
			nodeList.clear();
		}
		if(root != null){
			inOrderTraverse(root);
		}
	}
	private void inOrderTraverse(TreeNode node){
		if(node != null){
			inOrderTraverse(node.left);
			nodeList.add(node);
			inOrderTraverse(node.right);
		}
	}
	
	public void print(){
		System.out.println("**********中序遍历**********");
		for (TreeNode node : nodeList) {
			System.out.print(node.getVlaue() + " ");
		}
		System.out.println();
	}
	
	public int getSize(){
		return getSize(root);
	}
	
	private int getSize(TreeNode node){
		if(node != null){
			return 1 + getSize(node.left) + getSize(node.right);
		}
		return 0;
	}
	
//	public int getInBetween(int a,int b){
//	}
	
	public static void main(String[] args)   
    {  
        try {  
            BinaryTree bst = new BinaryTree();  
            System.out.println("查找树是否为空? " + (bst.isEmpty() ? "是" : "否"));  
            int[] keys = new int[] {15, 6, 18, 3, 7, 13, 20, 2, 9, 4};  
            for (int key: keys) {  
                bst.insert(key);  
            }  
            System.out.println("查找树是否为空? " + (bst.isEmpty() ? "是" : "否"));  
              
            TreeNode minkeyNode = bst.getMinElement();  
            System.out.println("最小关键字: " + minkeyNode.getVlaue());  
              
            TreeNode maxKeyNode = bst.getMaxElement();  
            System.out.println("最大关键字: " + maxKeyNode.getVlaue());  
              
            System.out.println("根结点关键字: " + bst.getRoot().getVlaue());  
            bst.inOrderTraverse(bst.getRoot());
            bst.print();
            
            System.out.println("查找 7 : " + (bst.search(7) != null ? "查找成功!" : "查找失败,不存在该关键字!"));  
            bst.delete(7); 
            bst.inOrderTraverse();
            bst.print();
            System.out.println("查找 7 : " + (bst.search(7) != null ? "查找成功!" : "查找失败,不存在该关键字!"));  
            System.out.println("查找 12 : " + (bst.search(12) != null ? "查找成功!" : "查找失败,不存在该关键字!"));  
            bst.insert(12);  
            System.out.println("查找 12 : " + (bst.search(12) != null ? "查找成功!" : "查找失败,不存在该关键字!")); 
              
            bst.inOrderTraverse();
            bst.print();
              
            bst.insert(16);  
            bst.delete(6);  
            bst.delete(4);  
              
            bst.inOrderTraverse();
            bst.print();
              
        } catch (Exception e) {  
            System.out.println(e.getMessage());  
            e.printStackTrace();  
        }  
    } 
	
}

名企面试100题_15

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
51、放鱼问题 题目:将20条鱼放入10个桶中,每个桶可以放0~10条,总共有多少种方法。 int Function(
又是一年新春到,又是一年跳槽时。年后跳槽的高峰期来临,IT界的骄子们,你,准备好了吗? 点击原文
全球五百强IT名企智力题精选 全球五百强IT名企智力题精选,汇聚了有史以来最完整最详细的思路分析和
2014,名企面试难度排行榜 有些公司面试门槛很高,很多求职的小伙伴倒在了面试途中,一起来看看2014
腾讯2011.10.15校园招聘会笔试题 1、下面的排序算法中,初始数据集的排列顺序对算法的性能无影响的
题目要求:   问题1:编写实现链表排序的一种算法。   问题2:编写实现数组排序的一种算法。
题目要求:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结
题目要求:   给出两个单向链表的头指针,比如h1和h2,判断两个链表是否相交。 题目分析:   1.
题目要求:   输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出
题目要求:   我们把只包含因子2、3和5的数称为丑数。例如6、8都是丑数,但是14不是,因为它包含
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号