資料結構-二叉搜所樹java實作

package com.data.struct;

/**
 * 二叉搜尋樹
 * @author Administrator
 *
 */
public class BinarySearchTree {
  private Node root;
  public BinarySearchTree(int[]data){
    for(int i=0;i<data.length;i++){
      Node node=new Node();
      node.setValue(data[i]);
      insert(node);
    }
  }
  
  /**
   * 中序周遊
   */
  public void inorderTreeWalk(){
    innerInorderTreeWalk(root);
    System.out.println();
  }
  /**
   * 中序周遊
   */
  private void innerInorderTreeWalk(Node node){
    if(node!=null){
      innerInorderTreeWalk(node.left);
      System.out.print("-->"+node.value);
      innerInorderTreeWalk(node.right);
    }
  }
  /**
   * 先序周遊
   */
  public void preorderWalk(){
    innerPreorderWalk(root);
    System.out.println();
  }
  private void innerPreorderWalk(Node node){
    System.out.print("-->"+node.value);
    innerPreorderWalk(node.left);
    innerPreorderWalk(node.right);
  }
  /**
   * 後續周遊
   */
  public void postorderWalk(){
    innerPostorderWalk(root);
    System.out.println();
  }
  private void innerPostorderWalk(Node node){
    innerPostorderWalk(node.left);
    innerPostorderWalk(node.right);
    System.out.print("-->"+node.value);
  }
  /**
   * 查找值為value的節點
   * @param value
   * @return
   */
  public Node search(int value){
    return innerSearch(root,value);
  }
  private Node innerSearch(Node node,int value){
    if(node==null||node.value==value){
      return node;
    }
    if(node.value>value){
      return innerSearch(node.left,value);
    }else{
      return innerSearch(node.right,value);
    }
  }
  /**
   * 傳回最小值節點
   * @return
   */
  public Node minimum(){
    return innerMinimum(root);
  }
  private Node innerMinimum(Node node){
    if(node.left!=null){
      return innerMinimum(node.left);
    }
    return node;
  }
  /**
   * 傳回最大值節點
   * @return
   */
  public Node maximum(){
    return innerMaximum(root);
  }
  private Node innerMaximum(Node node){
    if(node.right!=null){
      return innerMaximum(node.right);
    }
    return node;
  }
  /**
   * 傳回給定節點的後繼結點
   * @param node
   * @return
   */
  public Node successor(Node node){
    if(node.right!=null){
      return innerMinimum(node.right);
    }
    Node y=node.parent;
    while(y!=null&&y.right==node){
      node=y;
      y=y.parent;
    }
    return y;
  }
  public void insert(int value){
    Node node=new Node();
    node.setValue(value);
    insert(node);
  }
  /**
   * 插入節點
   * @param node
   */
  public void insert(Node node){
    Node y=null;
    Node x=root;
    while(x!=null){
      y=x;
      if(node.value<x.value){
        x=x.left;
      }else{
        x=x.right;
      }
    }
    node.parent=y;
    if(y==null){
      root=node;
    }else if(y.value>node.value){
      y.left=node;
    }else{
      y.right=node;
    }
  }
  
  private void transplant(Node u,Node v){
    if(u.parent==null){
      root=v;
    }else if(u==u.parent.left){
      u.parent.left=v;
    }else{
      u.parent.right=v;
    }
    if(v!=null){
      v.parent=u.parent;
    }
  }
  public void delete(int value){
    delete(search(value));
  }
  /**
   * 删除節點
   * @param node
   */
  public void delete(Node node){
    if(node.left==null){
      transplant(node,node.right);
    }else if(node.right==null){
      transplant(node,node.left);
    }else{
      Node y=innerMinimum(node.right);
      if(y.parent!=node){
        transplant(y,y.right);
        y.right=node.right;
        y.right.parent=y;
      }
      transplant(node,y);
      y.left=node.left;
      y.left.parent=y;
    }
  }
  private static class Node{
    private Node left;
    private Node right;
    private Node parent;
    private int value;
    public Node getLeft() {
      return left;
    }
    public void setLeft(Node left) {
      this.left = left;
    }
    public Node getRight() {
      return right;
    }
    public void setRight(Node right) {
      this.right = right;
    }
    public Node getParent() {
      return parent;
    }
    public void setParent(Node parent) {
      this.parent = parent;
    }
    public int getValue() {
      return value;
    }
    public void setValue(int value) {
      this.value = value;
    }
    
  }
  public static void main(String[] args) {
    int [] data=new int[]{8,3,2,6,3,9,1};
    BinarySearchTree tree=new BinarySearchTree(data);
    tree.inorderTreeWalk();
    tree.insert(5);
    tree.inorderTreeWalk();
    tree.delete(3);
    tree.inorderTreeWalk();

  }

}