2020软件工程作业04

这个作业属于哪个课程	2018级软件工程 - 中南林业科技大学涉外学院
这个作业要求在哪里	2020软件工程作业04
这个作业的目标	测试编程能力
其他参考文献

题一：寻找数组中第K大是数 考察算法：排序算法 总分:50

解题思路

按指定要求拷贝数组，拷贝后进行排序，得到指定大小的数

代码

import java.util.Arrays;
import java.util.Scanner;

public class Demo1 {

	public static void main(String[] args) {
		int n = 0;		
		int m = 0;
		int l,r,k;
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0;i<n;i++) {
			arr[i] = sc.nextInt();
		}
		
		m = sc.nextInt();
		for(int i = 0;i < m;i++) {
			l = sc.nextInt();
			r = sc.nextInt();
			k = sc.nextInt();
			
			int[] newarr = Arrays.copyOfRange(arr, l-1, r);
			Arrays.sort(newarr);			
			System.out.println(newarr[newarr.length-k]);
		}
	}

}

题二：二叉树的先、中、后 序遍历与层级遍历 考察算法： dfs + bfs搜索算法 总分:40

解题思路

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：先将根节点入队，出队保存队头并访问，将出队结点的左右子树根入队

代码

import java.util.LinkedList;


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

	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) {
		if (tree != null) {
			
			LinkedList<Node> linkedList = new LinkedList<Node>();
			 //先将根节点入队
			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;
		}
	}
}

此次学习感悟：

第一题我无法登陆蓝桥杯练习系统，所以也没有办法打开原题提交。
对于二叉树个人并不熟练，不太会写

时间	链接
2020/7/28	2020软件工程作业01
2020/8/1	2020软件工程作业02