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算法相关内容感兴趣的读者可查看本站专题：《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》

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