现在的位置: 首页 > 综合 > 正文

Binary Search Tree

2013年12月19日 ⁄ 综合 ⁄ 共 4963字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  1. /**
  2.  * filename: BinarySearchTree.java
  3.  * package: 
  4.  * author: Nick Ma
  5.  * email: nick.ma85@yahoo.com
  6.  * date: Nov 12, 2008
  7.  * description: this class implements an unbalanced binary search tree.
  8.  */
  10. public
     
    class
     BinarySearchTree<T 
    extends
     Comparable<T>> 
    extends
     BinaryTree<T>{
  11.     
  12.     
    // Data Field
  13.     
  14.     
    /** the deleted node */
  15.     
    protected
     BinaryNode<T> deletedNode = 
    null
    ;
  16.     
  17.     
    /**
  18.      * description: search the node with the given data
  19.      * @param target - the data stored in the node
  20.      * @return - the found node
  21.      */
  22.     
    public
     BinaryNode<T> search(T target) {
  23.         
    return
     find(
    this
    .root, target);
  24.     }
  26.     
    /**
  27.      * description: recursive find method
  28.      * @param node - the root of the subtree
  29.      * @param target - the target being sought
  30.      * @return - the node, if found, otherwise, return null
  31.      */
  32.     
    public
     BinaryNode<T> find(BinaryNode<T> node, T target) {
  33.         
    if
    (node == 
    null
    ) {
  34.             
    return
     
    null
    ;
  35.         } 
    else
     {
  36.             
    int
     result = target.compareTo(node.getData());
  37.             
  38.             
    if
    (result < 
    0
    ) {
  39.                 
    // target is less than the data in the local root
  40.                 
    return
     find(node.getLeft(), target);
  41.             } 
    else
     
    if
    (result > 
    0
    ) {
  42.                 
    // target is greater than the data in the local root
  43.                 
    return
     find(node.getRight(), target);
  44.             } 
    else
     {
  45.                 
    // target is equal to the data in the local root
  46.                 
    return
     node;
  47.             }
  48.         }
  49.     }
  50.     
  51.     
    /**
  52.      * description: add new node in the tree
  53.      * @param newNode - the new node
  54.      */
  55.     
    public
     
    void
     add(BinaryNode<T> newNode) {
  56.         
    this
    .root = addAux(
    this
    .root, newNode);
  57.     }
  58.     
  59.     
    /**
  60.      * description: recursive add-auxiliary method
  61.      * @param node - the local root
  62.      * @param newNode - the new node
  63.      * @return - the new local root which contains the new node
  64.      */
  65.     
    private
     BinaryNode<T> addAux(BinaryNode<T> node, BinaryNode<T> newNode) {
  66.         
    if
    (node == 
    null
    ) {
  67.             
    // the tree is empty
  68.             
    return
     newNode;
  69.         } 
    else
     {
  70.             
    int
     result = newNode.getData().compareTo(node.getData());
  71.             
  72.             
    if
    (result < 
    0
    ) {
  73.                 
    // insert new node in the left subtree
  74.                 node.setLeft(addAux(node.getLeft(), newNode));
  75.             } 
    else
     
    if
     (result > 
    0
    ){
  76.                 
    // insert new node in the right subtree
  77.                 node.setRight(addAux(node.getRight(), newNode));
  78.             }
  79.             
    return
     node;
  80.         }
  81.     }
  82.     
  83.     
    /**
  84.      * description: delete the node in the tree
  85.      * @param data - the data of the deleted node
  86.      * @return - the deleted node
  87.      */
  88.     
    public
     BinaryNode<T> delete(T data) {
  89.         
    this
    .root = 
    this
    .deleteAux(
    this
    .root, data);
  90.         
    return
     
    this
    .deletedNode;
  91.     }
  92.     
  93.     
    /**
  94.      * description: recursive delete-auxiliary method
  95.      * @param node - the local root
  96.      * @param target - the data of the deleted node
  97.      * @return - the new local root which deletes the target node
  98.      */
  99.     
    private
     BinaryNode<T> deleteAux(BinaryNode<T> node, T target) {
  100.         
    if
    (node == 
    null
    ) {
  101.             
    // the tree is empty
  102.             
    return
     
    null
    ;
  103.         } 
    else
     {
  104.             
    int
     result = target.compareTo(node.getData());
  105.             
  106.             
    if
    (result < 
    0
    ) {
  107.                 
    // target is less than the data in the local root
  108.                 node.setLeft(deleteAux(node.getLeft(), target));
  109.                 
    return
     node;
  110.             } 
    else
     
    if
     (result > 
    0
    ){
  111.                 
    // target is greater than the data in the local root
  112.                 node.setRight(deleteAux(node.getRight(), target));
  113.                 
    return
     node;
  114.             } 
    else
     {
  115.                 
    // target is equal to the data in the local root
  116.                 
  117.                 deletedNode = node;
  118.         
  119.                 
    if
    (node.getLeft() == 
    null
    ) {
  120.                     
    // there's no left child in the local root
  121.                     
    return
     node.getRight();
  122.                 } 
    else
     
    if
    (node.getRight() == 
    null
    ) {
  123.                     
    // there's no right child in the local root
  124.                     
    return
     node.getLeft();
  125.                 } 
    else
     {
  126.                     
    // the local root has two children
  127.                     
    if
    (node.getLeft().getRight() == 
    null
    ) {
  128.                         node.setData(node.getLeft().getData());
  129.                         node.setLeft(node.getLeft().getLeft());
  130.                         
    return
     node;
  131.                     } 
    else
     {
  132.                         node.setData(
    this
    .findLargestChild(node.getLeft()));
  133.                         
    return
     node;
  134.                     }
  135.                 }
  136.             }
  137.         }
  138.     }
  139.     
  140.     
    /**
  141.      * description: find the largest child of the tree
  142.      * @param node - the local root
  143.      * @return - the data in the largest node
  144.      */
  145.     
    protected
     T findLargestChild(BinaryNode<T> node) {
  146.         
    if
    (node == 
    null
    ) {
  147.             
    return
     
    null
    ;
  148.         } 
    else
     
    if
    (node.getRight() == 
    null
    ) {
  149.             
    return
     node.getData();
  150.         } 
    else
     {
  151.             
    // in-order
  152.             
    return
     findLargestChild(node.getRight());
  153.         }
  154.     }
  155. }
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