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("nnn输入 节点信息：");
     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( "nnn" );
     }
 }
    }
    
    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( "nnn" );
     }
 }
    }
    
    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( "nnn" );
     }
 }
    }
}

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("nn<----------------前------------------>n前序访问根：");
 link_1st.Front_Traverse(head);
 System.out.println("nn<----------------中------------------>n中序访问根：");
 link_1st.Center_Traverse(head);
 System.out.println("nn<----------------后------------------>n后序访问根：");
 link_1st.Bottom_Traverse(head);
 System.out.println("nnnnText over !nnn");
    }
}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。