欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 二叉查找树实例代码

程序员文章站 2024-03-04 20:01:12
java 二叉查找树实例代码 1.左边<中间<右边 2.前序遍历 左中右 3.中序遍历 中左右 4.后序遍历 左右中 public class...

java 二叉查找树实例代码

1.左边<中间<右边

2.前序遍历 左中右

3.中序遍历 中左右

4.后序遍历 左右中

public class binarytree {

  // 二叉树的根节点
  public treenode rootnode ;
  // 记录搜索深度
  public int count;

  /**
   * 利用传入一个数组来建立二叉树
   */
  public binarytree(int[] data) {
    for (int i = 0; i < data. length; i++) {
      addnodetotree(data[i]);
    }
  }

  /**
   * 将指定的值加入到二叉树中适当的节点
   */
  private void addnodetotree(int value) {
    treenode currentnode = rootnode;
    // 建立树根
    if (rootnode == null) {
      rootnode = new treenode(value);
      return;
    }

    // 建立二叉树
    while (true) {
      // 新增的value比节点的value小,则在左子树
      if (value < currentnode.value ) {
        if (currentnode.leftnode == null) {
          currentnode.leftnode = new treenode(value);
          return;
        } else {
          currentnode = currentnode.leftnode;
        }
      } else { // 新增的value比节点的value大,在右子树
        if (currentnode.rightnode == null) {
          currentnode. rightnode = new treenode(value);
          return;
        } else {
          currentnode = currentnode. rightnode;
        }
      }
    }
  }

  /**
   * 中序遍历(左子树 -树根- 右子树)
   */
  public void inorder(treenode node) {
    if (node != null) {
      inorder(node. leftnode);
      system. out.print("[" + node.value + "]");
      inorder(node. rightnode);
    }
  }

  /**
   * 前序遍历(树根 -左子树- 右子树)
   */
  public void preorder(treenode node) {
    if (node != null) {
      system. out.print("[" + node.value + "]");
      preorder(node. leftnode);
      preorder(node. rightnode);
    }
  }

  /**
   * 后序遍历(左子树 -右子树- 树根)
   */
  public void postorder(treenode node) {
    if (node != null) {
      postorder(node. leftnode);
      postorder(node. rightnode);
      system. out.print("[" + node.value + "]");
    }
  }

  /**
   * 从二叉树中查找指定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);
    }
  }

  /**
   * 利用中序遍历进行排序
   */
  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开始搜索:" );
    boolean isfind = tree.findtree(tree.rootnode, 48);
    system. out.println("是否搜索到" + 48 + ":" + isfind);

    system. out.println("\n进行排序:" );
    tree.sort();
  }
}

前序遍历:

[50][35][27][45][40][48][78][56][90]

中序遍历:

[27][35][40][45][48][50][56][78][90]

后序遍历:

[27][40][48][45][35][56][90][78][50]

开始搜索:

共搜索3次

是否搜索到48:true

进行排序:

[27][35][40][45][48][50][56][78][90]

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!