suhuanzheng7784877
- 浏览: 704351 次
- 性别:
- 来自: 北京
-
博客专栏
-
-
读金庸故事，品程序人生
浏览量：47750
文章分类
最新评论
-
hty881008：
LZ，你的json返回是怎么出来的，我的怎么是No messa ...
使用CXF暴露您的REST服务 -
jxFY：
赞
Apache的对象池化工具commons-pool -
wangyudong：
新版本的Wisdom RESTClient地址https:// ...
使用CXF暴露您的REST服务 -
wangyudong：
由CXF实现的微服务需要有比较好的工具去测试RESTful A ...
使用CXF暴露您的REST服务 -
spring_springdata：
可以参考最新的文档：如何在eclipse jee中检出项目并转 ...
Maven3实战笔记01环境配置与使用入门
1. 二叉树
一般的树限制比较少，所以才提出了具有特色的二叉树的概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干很多树不能干的事情了。如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。如下图
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。
2. 二叉树的操作
二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节点、返回指定节点的父节点，返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。
3. 二叉树的延伸
其实二叉树只是一个引子，计算机界很多的算法都是根据二叉树所展开的，比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。
4. 顺序实现二叉树
下面我们来看看二叉树的顺序实现方式，顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下
package dateStructer.tree.binaryTree;
/**
* 顺序二叉树
*
* @author liuyan
*/
public class ArrayBinaryTree<T> {
// 树的默认深度
private static final int DefTreeDeep = 4;
// 节点数组
private Object[] datas;
// 指定的树的深度
private int treeDeep;
// 实际的数组个数
private int arraySize;
/**
* 默认构造函数
*/
public ArrayBinaryTree() {
// 设置默认的树深度
treeDeep = DefTreeDeep;
// 2的DefTreeDeep次方-1个数组元素
arraySize = (int) Math.pow(2, DefTreeDeep) - 1;
datas = new Object[arraySize];
}
/**
* 指定深度构建二叉树
* @param deep
*/
public ArrayBinaryTree(int deep) {
// 按指定深度
treeDeep = deep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new Object[arraySize];
}
/**
* 指定深度和指定根节点构建二叉树
* @param deep
* @param data
*/
public ArrayBinaryTree(int deep, T data) {
// 按指定深度
treeDeep = deep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new Object[arraySize];
datas[0] = data;
}
/**
* 为指定节点索引增加子节点
* @param index
* @param data
* @param isLeft
* @return
*/
public boolean addNode(int index, T data, boolean isLeft) {
if (index * 2 + 2 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
if (isLeft) {
datas[index * 2 + 1] = data;
} else {
datas[index * 2 + 2] = data;
}
return true;
}
/**
* 判断二叉树是否为空
*
* @return
*/
public boolean isEmpty() {
return arraySize == 0;
}
/**
* 返回根节点
*
* @return
*/
@SuppressWarnings("unchecked")
public T getRoot() {
return (T) datas[0];
}
/**
* 返回指定节点的父节点
* @return
*/
@SuppressWarnings("unchecked")
public T getParent(int index) {
if (index > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
if (datas[(index - 1) / 2] == null) {
throw new RuntimeException("无父节点");
}
return (T) datas[(index - 1) / 2];
}
/**
* 返回左子节点
* @return
*/
@SuppressWarnings("unchecked")
public T getLeftNode(int index) {
if (index * 2 + 2 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[index * 2 + 1];
}
/**
* 返回右子节点
* @return
*/
@SuppressWarnings("unchecked")
public T getRightNode(int index) {
if (index * 2 + 2 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[index * 2 + 2];
}
/**
* 返回树的深度
* @return
*/
public int getTreeDeep() {
return treeDeep;
}
/**
* 返回指定节点的索引位置
* @param data
* @return
*/
public int getNodeIndex(T data) {
for (int i = 0; i < arraySize; i++) {
if (data == datas[i]) {
return i;
}
}
return -1;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
for (int i = 0; i < datas.length; i++) {
str.append("[" + datas[i] + "],");
}
if (datas.length > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
}
测试代码如下
public static void main(String[] args) {
ArrayBinaryTree<String> arrayBinaryTree = new ArrayBinaryTree<String>(4,"汉献帝");
System.out.println(arrayBinaryTree);
arrayBinaryTree.addNode(0, "刘备", true);
arrayBinaryTree.addNode(0, "曹操", false);
arrayBinaryTree.addNode(1, "关羽", true);
arrayBinaryTree.addNode(1, "张飞", false);
arrayBinaryTree.addNode(2, "张辽", true);
arrayBinaryTree.addNode(2, "许褚", false);
System.out.println(arrayBinaryTree);
System.out.println(arrayBinaryTree.getLeftNode(1));
System.out.println(arrayBinaryTree.getRightNode(0));
System.out.println(arrayBinaryTree.isEmpty());
System.out.println(arrayBinaryTree.getParent(4));
}
测试效果如下
顺序实现是比较浪费资源的，可以看到数组没有元素的位置都是null。如果将测试代码稍微变更一下，如下因为树本身就是具有递归性质的结构。
public static void main(String[] args) {
ArrayBinaryTree<String> arrayBinaryTree = new ArrayBinaryTree<String>(4,"汉献帝");
System.out.println(arrayBinaryTree);
arrayBinaryTree.addNode(0, "刘备", true);
arrayBinaryTree.addNode(0, "曹操", false);
arrayBinaryTree.addNode(2, "张辽", true);
arrayBinaryTree.addNode(2, "许褚", false);
arrayBinaryTree.addNode(6, "李典", true);
arrayBinaryTree.addNode(6, "乐进", false);
System.out.println(arrayBinaryTree);
System.out.println(arrayBinaryTree.getLeftNode(2));
System.out.println(arrayBinaryTree.getRightNode(0));
System.out.println(arrayBinaryTree.isEmpty());
System.out.println(arrayBinaryTree.getParent(14));
}
运行效果如下
可以看到数组中间资源浪费得很严重。
5. 二叉链表实现二叉树
为了弥补顺序实现的空间浪费问题，可以使用链表方式实现二叉树，但是链表又分为两种情况，一种是二叉链表，另一种稍后再说。二叉链表的思想就是构造一个对象，记住它的两个子节点，所谓记住两个子节点可以是子节点的位置，可以是子节点的实体对象。如果记录了位置，其实是离不开数组的帮助的。如果记录了整个子节点对象，那么就可以完全脱离数组，完完全全，真真正正的链表离散式存储。这次使用记录节点位置，算法如下
package dateStructer.tree.binaryTree;
/**
* 二叉链表二叉树
*
* @author liuyan
*/
public class TwoLinkedBinaryTree<T> {
// 树的默认深度
private static final int DefTreeDeep = 4;
// 节点数组
private TwoLinkNode<T>[] datas;
// 指定的树的深度
private int treeDeep;
// 实际的数组个数
private int arraySize;
//节点个数
private int nodeSize;
/**
* 二叉节点
*/
@SuppressWarnings("hiding")
class TwoLinkNode<T> {
public int leftChildIndex;
public int rightChildIndex;
public int index;
public T data;
}
@SuppressWarnings("unchecked")
public TwoLinkedBinaryTree() {
treeDeep = DefTreeDeep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new TwoLinkNode[arraySize];
}
@SuppressWarnings("unchecked")
public TwoLinkedBinaryTree(int deep, T data) {
treeDeep = DefTreeDeep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new TwoLinkNode[arraySize];
TwoLinkNode<T> twoLinkNode = new TwoLinkNode<T>();
twoLinkNode.data = data;
twoLinkNode.leftChildIndex = 1;
twoLinkNode.rightChildIndex = 2;
twoLinkNode.index = 0;
datas[0] = twoLinkNode;
nodeSize = 1;
}
/**
* 为指定节点索引增加子节点
*
* @param index
* @param data
* @param isLeft
* @return
*/
public boolean addNode(int index, T data, boolean isLeft) {
if (index + 1 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
for (int i = index + 1; i < arraySize; i++) {
if (datas[i] == null) {
TwoLinkNode<T> twoLinkNode = new TwoLinkNode<T>();
twoLinkNode.data = data;
twoLinkNode.index = i;
datas[i] = twoLinkNode;
if (isLeft) {
datas[index].leftChildIndex = i;
} else {
datas[index].rightChildIndex = i;
}
nodeSize ++;
return true;
}
}
return false;
}
/**
* 判断二叉树是否为空
*
* @return
*/
public boolean isEmpty() {
return nodeSize == 0;
}
/**
* 返回根节点
*
* @return
*/
@SuppressWarnings("unchecked")
public T getRoot() {
return (T) datas[0];
}
/**
* 返回指定节点的父节点
*
* @return
*/
public T getParent(int index) {
if (index > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
for (int i = 0; i < arraySize; i++) {
if (datas[i] != null) {
if (datas[i].leftChildIndex == index
|| datas[i].rightChildIndex == index) {
return datas[i].data;
}
}
}
return null;
}
/**
* 返回左子节点
*
* @return
*/
public T getLeftNode(int index) {
if (index + 2 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[datas[index].leftChildIndex].data;
}
/**
* 返回右子节点
*
* @return
*/
public T getRightNode(int index) {
if (index + 2 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[datas[index].rightChildIndex].data;
}
/**
* 返回树的深度
*
* @return
*/
public int getTreeDeep() {
return treeDeep;
}
/**
* 返回指定节点的索引位置
*
* @param data
* @return
*/
public int getNodeIndex(T data) {
for (int i = 0; i < arraySize; i++) {
if (data == datas[i]) {
return i;
}
}
return -1;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
for (int i = 0; i < nodeSize; i++) {
if(datas[i].data != null){
str.append("[" + datas[i].data + "],");
}
}
if (datas.length > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
}
使用这种实现其实是想利用好数组的空间。别让中间任何的节点空间白白浪费了。但是可以发现找父节点的时候比较麻烦。还得遍历一下整个节点。三叉链表就不必遍历，因为三叉链表比二叉链表多了记录了一个节点，那就是此节点的父节点。无论是父节点的位置或者父节点实体，都是一样的思想。
6. 三叉链表实现二叉树
下面我们基于上面的二叉链表形式编写三叉链表。代码如下
package dateStructer.tree.binaryTree;
/**
* 三叉链表的实现
*
* @author liuyan
*/
public class ThreeLinkedBinaryTree<T> {
// 树的默认深度
private static final int DefTreeDeep = 4;
// 节点数组
private ThreeLinkNode<T>[] datas;
// 指定的树的深度
private int treeDeep;
// 实际的数组个数
private int arraySize;
// 节点个数
private int nodeSize;
/**
* 三叉节点
*/
@SuppressWarnings("hiding")
class ThreeLinkNode<T> {
public int parentIndex;
public int leftChildIndex;
public int rightChildIndex;
public int index;
public T data;
}
@SuppressWarnings("unchecked")
public ThreeLinkedBinaryTree() {
treeDeep = DefTreeDeep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new ThreeLinkNode[arraySize];
}
@SuppressWarnings("unchecked")
public ThreeLinkedBinaryTree(int deep, T data) {
treeDeep = DefTreeDeep;
arraySize = (int) Math.pow(2, treeDeep) - 1;
datas = new ThreeLinkNode[arraySize];
ThreeLinkNode<T> threeLinkNode = new ThreeLinkNode<T>();
threeLinkNode.data = data;
threeLinkNode.leftChildIndex = 1;
threeLinkNode.rightChildIndex = 2;
threeLinkNode.index = 0;
threeLinkNode.parentIndex = -1;
datas[0] = threeLinkNode;
nodeSize = 1;
}
/**
* 为指定节点索引增加子节点
*
* @param index
* @param data
* @param isLeft
* @return
*/
public boolean addNode(int index, T data, boolean isLeft) {
if (index + 1 > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
for (int i = index + 1; i < arraySize; i++) {
if (datas[i] == null) {
ThreeLinkNode<T> threeLinkNode = new ThreeLinkNode<T>();
threeLinkNode.data = data;
threeLinkNode.index = i;
threeLinkNode.parentIndex = index;
datas[i] = threeLinkNode;
if (isLeft) {
datas[index].leftChildIndex = i;
} else {
datas[index].rightChildIndex = i;
}
nodeSize++;
return true;
}
}
return false;
}
/**
* 判断二叉树是否为空
*
* @return
*/
public boolean isEmpty() {
return nodeSize == 0;
}
/**
* 返回根节点
*
* @return
*/
@SuppressWarnings("unchecked")
public T getRoot() {
return (T) datas[0];
}
/**
* 返回指定节点的父节点
*
* @return
*/
@SuppressWarnings("unchecked")
public T getParent(int index) {
if (index > arraySize || datas[index] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[datas[index].parentIndex];
}
/**
* 返回左子节点
*
* @return
*/
public T getLeftNode(int index) {
if (index + 2 > arraySize || datas[index] == null
|| datas[datas[index].leftChildIndex] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[datas[index].leftChildIndex].data;
}
/**
* 返回右子节点
*
* @return
*/
public T getRightNode(int index) {
if (index + 2 > arraySize || datas[index] == null
|| datas[datas[index].rightChildIndex] == null) {
throw new RuntimeException("标记无效");
}
return (T) datas[datas[index].rightChildIndex].data;
}
/**
* 返回树的深度
*
* @return
*/
public int getTreeDeep() {
return treeDeep;
}
/**
* 返回指定节点的索引位置
*
* @param data
* @return
*/
public int getNodeIndex(T data) {
for (int i = 0; i < arraySize; i++) {
if (data == datas[i]) {
return i;
}
}
return -1;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
for (int i = 0; i < nodeSize; i++) {
if (datas[i].data != null) {
str.append("[" + datas[i].data + "],");
}
}
if (datas.length > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
}
可以看到基本上方法实现都一样，就是找寻父节点的时候更省事了。因为节点对象多存了父节点的信息，当然就省事了。
7. 二叉树的遍历
遍历二叉树实际上就是将一个非线性的二维结构给排列呈线性的过程。如果是顺序实现了二叉树的结构，自然底层就是线性的，无需转化。如果是纯链表实现呢，就需要将离散的节点重新组织组织了。
遍历也分为深度优先遍历、广度优先遍历。而对于深度优先遍历又分为三种模式：先根遍历、中根遍历、后根遍历。
深度优先遍历：就是优先访问树中最深层次的节点
广度优先遍历：就是从根往下一层一层遍历访问
先根遍历：先遍历根节点，之后处理其他子节点
中根遍历：先遍历根节点的左子树，之后遍历根节点，最后遍历右子树
后根遍历：先遍历根节点的左子树，之后遍历右子树，最后遍历根节点
先根遍历算法如下
public List<TwoLinkNode<T>> firstRoot(TwoLinkNode<T> twoLinkNode) {
if (twoLinkNode == null) {
return null;
}
List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();
list.add(twoLinkNode);
if (twoLinkNode.leftChildIndex > 0) {
list.addAll(firstRoot(datas[twoLinkNode.leftChildIndex]));
}
if (twoLinkNode.rightChildIndex > 0) {
list.addAll(firstRoot(datas[twoLinkNode.rightChildIndex]));
}
return list;
}
中根遍历算法如下
/**
* 中根遍历
*
* @param twoLinkNode
* @return
*/
public List<TwoLinkNode<T>> minRoot(TwoLinkNode<T> twoLinkNode) {
if (twoLinkNode == null) {
return null;
}
List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();
if (twoLinkNode.leftChildIndex > 0) {
list.addAll(minRoot(datas[twoLinkNode.leftChildIndex]));
}
list.add(twoLinkNode);
if (twoLinkNode.rightChildIndex > 0) {
list.addAll(minRoot(datas[twoLinkNode.rightChildIndex]));
}
return list;
}
后根遍历
/**
* 后根遍历
*
* @param twoLinkNode
* @return
*/
public List<TwoLinkNode<T>> afterRoot(TwoLinkNode<T> twoLinkNode) {
if (twoLinkNode == null) {
return null;
}
List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();
if (twoLinkNode.leftChildIndex > 0) {
list.addAll(afterRoot(datas[twoLinkNode.leftChildIndex]));
}
if (twoLinkNode.rightChildIndex > 0) {
list.addAll(afterRoot(datas[twoLinkNode.rightChildIndex]));
}
list.add(twoLinkNode);
return list;
}
广度优先遍历
/**
* 后根遍历
*
* @param twoLinkNode
* @return
*/
public List<TwoLinkNode<T>> deepFirst() {
List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();
Queue<TwoLinkNode<T>> queue = new ArrayDeque<TwoLinkNode<T>>();
queue.add(datas[0]);
while (!queue.isEmpty()) {
list.add(queue.peek());
TwoLinkNode<T> twoLinkNode = queue.poll();
if (twoLinkNode.leftChildIndex > 0) {
queue.add(datas[twoLinkNode.leftChildIndex]);
}
if (twoLinkNode.rightChildIndex > 0) {
queue.add(datas[twoLinkNode.rightChildIndex]);
}
}
return list;
}
8. 二叉树、树、森林转换
其实这三个结构可以互相转换，具体参考
http://jpkc.nwu.edu.cn/sjjg/study_online/book/6/4_2.htm
9. 总结
这次总结学习了二叉树的概念、用法、实现细节、二叉树的遍历法。当然了这篇总结还不是很全面。回头再补上吧。
分享到：
发表评论
-
Web应用单点压力测试调优-第6季-阶段性总结
2014-03-14 12:24 3412阶段性总结 <! ... -
Web应用单点压力测试调优-第5季
2014-03-13 09:32 4167各项配置： my.cnf [clien ... -
Web应用单点压力测试调优-第4季
2014-03-12 14:55 3189调整5-Tomcat的启动JVM参数 首先先启动 ... -
单点网站压力测试调优-第3季
2014-03-11 16:21 3453调整2-调整配置，数据库连接池数量 mysql ... -
Web应用单点压力测试调优-第2季
2014-03-07 16:52 8915并发1000,准备时间1s，让它产生大量的等待请求 ... -
单点网站压力测试调优-第1季
2014-03-07 10:36 3981环境介绍 虚拟机配置 ... -
编程质量提高建议总结1（持续总结）
2014-03-05 19:42 1320编程质量提高建议总结1（持续总结） 1.混淆字母要明显 ... -
关于博客文章内容显示不全的问题
2011-06-14 09:36 2437关于博客文章内容显示不全的问题，我发现有些文章显示内容不全。 ... -
Maven3实战笔记05仓库依赖解析与插件解析
2011-06-07 09:00 34271. Maven仓库依赖解析机 ... -
Apache的对象池化工具commons-pool
2011-05-16 09:21 131311. 前言 当我们的应用中创建一个十分最重量级的 ... -
将Sun的Open Message Queue与Spring集成
2011-05-06 09:01 34961. 前言 基于JMS标准的消息中间件实现的产品 ... -
要不要池化是个艰难的选择（转）-我觉得很生动就转载了下来
2011-05-05 09:50 1573转自http://www.ixpub.net/thre ... -
java.lang.IllegalStateException: STREAM错误的理解（转）
2011-05-04 18:09 13823转自http://dimple.iteye.com/blog/ ... -
Spring3配置声明式事务
2011-05-02 16:52 45541. 配置Spring3声明式事务 在Sprin ... -
Java基础复习笔记11基本排序算法
2011-04-25 13:20 21491. 排序 排序是一个历来都是很多算法家热衷的领 ... -
Java基础复习笔记07数据结构-树的概述
2011-04-19 17:35 19601. 树的概念 如果线性表、栈、队列是线性结构（ ... -
Java基础复习笔记06数据结构-队列
2011-04-19 17:25 17101. 队列 队列又是一种比较特殊的线性表，和栈一 ... -
Java基础复习笔记04数据结构-线性表
2011-04-15 14:14 23071. 线性表 线性表是数据结构的一种逻辑结构，其 ... -
Java基础复习笔记03面试、笔试、开发中我们不太注意的陷阱之流程控制、面向对象、异常处理
2011-04-13 09:59 22221. switch语句的用法 有人说：“笔者基础 ... -
Java基础复习笔记03面试、笔试、开发中我们不太注意的陷阱之多线程
2011-04-13 09:51 19711. 什么样的对 ...
相关推荐
【Java基础复习笔记10数据结构-排序二叉树】 排序二叉树是一种特殊类型的二叉树，其每个节点的数据值满足以下特性：对于任意节点，其左子树中的所有节点值都小于该节点，而右子树中的所有节点值都大于或等于该节点...
### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树，它在计算机科学领域有着广泛的应用，尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树，其构建原则是使得带权路径...
### Java基础复习笔记07数据结构-树的概述 #### 一、树的基本概念与术语 树是一种非线性的数据结构，它由一系列节点组成，这些节点之间通过边（连接节点的线）来表示关系。在树形结构中，一个特殊的节点被称为根...
### Java数据结构与算法学习笔记知识点总结 #### 一、数据结构概述 数据结构是对数据的一种组织形式，它决定了数据的存储方式以及处理数据的方法。常见的数据结构包括但不限于数组、链表、栈、队列、二叉树、图等...
7. **实际应用**：最后，笔记可能会将这些理论知识与实际编程语言（如C++、Java或Python）结合，通过示例代码解释如何实现这些数据结构和算法。 由于笔记名为“数据结构高分笔记”，它很可能会重点强调考试中的常见...
数据结构是计算机科学中至关重要的一个领域，它研究如何在计算机中组织和管理数据，以提高数据处理的效率。清华大学的殷人昆教授是数据结构领域的权威专家，他的数据结构笔记因其深入浅出的讲解而备受赞誉。这些PPT...
数据结构笔记-考研复习 数据结构是计算机科学中的一门重要学科，研究如何组织、存储和使用数据。...这些知识点是考研复习笔记中的一些重要内容，通过学习和掌握这些知识点，可以更好地理解和应用数据结构。
java二叉树遍历笔试题 Java中InterviewBit问题的解决方案 编程 种类 递归 二叉搜索树 广度优先搜索 深度优先搜索 动态规划 贪婪的 图形 几何学 模拟 设计 大批 ID 标题 解决方案 时间 空间 困难 笔记 1 O(n*m) O(1) ...
根据提供的信息，我们可以总结出关于考研杭电计算机数据结构笔记的一些关键知识点。由于提供的内容较为杂乱无章，这里将尝试整理出一个清晰的学习框架，并解释其中涉及的主要概念和技术。 ### 1. 数据结构基础 ###...
在Java语言中，数据结构的实现尤为重要，因为Java提供了丰富的库支持来创建和操作各种数据结构。 标题提及的是“数据结构java语言描述课后答案”，这通常指的是学生在学习数据结构课程时，针对教材或课堂讲解的习题...
数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和管理数据，以...学习者通过这份精选笔记，可以系统性地掌握数据结构的核心概念，提高问题解决能力，并为后续的算法学习和软件开发打下坚实基础。
本资源主要讲解了如何使用前序遍历和中序遍历来构造二叉树的算法，并提供了Java和Python的实现代码。下面是对该算法的详细解释： 二叉树的遍历规则 在解决这个问题之前，我们首先需要了解二叉树的遍历规则。二叉树...
3. ** Morris遍历**：这是一种不使用额外数据结构的遍历方法，通过改变二叉树的链接来达到遍历的目的。在原始树的基础上创建临时指向，使得遍历过程中能够回溯。 然而，给定的文件内容主要讨论的是**二叉树的层序...
这份"数据结构考研复习笔记"是作者原创的复习资料，旨在帮助考生系统性地整理和复习数据结构的所有关键概念。 笔记内容可能涵盖以下几个方面： 1. **基本概念**：首先，会介绍数据结构的基本概念，如什么是数据、...
本笔记涵盖了数据结构的重要知识点，包括顺序存储结构、链式存储结构、二叉树、图、树、队列、栈、数组等数据结构的概念和特点，以及它们之间的关系和应用。同时，也包含了算法和数据结构的相关知识点，如排序算法、...
本资源摘要信息将详细介绍如何根据中序遍历和后序遍历结果构建二叉树。 算法笔记 在这里，我们将学习如何使用中序遍历和后序遍历结果构建二叉树。首先，我们需要理解中序遍历和后序遍历的特性。 中序遍历 中序...
这篇超详细的“数据结构知识点-个人笔记”涵盖了数据结构的基础理论和实际应用，是初学者入门的理想资源。 笔记首先介绍了数据结构的基本概念，包括数组、链表、栈和队列等基本类型。数组是最基础的数据结构，它是...
2019 版数据结构高分笔记 X 3.1 栈和队列的基本概念 55 3.1.1 栈的基本概念 55 3.1.2 队列的基本概念 56 3.2 栈和队列的存储结构、算法与应用 56 3.2.1 本章所涉及的结构体定义 56 3.2.2 顺序栈 57 3.2.3 链栈 59 ...