java 二叉查找樹(shù)實(shí)例代碼

更新時(shí)間：2017年03月20日 11:50:10 投稿：lqh

這篇文章主要介紹了java 二叉查找樹(shù)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下

java 二叉查找樹(shù)實(shí)例代碼

1.左邊<中間<右邊

2.前序遍歷左中右

3.中序遍歷中左右

4.后序遍歷左右中

public class BinaryTree {

  // 二叉樹(shù)的根節(jié)點(diǎn)
  public TreeNode rootNode ;
  // 記錄搜索深度
  public int count;

  /**
   * 利用傳入一個(gè)數(shù)組來(lái)建立二叉樹(shù)
   */
  public BinaryTree(int[] data) {
    for (int i = 0; i < data. length; i++) {
      addNodeToTree(data[i]);
    }
  }

  /**
   * 將指定的值加入到二叉樹(shù)中適當(dāng)?shù)墓?jié)點(diǎn)
   */
  private void addNodeToTree(int value) {
    TreeNode currentNode = rootNode;
    // 建立樹(shù)根
    if (rootNode == null) {
      rootNode = new TreeNode(value);
      return;
    }

    // 建立二叉樹(shù)
    while (true) {
      // 新增的value比節(jié)點(diǎn)的value小，則在左子樹(shù)
      if (value < currentNode.value ) {
        if (currentNode.leftNode == null) {
          currentNode.leftNode = new TreeNode(value);
          return;
        } else {
          currentNode = currentNode.leftNode;
        }
      } else { // 新增的value比節(jié)點(diǎn)的value大，在右子樹(shù)
        if (currentNode.rightNode == null) {
          currentNode. rightNode = new TreeNode(value);
          return;
        } else {
          currentNode = currentNode. rightNode;
        }
      }
    }
  }

  /**
   * 中序遍歷(左子樹(shù) -樹(shù)根- 右子樹(shù))
   */
  public void inOrder(TreeNode node) {
    if (node != null) {
      inOrder(node. leftNode);
      System. out.print("[" + node.value + "]");
      inOrder(node. rightNode);
    }
  }

  /**
   * 前序遍歷(樹(shù)根 -左子樹(shù)- 右子樹(shù))
   */
  public void preOrder(TreeNode node) {
    if (node != null) {
      System. out.print("[" + node.value + "]");
      preOrder(node. leftNode);
      preOrder(node. rightNode);
    }
  }

  /**
   * 后序遍歷(左子樹(shù) -右子樹(shù)- 樹(shù)根)
   */
  public void postOrder(TreeNode node) {
    if (node != null) {
      postOrder(node. leftNode);
      postOrder(node. rightNode);
      System. out.print("[" + node.value + "]");
    }
  }

  /**
   * 從二叉樹(shù)中查找指定value
   */
  public boolean findTree(TreeNode node, int value) {
    if (node == null) {
      System. out.println("共搜索" + count + "次");
      return false;
    } else if (node.value == value) {
      System. out.println("共搜索" + count + "次");
      return true;
    } else if (value < node.value) {
      count++;
      return findTree(node.leftNode , value);
    } else {
      count++;
      return findTree(node.rightNode , value);
    }
  }

  /**
   * 利用中序遍歷進(jìn)行排序
   */
  public void sort() {
    this.inOrder(rootNode );
  }

  class TreeNode {
    int value ;
    TreeNode leftNode;
    TreeNode rightNode;

    public TreeNode(int value) {
      this.value = value;
      this.leftNode = null;
      this.rightNode = null;
    }
  }

  public static void main(String[] args) {
    int[] content = { 50, 35, 27, 45, 40, 48, 78, 56, 90 };

    BinaryTree tree = new BinaryTree(content);
    System. out.println("前序遍歷:" );
    tree.preOrder(tree. rootNode);
    System. out.println("\n中序遍歷:" );
    tree.inOrder(tree. rootNode);
    System. out.println("\n后序遍歷:" );
    tree.postOrder(tree. rootNode);

    System. out.println("\n\n開(kāi)始搜索:" );
    boolean isFind = tree.findTree(tree.rootNode, 48);
    System. out.println("是否搜索到" + 48 + ":" + isFind);

    System. out.println("\n進(jìn)行排序:" );
    tree.sort();
  }
}

前序遍歷: