根据树的前序和后序表达式构造唯一树

原题是“根据树的前序和后序表达式求中序表达式”,构造出了树求中序表达式还是问题吗?

构造树是需要一定技巧的,需要不断的递归分析。将大规模分为小规模,将每个小规模再细分,直到不可再分,树也就构建好了。就跟 归并排序 一样

前序和中序分别是:

pre: A B D E G C F

on: D B G E A C F

树的三种遍历方式

算法第二章 排序

第二章 排序

待排序的元素需要实现 Java 的 Comparable 接口,该接口有 compareTo() 方法,可以用它来判断两个元素的大小关系。

定义算法模板类API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public abstract class Example {

/**
* 具体排序算法实现
*/
public abstract void sort(Comparable[] a);

/**
* 对元素进行比较
* @return first < second ? true : false
*/
public static boolean less(Comparable first, Comparable second) {
return first.compareTo(second) < 0;
}

/**
* 把两个元素交换位置
*/
public static void exch(Comparable[] a, int i, int j) {
Comparable tem = a[i];
a[i] = a[j];
a[j] = tem;
}

/**
* 返回序列是否有序(asc)
*/
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
// 后面的元素 < 前面的元素 不是升序排列 返回false
return false;
}
}
return true;
}

public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
}

算法第一章 基础

第一章 基础

基础编程模型

格式化输出

从标准输出流中打印随机生成的数值,“%.2f\n”表示输出两位小数精度的浮点型数值并换行。

cmd运行需要注意的几个地方:

  1. 我们的工程一般使用utf-8编码,但是windows系统默认gbk编码,所以编译javac会出现“找不到gbk编码的字符映射”。解决办法:编译时指定参数 -encoding utf-8

  2. “找不到某个类”,程序中引用了非当前目录的jar文件,在本路径编译会找不到jar包,需要执行参数:-Djava.ext.dirs=jar包作为路径

  3. “无法运行主类”,检查是否配置了classpath环境变量,CLASSPATH=".;%JAVA_HOME%\lib;%JAVA_HOME%\lib\tools.jar;"

  4. 如果被编译类有包,需要在该包下执行编译和运行,最终该类的编译和运行命令:

    javac -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib -encoding utf-8 chapter_1/programming_model/RandomSeq.java
    java -Djava.ext.dirs=D:\IdeaProjects\Algorithms\lib chapter_1/programming_model/RandomSeq 10 1 100

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×