# Algorithm
学习数据结构和算法分析的一些实例,包括排序算法、搜索算法、递归、二叉树等等实例
如二叉树中的表达式树构造的完整实例:
## 表达式树
表达式树(expression tree)的树叶是操作数(operand),如常量或变量名,而其他节点为操作符(operator)。如下图
![表达式树](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91.png)
<center>图1 (a+b\*c)+((d\*e+f)\*g)的表达式树</center>
我们可以通过递归地产生一个带括号的左表达式,然后打印出在跟出的运算符,最后再递归地产生一个带括号的右表达式从而得到一个中缀表达式。这种一般的方法(左,节点,右)的方式成为**中序遍历**。
## 构造表达式树
我们现在给出一个算法来把后缀表达式转变成表达式树。
设输入为:
a b + c d e + * *
前两个符号是操作数,因此创建两颗单节点书并将它们压入栈中。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/1%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
接着,+被读取,因此两棵树被弹出,一颗新的树形成,并被压入栈中。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/2%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
然后,c、d、e被读入,分别创建对应的单节点树,然后压入栈中。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/3%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
接下来读到+号,因此两棵树合并。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/4%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
继续进行,读到\*号,弹出两棵树合成一颗新的树并压入栈中。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/5%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
最后,读入最后一个符号,两棵树合并,而最后的树被留在栈中。
![](http://odwpzo1jp.bkt.clouddn.com//starshipzhou/Algorithm/6%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%A0%91%E6%9E%84%E9%80%A0.png)
## 从后缀表达式构造表达式树的实现
创建节点类BinaryNode.class
```
public class BinaryNode {
String element;
BinaryNode left;
BinaryNode right;
public BinaryNode(String element) {
this.element = element;
}
public BinaryNode(String element, BinaryNode left, BinaryNode right) {
this.element = element;
this.left = left;
this.right = right;
}
//为节省篇幅,getter()、setter()方法略去,请自行补充
}
```
常见一个ExpressionTree.class类,该类有三个静态方法,分别是:postfixToExpressionTree(String[] expressions)、printBinaryTree(int depth,BinaryNode binaryNode)和main(String[] args)。
postfixToExpressionTree(String[] expressions)方法负责将后缀表达式构造成表达式树并返回:
```
/**
* 构造表达式树的静态方法。
* 遍历表达式,若为操作数则构造单节点树压入stack,若为操作符,则弹出两个节点,与
* 操作符构造成新的树,再压入stack中。最后stack中只剩一个节点,该节点就是我们要求的
* 表达式树。
* @param expressions 后缀表达式分解过后的字符串数组
* @return
*/
public static BinaryNode postfixToExpressionTree(String[] expressions){
BinaryNode operand1; //用于暂存弹出的BinaryNode节点
BinaryNode operand2;
Stack<BinaryNode> stack = new Stack<BinaryNode>(); //用于构造表达式树的栈
for (String s:expressions) { //遍历表达式
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
operand1=stack.pop(); //弹出操作数
operand2=stack.pop();
stack.push(new BinaryNode(s,operand2,operand1)); //构造成新树并压入栈中
}else {
stack.push(new BinaryNode(s));
}
}
return stack.pop();
}
```
printBinaryTree(int depth,BinaryNode binaryNode)方法负责打印二叉树,并在每个节点前锁紧与深度相当的空格,方便观察树的结构。
```
/**
* 打印二叉树的方法。
* 通过递归调用来打印二叉树。并在节点前缩进了与深度相当的空格,方便观察。
* @param depth 当前节点在树中的的深度
* @param binaryNode 当前树节点
*/
public static void printBinaryTree(int depth,BinaryNode binaryNode){
for (int i=0;i<depth;i++){ //打印与深度相当的缩进
System.out.print(" ");
}
System.out.println(binaryNode.getElement()); //打印当前节点的数据
if (binaryNode.getLeft() != null){ //若左子树不为空,那么递归调用打印方法,打印左子树
printBinaryTree(depth+1,binaryNode.getLeft());
}
if (binaryNode.getRight() != null){ //若右子树不为空,那么递归调用打印方法,打印右子树
printBinaryTree(depth+1,binaryNode.getRight());
}
}
```
main()方法用于测试,负责接收表达式并将其拆解成字符串数组,传递给postfixToExpressionTree方法,然后调用printBinaryTree方法打印返回的表达式树。
```
/**
* 测试构造和打印表达式树的方法。
* main()方法用于测试,负责接收表达式并将其拆解成字符串数组,传递给
* postfixToExpressionTree方法,然后调用printBinaryTree方法打印返回的表达式树。
* @param args 忽略
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine(); //接收表达式
String[] splits= s.split(""); //分解成字符串数组
BinaryNode binaryNode=postfixToExpressionTree(splits); //构造比表达式树
printBinaryTree(0,binaryNode); //打印表达式树
}
```
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何具体存储。例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界法等。 算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
资源推荐
资源详情
资源评论
收起资源包目录
学习数据结构和算法分析的一些实例,包括排序算法、搜索算法、递归、二叉树等等实例.zip (34个子文件)
open_suanfayushujujiegouxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxcxvcvcv
pom.xml 421B
src
main
java
dataStructure
tree
ExpressionTree.java 3KB
BinaryNode.java 797B
collection
SetAndMap.java 872B
list
LinkList_Error1.java 666B
graph
graph_v
Graph.java 257B
Vertex.java 214B
CreateGraph.java 3KB
Test.java 277B
graph_ve
Graph.java 2KB
Vertex.java 214B
Edge.java 313B
Test.java 1KB
binary_heap
BHTest.java 348B
BinaryHeap.java 3KB
binary_tree
BinarySearchTree.java 3KB
algorithm
sorting
InsertionSorting.java 1KB
ShellSorting.java 1KB
HeapSorting.java 2KB
MergeSorting.java 3KB
greedy
Greedy.java 1KB
面试题——贪心算法.md 443B
generic
GenericClass.java 164B
GenericMethod.java 234B
search
BinarySearch.java 2KB
recursion
PrintNumTest.java 704B
quicksort
QuickSort2.java 3KB
QuickSort.java 1KB
Test.java 246B
.idea
misc.xml 454B
compiler.xml 630B
modules.xml 258B
Algorithm.iml 830B
README.md 6KB
共 34 条
- 1
资源评论
极致人生-010
- 粉丝: 2902
- 资源: 2822
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功