二叉排序树java实现
二叉排序树java实现
随风1993 发表于6个月前
二叉排序树java实现
  • 发表于 6个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: 构造二叉排序树,以及二叉树的前中后序遍历

import java.util.Scanner;

/**
 * @author tj
 * 
        题目描述:
        
            有一棵树,输出某一深度的所有节点,有则输出这些节点,无则输出EMPTY。该树是完全二叉树。
        
        输入:
        
            输入有多组数据。
            每组输入一个n(1<=n<=1000),然后将树中的这n个节点依次输入,再输入一个d代表深度。
        
        输出:
        
            输出该树中第d层得所有节点,节点间用空格隔开,最后一个节点后没有空格。
        
        样例输入:
        
            4
            1 2 3 4
            2
       
                      样例输出:

            2 3

 */
public class PerfectTree {
    
    public PerfectTree left;
    public PerfectTree right;
    public int value;
    public int level;
    
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        
        while(cin.hasNext()){
            
            PerfectTree tree = new PerfectTree();
            int n = cin.nextInt();
            
            int[] mar = new int[n];
            for(int i=0;i<n;i++){
                mar[i] = cin.nextInt();
            }
            int k = cin.nextInt();
            
            tree.value = mar[0];
            tree.level = 1;
            tree.createTree(mar,k);
            tree.middleList();
            
        }
    }

    private void createTree(int[] mar,int k) {
        // TODO Auto-generated method stub
        if(mar.length>=this.value*2){
            this.left = new PerfectTree();
            this.left.value = this.value*2;
            this.left.level = this.level+1;
            this.left.createTree(mar,k);
        }
        
        if(mar.length>=(this.value*2)+1){
            this.right = new PerfectTree();
            this.right.value = this.value*2+1;
            this.right.level = this.level+1;
            this.right.createTree(mar,k);
        }
    }
    
    public void prelist(){
        System.out.println(this.value);
        if(this.left != null){
            this.left.prelist();
        }
        
        if(this.right !=null){
            this.right.prelist();
        }
    }
    
    //中序遍历
    public void middleList(){
            if(this.left != null){
                this.left.middleList();
            }
            
            System.out.println(this.value+"| "+this.level);
            
            if(this.right !=null){
                this.right.middleList();
            }
    }
    //后序遍历
    public void afterList(){
            
            if(this.left != null){
                this.left.afterList();
            }
            
            if(this.right !=null){
                this.right.afterList();
            }
            
            System.out.println(this.value);
        }

}
 

共有 人打赏支持
粉丝 0
博文 9
码字总数 2110
×
随风1993
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: