- 浏览: 32294 次
- 性别:
- 来自: 北京
文章分类
最新评论
第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(); } } }
相关推荐
100IT名企java面试必考面试题 你不清楚的18个非技术面试题是这些
想要进入IT公司,面试笔试题是一定要有所准备的。那么这里我们总结了一些名企笔试题
100家IT名企笔试面试题 百度笔试题,中兴笔试题,腾讯笔试题,华为笔试题,联想笔试题
第1章 计算机语基础51.1 在C++ 程序中调被C 编译器编译后的函数,为什么要加extern“C”?51.2 什么是多线程,多线程与多任务有什么区别?81.
该文本汇总了常见C++面试中遇到的各种坑,涵盖基础知识比较全面
100IT名企java面试真题整理面试必考点(高清修正版)
C语言面试题总汇(名企面试题总汇),完整,全面,含答案
这些面试试题是各个名企的面试题哦,都有详细的分析,非常棒的,如果你正在找工作,千万不要错过这套试题哦~~~
中外名企面试笔试智力题,IBM社会招聘笔试题 ,Intel笔试面试题目,微软公司的面试问题,广州本田汽车有限公司笔试题,某著名高科技骨干企业的面试试题
linux名企面试题曝光
牛客网_2018名企校招笔试真题精选技术篇,有价值的资料
名企(华为_阿卡_TCL_索尼_微软_百度_大唐)笔试面试题,C居多含C++及数据结构等等。
适宜阅读人群 需要面试的初/中/高级 java 程序员 想要查漏补缺的人 想要不断完善和扩充自己 java 技术栈的人 java 面试官 具体面试题
名企面试笔试真题:TI 笔试题
100IT名企java面试必考面试题.PDF
数据结构和算法名企面试题目,里面的test是其中一道的解答
名企片爬虫面试题.pdf_python面试
其他互联网名企面试笔试题.rar
互联网名企的笔试部分的题目。。。。。。大家想去的话,可以参考一下
名企面试题,包括华为、微软、大唐等企业。是面试者最佳的选择