找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ 算法面试题 ] [守望者 java算法]说说生活中遇到的二叉树,用java实现二叉树

2014-09-22 17:14| 发布者: zhouy | 查看: 1075 | 收藏


你有新的观点?  

已有3参与讨论

  • 这是组合设计模式。
    我有很多个(假设10万个)数据要保存起来,以后还需要从保存的这些数据中检索是否存在某个数据,(我想说出二叉树的好处,该怎么说呢?那就是说别人的缺点),假如存在数组中,那么,碰巧要找的数字位于99999那个地方,那查找的速度将很慢,因为要从第1个依次往后取,取出来后进行比较。平衡二叉树(构建平衡二叉树需要先排序,我们这里就不作考虑了)可以很好地解决这个问题,但二叉树的遍历(前序,中序,后序)效率要比数组低很多,原理如下图:
    代码如下:
    package com.huawei.interview;

    publicclass Node {
        public int value;
        public Node left;
        public Node right;
       
        public void store(intvalue)
        {
           if(value<this.value)
           {
               if(left ==null)
               {
                  left = new Node();
                  left.value=value;
               }
               else
               {
                  left.store(value);
               }
           }
           else if(value>this.value)
           {
               if(right ==null)
               {
                  right = new Node();
                  right.value=value;
               }
               else
               {
                  right.store(value);
               }         
           }
        }
       
        public boolean find(intvalue)
        {  
           System.out.println(&quot;happen&quot; +this.value);
           if(value ==this.value)
           {
               return true;
           }
           else if(value>this.value)
           {
               if(right ==null)returnfalse;
               return right.find(value);
           }else
           {
               if(left ==null)returnfalse;
               return left.find(value);
           }

        }
       
        public  void preList()
        {
           System.out.print(this.value+ &quot;,&quot;);
           if(left!=null)left.preList();
           if(right!=null) right.preList();
        }
       
        public void middleList()
        {
           if(left!=null)left.preList();
           System.out.print(this.value+ &quot;,&quot;);
           if(right!=null)right.preList();      
        }
        public void afterList()
        {
           if(left!=null)left.preList();
           if(right!=null)right.preList();
           System.out.print(this.value+ &quot;,&quot;);      
        }  
        public static voidmain(String [] args)
        {
           int [] data =new int[20];
           for(inti=0;i<data.length;i++)
           {
               data = (int)(Math.random()*100)+ 1;
               System.out.print(data +&quot;,&quot;);
           }
           System.out.println();
          
           Node root = new Node();
           root.value = data[0];
           for(inti=1;i<data.length;i++)
           {
               root.store(data);
           }
          
           root.find(data[19]);
          
           root.preList();
           System.out.println();
           root.middleList();
           System.out.println();      
           root.afterList();
        }
    }
    -----------------又一次临场写的代码---------------------------
    importjava.util.Arrays;
    importjava.util.Iterator;

    public class Node{
        private Node left;
        private Node right;
        private int value;
        //private int num;
       
        public Node(int value){
           this.value = value;
        }
        public void add(int value){
          
           if(value > this.value)
           {
               if(right != null)
                  right.add(value);
               else
               {
                  Node node = new Node(value);            
                  right = node;
               }
           }
           else{
               if(left != null)
                  left.add(value);
               else
               {
                  Node node = new Node(value);            
                  left = node;
               }         
           }
        }
       
        public boolean find(int value){
           if(value == this.value) return true;
           else if(value > this.value){
               if(right == null) return false;
               else return right.find(value);
           }else{
               if(left == null) return false;
               else return left.find(value);         
           }

        }
       
        public void display(){
           System.out.println(value);
           if(left != null) left.display();
           if(right != null) right.display();
          
        }
       
        /*public Iterator iterator(){
          
        }*/
       
        public static void main(String[] args){
           int[] values = new int[8];
           for(int i=0;i<8;i++){
               int num = (int)(Math.random() * 15);
               //System.out.println(num);
               //if(Arrays.binarySearch(values,num)<0)
               if(!contains(values,num))
                  values = num;
               else
                  i--;
           }
          
           System.out.println(Arrays.toString(values));
          
           Node root = new Node(values[0]);
           for(int i=1;i<values.length;i++){
               root.add(values);
           }
          
           System.out.println(root.find(13));
          
           root.display();
          
        }
       
        public static boolean contains(int [] arr,int value){
           int i = 0;
           for(;i<arr.length;i++){
               if(arr == value) return true;
             
           }
           return false;
        }
       
    }
    watchmen

    2014-09-22 19:51
  • 生活中太多二叉树了!
    costan

    2014-09-23 11:13

赞过此文的人

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包