Java实现二叉树的建立、计算高度与递归输出操作示例

小蚂蚁

这篇文章主要介绍了Java实现二叉树的建立、计算高度与递归输出操作,结合实例形式分析了Java二叉树的创建、遍历、计算等相关算法实现技巧,需要的朋友可以参考下
本文实例讲述了java实现二叉树的建立、计算高度与递归输出操作。分享给大家供大家参考，具体如下：
1. 建立 递归输出 计算高度 前中后三种非递归输出

public class tree_link {
  private int save = 0;
  private int now = 0;
  scanner sc = new scanner(system.in);
  /*
   * 构造函数
   */
  tree_link(){
  }
  /*
   * 链表建立
   */
  public tree link_build(tree head){
//    tree head = new tree();//头节点
    system.out.println("继续code：1");
    int flag = sc.nextint();
    if(flag != 1){
      return head;
    }else{
      system.out.println("\n\n\n输入 节点信息：");
      head.setcode(sc.nextint());
      system.out.println("\n建立 左 子树code：1  否则：0");
      flag = sc.nextint();
      if(flag == 1){
        now++;
        tree ltree = new tree();
        head.setltree(ltree);  
        ltree.setfronttree(head);//设置父母节点
        link_build( head.getltree() );
      }
      system.out.println("\n当前位置：" + head.getcode());
      system.out.println("\n建立 右 子树code：1  否则：0");
      flag = sc.nextint();
      if(flag == 1){
        now++;
        tree rtree = new tree();
        head.setrtree(rtree);
        rtree.setfronttree(head);//设置父母节点
        link_build( head.getrtree() );
      }
      if( now > save ){
        save = now;
      }
      now--;
    }
    return head;
  }
  /*
   * 输出树
   */
  public tree output(tree head){
    int flag;
    if(head.getcode() == -1){
      return head;
    }else{
      system.out.println("\n当前位置：" + head.getcode());
      system.out.println(head.getltree() != null);
      if(head.getltree() != null){
        system.out.println("\n访问 左子树:");
        output( head.getltree() );
      }
      if(head.getrtree() != null){
        system.out.println("\n访问 右子树:");
        output( head.getrtree() );
      }
    }
    return head;
  }
  /*
   * 获得高度
   */
  public int getsave(){
    return this.save;
  }
  /*
   * 非递归 前序遍历
   */
  public void front_traverse(tree head){
    tree star = head;//退出标记
    int choose = 1; //左
    int flag = 1;  //右
    system.out.println( "<---前序遍历--->" + head.getcode() );//先访问根
    while(true){
      if( head.getltree() != null && choose != 0 ){
        head = head.getltree();
        system.out.println( "<---前序遍历--->" + head.getcode() );//获得信息
        flag = 1;
      }else if( head.getrtree() != null && flag != 0 ){
        head = head.getrtree();
        system.out.println( "<---前序遍历--->" + head.getcode() );
        choose = 1;
      }else if( flag == 0 && choose == 0 && head == star){
        break;
      }else{
        if(head == head.getfronttree().getrtree()){
          flag = 0;
          choose = 0;
        }
        if(head == head.getfronttree().getltree()){
          choose = 0;
          flag = 1;
        }
        head = head.getfronttree();
        system.out.println("获得 父母" + head.getcode());
        system.out.println( "\n\n\n" );
      }
    }
  }
  /*
   * 非递归 中序遍历
   */
  public void center_traverse(tree head){
    tree star = head;//退出标记
    int choose = 1; //左
    int flag = 1;  //右
    while(true){
      if( head.getltree() != null && choose != 0 ){
        head = head.getltree();
        flag = 1;
      }else if( head.getrtree() != null && flag != 0 ){
        if(head.getltree() == null){//因为左边为空而返回
          system.out.println( "<-1--中序遍历--->" + head.getcode());
        }
        head = head.getrtree();
        choose = 1;
      }else if( flag == 0 && choose == 0 && head == star){
        break;
      }else{
        int area = 0;//判断哪边回来
        flag = 1;
        choose = 1;
        if(head == head.getfronttree().getrtree()){
          area = 1;//右边回来
          flag = 0;
          choose = 0;
        }
        if(head == head.getfronttree().getltree()){
          area = 2;//左边回来
          choose = 0;
          flag = 1;
        }
        if( head.getltree() == null && head.getrtree() == null ){//因为左边为空而返回
          system.out.println( "<-2--中序遍历--->" + head.getcode());
        }
        head = head.getfronttree();
        if( area == 2){//因为左边访问完返回
          system.out.println( "<-3--中序遍历--->" + head.getcode());
        }
        system.out.println("获得 父母" + head.getcode());
        system.out.println( "\n\n\n" );
      }
    }
  }
  /*
   * 非递归 后续遍历
   */
  public void bottom_traverse(tree head){
    tree star = head;//退出标记
    int choose = 1; //左
    int flag = 1;  //右
    while(true){
      if( head.getltree() != null && choose != 0 ){
        head = head.getltree();
        flag = 1;
      }else if( head.getrtree() != null && flag != 0 ){
        head = head.getrtree();
        choose = 1;
      }else if( flag == 0 && choose == 0 && head == star){
        break;
      }else{
        int area = 0;//判断哪边回来
        flag = 1;
        choose = 1;
        if(head == head.getfronttree().getrtree()){
          area = 1;//右边回来
          flag = 0;
          choose = 0;
        }
        if(head == head.getfronttree().getltree()){
          choose = 0;
          flag = 1;
        }
        if(head.getrtree() == null){//因为右边为空而返回
          system.out.println( "<-1--后序遍历--->" + head.getcode());
        }
        head = head.getfronttree();
        if( area == 1){
          system.out.println( "<-2--后序遍历--->" + head.getcode());
        }
        system.out.println("获得 父母" + head.getcode());
        system.out.println( "\n\n\n" );
      }
    }
  }
}

