春风博客

春天里，百花香...

导航

<2008年10月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

二叉树搜索树代码

/**
 * 二叉树节点类
 * @author HEYANG
 * @since 2008-7-26 下午02:59:06
 */
class Node<T extends Comparable> {
  public Node(T data){
    this.data=data;
  }
  
  T data;
  Node<T> left;
  Node<T> right;
}

/**
 * 二叉树类
 * @author HEYANG
 * @since 2008-7-26 下午02:55:33
 */
public class BinaryTree<T extends Comparable> {

  /**
   * 根節點
   */
  private Node<T> root;

  /**
   * 插入一個值
   * @param value
   */
  public void insert(T value) {
    Node<T> node = new Node<T>(value);

    if (root == null) {
      root = node;
    } else {
      Node<T> curr = root;
      Node<T> parrent;

      while (true) {
        parrent = curr;

        if (value.compareTo(curr.data) >= 0) {
          curr = curr.right;

          if (curr == null) {
            parrent.right=node;
            return;
          }
        } else {
          curr = curr.left;

          if (curr == null) {
            parrent.left=node;
            return;
          }
        }
      }
    }
  }

  /**
   * 尋找一個值對應的節點
   * @param value
   * @return
   */
  public Node<T> find(T value) {
    Node<T> curr = root;

    while (curr.data.equals(value) == false) {
      if (value.compareTo(curr.data) > 0) {
        curr = curr.right;
      } else {
        curr = curr.left;
      }

      if (curr == null) {
        return null;
      }
    }

    return curr;
  }

  /**
   * 輸出
   *
   */
  public void printAll() {
    System.out.println("--------------先序遍历------------------");
    preOrder(root);
    System.out.println("--------------中序遍历------------------");
    inorder(root);
    System.out.println("--------------后序遍历------------------");
    postOrder(root);
  }
  
  /**
   * 先序遍歷
   * @param node
   */
  private void preOrder(Node<T> node) {
    if (node != null) {
      System.out.println(node.data);
      preOrder(node.left);      
      preOrder(node.right);
    }
  }

  /**
   * 中序遍歷
   * @param node
   */
  private void inorder(Node<T> node) {
    if (node != null) {
      inorder(node.left);
      System.out.println(node.data);
      inorder(node.right);
    }
  }
  
  /**
   * 后序遍歷
   * @param node
   */
  private void postOrder(Node<T> node) {
    if (node != null) {
      postOrder(node.left);     
      postOrder(node.right);
      System.out.println(node.data);
    }
  }

  public static void main(String[] args) {
    
    Integer[] arr={31,25,47,42,50};
    
    // 以數組2為基礎創建二叉樹
    BinaryTree<Integer> tree1=new BinaryTree<Integer>();   
    for(Integer i:arr){
      tree1.insert(i);
    }
    
    tree1.printAll();
    
    
    String[] arr02={"Ceaser","Andy","Martin","Bill","Felex","Fowler","Green","Alice","Gates"};
    
    // 以數組2為基礎創建二叉樹
    BinaryTree<String> tree=new BinaryTree<String>();   
    for(String str:arr02){
      tree.insert(str);
    }
    
    tree.printAll();
    
    // 將在二叉樹中不存在的元素放入鏈錶
    String[] arr01={"Andy","Bill","Cindy","Douglas","Felex","Green"};
    List<String> ls=new ArrayList<String>();    
    for(String str:arr01){
      if(tree.find(str)==null){
        ls.add(str);
      }
    }
    
    // 輸出
    System.out.println("--------------二叉樹中不存在的元素有------");
    for(String str:ls){
      System.out.println(str);
    }
  }
}

posted on 2008-07-26 16:25 sitinspring 阅读(1174) 评论(1)  编辑  收藏 所属分类: 算法数据结构

评论

# re: 二叉树搜索树代码 2008-10-04 08:34 sclsch

老兄，二叉树有没有实际应用的实例。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.