爪哇国新游记之二十四----二叉树

简介:
复制代码
/**
 * 二叉树节点类
 * */
class Node<T extends Comparable> {
  public Node(T data){
    this.data=data;
  }
  
  T data;
  Node<T> left;
  Node<T> right;
}

/**
 * 二叉树类
*/
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);
    }
  }
}
复制代码

 













本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/xiandedanteng/p/3884976.html,如需转载请自行联系原作者



相关文章
|
存储 算法 NoSQL
膜拜!砍下13个大厂Offer神仙案例! | 彭文华
膜拜!砍下13个大厂Offer神仙案例! | 彭文华
|
C语言 C++
《C游记》 第一章 - 灵根孕育源流出 初识C言大道生(贰)
《C游记》 第一章 - 灵根孕育源流出 初识C言大道生(贰)
190 0
《C游记》 第一章 - 灵根孕育源流出 初识C言大道生(贰)
|
算法
​LeetCode刷题实战417:太平洋大西洋水流问题
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
143 0
​LeetCode刷题实战417:太平洋大西洋水流问题
|
算法
算法给小码农链式二叉树-----一根草可斩星辰
链式二叉树 我们需要明白一点,就是普通的二叉树增删查改没有什么价值,因为普通二叉树用来存数据复杂且不方便
96 0
算法给小码农链式二叉树-----一根草可斩星辰