2. tree 类实现：

public class tree {
  private int code = -1;
  private tree fonttree;
  private tree ltree;
  private tree rtree;
  tree(){
    this.code = -1;
    this.ltree = null;
    this.rtree = null;
  }
  /*
   * 树内容查看方法：
   */
  public void setcode(int code){//设置编号
    this.code = code;
  }
  public int getcode(){   //获取编号
    return this.code;
  }
  /*
   * 设置父母指针：
   */
  public void setfronttree(tree front){
    this.fonttree = front;
  }
  public tree getfronttree(){
    system.out.println("获得 父母");
    return this.fonttree;
  }
  /*
   * 设置左子女：
   */
  public void setltree(tree ltree){
    this.ltree = ltree;
  }
  public tree getltree(){
    system.out.println("获得左子树");
    return this.ltree;
  }
  /*
   * 设置右子女：
   */
  public void setrtree(tree rtree){
    this.rtree = rtree;
  }
  public tree getrtree(){
    system.out.println("获得右子树");
    return this.rtree;
  }
}

3. 主函数测试：

public class mainactivity {
  scanner sc = new scanner(system.in);
  public static void main(string[] args) {
    tree head = new tree();
    tree_link link_1st = new tree_link();
    head = link_1st.link_build(head);
    system.out.println("build succeed !");
    system.out.println("\n二叉树高度-->" + link_1st.getsave());
    link_1st.output(head);
    system.out.println("output over  !");
    system.out.println("\n\n<----------------前------------------>\n前序访问根：");
    link_1st.front_traverse(head);
    system.out.println("\n\n<----------------中------------------>\n中序访问根：");
    link_1st.center_traverse(head);
    system.out.println("\n\n<----------------后------------------>\n后序访问根：");
    link_1st.bottom_traverse(head);
    system.out.println("\n\n\n\ntext over !\n\n\n");
  }
}

希望本文所述对大家java程序设计有所帮助。
原文链接：https://blog.csdn.net/qq_43377749/article/details/83475907