java实现二插排序树插入和中序遍历(新增广度优先遍历,加入程序代码注释)

主要使用递归调用的方式实现二叉排序树的插入和遍历。

昨天在HackeRrank刷题时候看到关于二叉树的知识点,今天做了个简单的算法实现。主要使用递归调用的方式实现二叉排序树的插入和遍历。

  • 二叉排序树:二叉树的特殊形式,其节点的的左分叉小于或者等于节点,右侧分叉大于节点数;这样的主要好处是,进行中序遍历的时候,直接可以输出从小到大的排列顺序。(关于二叉树,可以自行去百度搜索)

public class Tree {
 
    Tree treeLeft;
    Tree treeRight;//创建了树的两个分支,声明类型自己本身树,目的是每新建一个分支依旧为树的一个节点
    int data;
 
    Tree(int data){
        this.data = data;//data在这里是树节点(或分支)的值
        treeLeft = treeRight = null;
    }  
}
public class TreeMain {
 
    /**
     * 二叉排序树;左边是小于等于,右边是大于根节点。
     * @param root
     * @param data
     * @return
     */
    public static Tree insert(Tree root, int data) {
 
        if (root == null) {
            return new Tree(data);//新建树节点
        }else {
            Tree cur;
            if (data <= root.data) {//小的放在左侧
                cur = insert(root.treeLeft,data);//递归一直到root为空时,调用第一个IF实现新建树节点
                root.treeLeft = cur;
            }else {//大的放在右侧
                cur = insert(root.treeRight,data);
                root.treeRight = cur;
            }
 
            return root;
        }
 
    }
 
 
    /**
     * 递归法实现中序遍历,并打印
     * @param root
     */
    public static void inOrder(Tree root){
        if(root == null) return;
        inOrder(root.treeLeft);//用递归的方法一直找到树的最左侧
        System.out.print(root.data + " ");
        inOrder(root.treeRight);
    }
 
    /**
     * 对列法实现二叉树广度优先遍历,队列遵循先进先出的规则,适合本方法
     * @param root
     */
    public static void levelOrer(Tree root){
        Queue<Tree> queue = new LinkedList<Tree>();//新增队列
 
        if(root != null){
            queue.add(root);//将根节点加入队列
        }
 
        while (!queue.isEmpty()){
            Tree cur = queue.peek();//创建cur的目的是在while循环的时候逐层将树带入,如果直接用root,会导致只能输出一级树
            System.out.print(cur.data + " ");
            queue.remove();
            if (cur.treeLeft != null){
                queue.add(cur.treeLeft);//先将左分支加入队列,之后先输出
            }
            if(cur.treeRight != null){
                queue.add(cur.treeRight);
            }
        }
 
    }
 
    /**
     * main函数,输入输出,遍历
     * @param args
     */
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数字的个数:");
        int T = sc.nextInt();
        int[] t = new int[T];
        System.out.println("请输入数字,以空格分隔:");
        for (int i = 0; i < T; i++) {
            t[i] = sc.nextInt();
        }
 
        Tree root = null;
        for (int i = 0; i < T; i++) {
            root = insert(root,t[i]);
        }
 
        inOrder(root);
        System.out.println("\n");
        levelOrer(root);
 
    }
}

结果如下:

评论:

1 条评论,访客:0 条,站长:1 条
  1. admin
    admin发布于: 

    写的非常不错,可以记录一下,这个图片得通过媒体上传,不然会失效,很尴尬 网站还很多不足

发表评论