2020软件工程作业04

一、第一题:寻找数组中第K大是数，考察算法：排序算法

　　解题思路：控制台录入序列相关信息数据，再声明一个等长的新序列接受、处理，然后根据询问次数，利用选择排序遍历找到K位，进行存储输出。　　　

package com.study;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner  sc =new Scanner(System.in);

        int length;
        System.out.print("请输入序列长度：");
        length =sc.nextInt();

        int [] xulie = new int[length];
        System.out.print("请输入给定的序列：");
        for (int i = 0; i < length; i++) {
            xulie[i]=sc.nextInt();
        }

        System.out.print("请输入询问个数：");
        int num =sc.nextInt();

        int l,r,k;
        int []anser =new int[num];
        for (int j = 0; j < num; j++) {
            System.out.print("请输入l r k:");
            l =sc.nextInt();
            r=sc.nextInt();
            k=sc.nextInt();
            int[] xulie2 =Arrays.copyOfRange(xulie, l-1, r);
            for (int i = 0; i < xulie2.length-1; i++) {
                for (int a = 0; a < xulie2.length-1-i; a++) {
                    if (xulie2[a]>xulie2[a+1]) {
                        int temp =xulie2[a];
                        xulie2[a]=xulie2[a+1];
                        xulie2[a+1]=temp;
                    }
                }
                anser[j]=xulie2[xulie2.length-k];
            }
        }
        System.out.println("结果输出:");
        for (int i : anser) {
            System.out.println(i);
        }


    }


}

二、第二题

　　1.题目名称：二叉树的先、中、后 序遍历与层级遍历
　　2.解题思路：
　　先序遍历：对于先序遍历，我们先输出节点的值，再递归遍历左右子树。中序和后序的递归类似，改变根节点输出位置就可以了。
　　中序遍历：对于中序遍历，我们先遍历左子数，然后输出节点值，再遍历右子树。
　　后序遍历：对于后序遍历，我们先遍历左右子树，再输入节点值。
　　层级遍历：对于层次遍历，只需要一个队列即可，先在队列中加入根结点。之后对于任意一个结点来说，在其出队列的时候访问。如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。同时如果左孩子和右孩子有不为空的，入队           列。

　　3、代码

package demo01;
import java.util.LinkedList;

public class Tree01 {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		/*
        作业要求：叉树的先、中、后 序遍历与层级遍历
        自己实现四个方法，Tree01方法中调用，将结果打印到控制台
     */
		 /*  二叉树的结构
        A
       / \
      T   6
     /
    D
  /   \
 N     5
/ \    /
B   4  1
    \
     9
*/
 Node root = into();
// 先序遍历
 A(root);
 System.out.println("先序");
// 中序遍历
 B(root);
 System.out.println("中序");
// 后序遍历
 C(root);
 System.out.println("后序");
// 层级遍历
 D(root);
 System.out.println("层级");

}
 private static void A(Node tree) {
// TODO 先序遍历
 if (tree != null) {
   System.out.print(tree.data + " ");
   A(tree.l);
   A(tree.r);
}

}

 private static void B(Node tree) {
// TODO 中序遍历
 if (tree != null) {
 B(tree.l);
 System.out.print(tree.data + " ");
 B(tree.r);
}

}

 private static void C(Node tree) {
// TODO 后序遍历
 if (tree != null) {
 C(tree.l);
 C(tree.r);
 System.out.print(tree.data + " ");
}

}

 private static void D(Node tree) {
// TODO 层级遍历
 if (tree != null) {
 LinkedList linkedList = new LinkedList();
     //将根节点列入到List中
 linkedList.offer(tree);
 Node node = null;
 while (!linkedList.isEmpty()) {
	 //移除列表中的一个元素,返回元素值
   node = (Node) linkedList.pop();
   System.out.print(node.data + " ");
   if (node.l != null) {
       //将出队结点的左子树根入队
       linkedList.offer(node.l);
   }
   if (node.r != null) {
       //将出队结点的右子树根入队
       linkedList.offer(node.r);
   }
}
}

}

// 构建一颗树，返回至根节点
 private static Node into(){
 Node root = new Node("A");
 Node node1 = new Node("T");
 Node node2 = new Node("D");
 Node node3 = new Node("N");
 Node node4 = new Node("B");
 Node node5 = new Node("6");
 Node node6 = new Node("5");
 Node node7 = new Node("4");
 Node node8 = new Node("9");
 Node node9 = new Node("1");
 root.l = node1;
 node1.l = node2;
 node2.l = node3;
 node2.r = node6;
 node3.r = node7;
 node7.r = node8;
 node6.l = node9;
 node3.l = node4;
 root.r = node5;
 return root;
}

// 节点
 static class Node{
// 数据
 Object data;
// 左孩子
 Node l;
// 右孩子
 Node r;

 public Node(){}

 public Node(Object data) {
 this.data = data;
 this.l = null;
 this.r = null;
}

 public Node(Object data, Node l, Node r) {
 this.data = data;
 this.l = l;
 this.r = r;
}
	}

}