黑马程序员技术交流社区

标题: 二叉查找树 [打印本页]
作者: Lemen    时间: 2015-8-22 22:24
标题: 二叉查找树
用的是先序遍历
  1. package com.bst;

  3. public class TreeNode<E extends Number> {//节点
  4.         private E element; //root
  5.         private TreeNode<E> left;
  6.         private TreeNode<E> right;
  7.        
  8.         public TreeNode(E e){
  9.                 element=e;
  10.         }
  11.         public TreeNode(){}
  12.        

  14.         public boolean insert(E e){
  15.                 //如果tree为空，则给root赋值
  16.                 if(this.element==null){
  17.                         this.setElement(e);
  18.                         return true;
  19.                 }
  20.                
  21.                 TreeNode<E> current=this;
  22.                 //parent 在插入e时会用到
  23.                 TreeNode<E> parent=this;
  24.                 while(current!=null)
  25.                 {
  26.                         //判断与root元素大小
  27.                         if(e.floatValue()<current.element.floatValue())
  28.                         {
  29.                                 parent=current;
  30.                                 current=current.left; //Go ledt 进入左子树！下同
  31.                         }else if(e.floatValue()>current.element.floatValue())
  32.                         {
  33.                                 parent=current;
  34.                                 current=current.right;
  35.                         }else
  36.                                 return false;
  37.                 }
  38.                 //current=new TreeNode<E>(e) 给current指向，但不是其节点的子树所指。所以一直用parent
  39.                 if(e.floatValue()<parent.element.floatValue())
  40.                         parent.left=new TreeNode<E>(e);
  41.                 else
  42.                         parent.right=new TreeNode<E>(e);
  43.                 return true;
  44.         }
  45.         public boolean search(E e){
  46.                 TreeNode<E> current=this;
  47.                 while(current!=null){
  48.                         if(e.floatValue()<current.element.floatValue())
  49.                                 current=current.left;
  50.                         else if(e.floatValue()>current.element.floatValue())
  51.                                 current=current.right;
  52.                         else
  53.                                 return true;
  54.                 }
  55.                 return false;
  56.         }
  57.         public void print(){
  58.                 if(left!=null)
  59.                         left.print();
  60.                         System.out.print(element+" ");
  61.                 if(right!=null){
  62.                         right.print();
  63.                 }
  64.         }
  65.        
  66.        
  67.         public E getElement() {
  68.                 return element;
  69.         }
  70.         public void setElement(E element) {
  71.                 this.element = element;
  72.         }
  73.         public TreeNode<E> getLeft() {
  74.                 return left;
  75.         }
  76.         public void setLeft(TreeNode<E> left) {
  77.                 this.left = left;
  78.         }
  79.         public TreeNode<E> getRight() {
  80.                 return right;
  81.         }
  82.         public void setRight(TreeNode<E> right) {
  83.                 this.right = right;
  84.         }
  85.        
  86.        
  87.         public static void main(String[] args) {
  88.                 TreeNode<Integer> integer =new TreeNode<Integer>();
  89.                 Integer[] intes={9,6,20,8,5,16,23};
  90.                 for(Integer i:intes)
  91.                         integer.insert(i);
  92.                 //System.out.println(integer.search(9));
  93.                 integer.print();
  94.         }

  96. }
复制代码


作者: 张兵    时间: 2015-8-23 21:32
赞赞！！！！！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2