1. 排序二叉树
排序二叉树是在二叉树的限制基础上又加了一些限制,所有的的树节点数据都具有可比较性质、树的根节点数据肯定都大于它的左子树中所有节点、树的根节点数据也都小于或者等于它的右子树的所有节点。同理这个棵树上的父节点都大于左节点,并且小于等于右节点。如下图所示。
就是一颗排序二叉树,对此树进行深度优先中根遍历法,那么会得到从小到大的排列顺序:1、2、4、5、7、10、12、13、14、15、18。
2. 使用场景
顾名思义,排序二叉树就是为了快速排序,查找元素时用的最多的。
3. 维护排序二叉树
构建一棵排序二叉树可能对于咱们来说不是什么难事,但是关键是维护好这颗排序二叉树。比如新增或者删除一个元素节点后,还能严格的保持这棵树是一颗排序二叉树。尤其是涉及到删除节点元素的时候,需要考虑的因素就比较多了比如删除一个节点后,得考虑这个节点是否有子节点,有几个子节点等等。
一般分为如下几个情况处理。
1):被删除的节点是叶子节点,没关系,不会影响大局,直接删除即可
2):被删节点只有左子树或者只有右子树,被删除的节点只有单子树的。直接将被删节点的子树赋给被删节点的父节点即可,也就是说被删节点的左子树代替被删节点成为被删结点父亲的左子树,而被删节点的右子树代替被删节点成为被删结点父亲的右子树。
3):被删节点既有左子树又有右字数,这种是比较麻烦的,也就是当不当、正不正只删除中间的节点。这个时候就要用被删节点最大左子树的节点或者用最小右子树的的节点代替被删节点。
添加节点:添加节点的过程实际上就是构建排序二叉树的过程。原理如下
1):首先有一个根节点
2):以根节点作为当前节点开始检索
3):新增节点和当前节点进行值比较
4):如果新节点比当前节点大,那么当前节点的右子节点作为新的当前节点,如果当前节点比当前节点小,那么当前节点的左子节点作为新的当前节点。
5):重复3和4步骤直到当前节点没有了子节点,那么新节点作为当前节点的子节点,具体作为左子节点还是有子节点得看新节点的值和当前节点值得比较。
4. 算法代码
实现创建排序二叉树以及维护排序二叉树的代码如下:
package dateStructer.tree.orderTree;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
/**
* 排序二叉树
*
* @author liuyan
*/
public class OrderTree {
static class Node {
Integer data;
Node parent;
Node left;
Node right;
public Node(Integer data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "[data:" + this.data + "]";
}
}
private Node root;
public OrderTree(Integer data) {
root = new Node(data, null, null, null);
}
/**
* 添加新节点
*
* @param data
*/
public void addNode(Integer data) {
if (root == null) {
root = new Node(data, null, null, null);
return;
}
// 从根节点开始
Node nowNode = root;
Node newParent = null;
do {
newParent = nowNode;
if (nowNode.data > data) {
nowNode = nowNode.left;
} else {
nowNode = nowNode.right;
}
} while (nowNode != null);
if (newParent.data > data) {
newParent.left = new Node(data, newParent, null, null);
} else {
newParent.right = new Node(data, newParent, null, null);
}
}
/**
* 查找节点对象
*
* @param data
* @return
*/
public Node findNode(Integer data) {
Node nowNode = root;
while (nowNode != null) {
if (nowNode.data == data) {
return nowNode;
}
if (nowNode.data > data) {
nowNode = nowNode.left;
} else {
nowNode = nowNode.right;
}
}
return null;
}
/**
* 删除节点
*
* @param data
*/
public void deleteNode(Integer data) {
Node tagNode = findNode(data);
if (tagNode == null) {
return;
}
if (tagNode == root) {
root = null;
}
if (tagNode.left == null && tagNode.right == null) {
if (tagNode.parent.left == tagNode) {
tagNode.parent.left = null;
} else if (tagNode.parent.right == tagNode) {
tagNode.parent.right = null;
}
return;
}
if (tagNode.left == null && tagNode.right != null) {
if (tagNode.parent.left == tagNode) {
tagNode.parent.left = tagNode.right;
} else if (tagNode.parent.right == tagNode) {
tagNode.parent.right = tagNode.right;
}
return;
}
if (tagNode.left != null && tagNode.right == null) {
if (tagNode.parent.left == tagNode) {
tagNode.parent.left = tagNode.left;
} else if (tagNode.parent.right == tagNode) {
tagNode.parent.right = tagNode.left;
}
return;
}
Node leftMaxNode = tagNode.left;
while (leftMaxNode.right != null) {
leftMaxNode = leftMaxNode.right;
}
leftMaxNode.parent.right = null;
leftMaxNode.parent = tagNode.parent;
if (tagNode == tagNode.parent.left) {
leftMaxNode.parent.left = leftMaxNode;
} else {
leftMaxNode.parent.right = leftMaxNode;
}
leftMaxNode.left = tagNode.left;
leftMaxNode.right = tagNode.right;
tagNode.left = null;
tagNode.right = null;
tagNode.parent = null;
}
public static List<Node> deepFirst(Node root) {
List<Node> list = new ArrayList<Node>();
Queue<Node> queue = new ArrayDeque<Node>();
queue.add(root);
while (!queue.isEmpty()) {
list.add(queue.peek());
Node twoLinkNode = queue.poll();
if (twoLinkNode.left != null) {
queue.add(twoLinkNode.left);
}
if (twoLinkNode.right != null) {
queue.add(twoLinkNode.right);
}
}
return list;
}
/**
* @param args
*/
public static void main(String[] args) {
OrderTree orderTree = new OrderTree(7);
orderTree.addNode(4);
orderTree.addNode(1);
orderTree.addNode(2);
orderTree.addNode(5);
orderTree.addNode(5);
orderTree.addNode(13);
orderTree.addNode(10);
orderTree.addNode(12);
orderTree.addNode(15);
orderTree.addNode(14);
orderTree.addNode(18);
System.out.println(deepFirst(orderTree.root));
orderTree.deleteNode(4);
System.out.println(deepFirst(orderTree.root));
}
}
运行后效果如下
[[data:7], [data:4], [data:13], [data:1], [data:5], [data:10], [data:15], [data:2], [data:5], [data:12], [data:14], [data:18]]
//删除后
[[data:7], [data:2], [data:13], [data:1], [data:5], [data:10], [data:15], [data:5], [data:12], [data:14], [data:18]]
删除后的树形图应该如下
- 大小: 35.9 KB
- 大小: 31.2 KB
分享到:
相关推荐
### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树,它在计算机科学领域有着广泛的应用,尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树,其构建原则是使得带权路径...
在Java编程中,数据结构是解决问题的关键工具之一,其中树是一种非常重要的非线性数据结构。本篇复习笔记主要关注树的概述,包括树的概念、基本操作、使用场景以及一种特殊的树实现——记父节点实现。 1. **树的...
7. **实际应用**:最后,笔记可能会将这些理论知识与实际编程语言(如C++、Java或Python)结合,通过示例代码解释如何实现这些数据结构和算法。 由于笔记名为“数据结构高分笔记”,它很可能会重点强调考试中的常见...
### JavaSE基础复习知识点 #### 1. 数组在内存中的存储状态 ...综上所述,Java的基础复习不仅仅是对语言特性的简单回顾,更重要的是深入理解其背后的实现原理和技术细节,从而更好地掌握Java编程的核心技能。
此外,笔记还会强调实际编程实现,包括C++或Java等语言的数据结构实现,如链表的插入、删除、遍历,树的构建与遍历,图的邻接矩阵和邻接表表示,以及各种排序和查找算法的代码实现。这部分内容有助于考生提升编程...
这些文件涵盖了Java数据结构与算法的核心主题,是学习和复习的重要资源。让我们逐一解析每个文件名,探索其中可能涵盖的知识点: 1. **day02 链表.md** - 链表是数据结构的基础,它不依赖于内存位置连续存储元素。...
数据结构是计算机科学中...这个压缩包“my_resource”可能包含了上述所有知识点的相关文件,如笔记、代码示例、练习题解答等,是学习和复习数据结构算法的理想资源。记得深入学习和动手实践,以真正掌握这些重要概念。
"newreview_die4ix_Java数据结构_"这个标题暗示了这是一个关于Java编程和数据结构复习的资源,可能包含了作者die4ix在学习或教学过程中整理的笔记、示例代码或测试题目。 描述中提到的“java基本编程的复习”涵盖了...
至于怎么判断笔记是否翻新过,主要看前缀有没有《恋上数据结构第x季》 抛开学习数据结构的角度不说,恋上数据结构的每一份数据结构的代码都是健壮而又完善的,完全可以在业务中需要的时候直接拿来用。 我的《恋上...
"Java数据结构与算法视频下载地址.txt"这个文件很可能是提供视频资源的链接,确保下载并按照顺序学习,同时做好笔记,及时复习巩固。通过44集的学习,你将对数据结构和算法有深入的理解,并能将这些知识应用到实际的...
1. **基础数据结构与算法**:Java中常见的数据结构如数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)以及图等是面试的基础。算法方面,排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找)...
数据结构与算法分析是计算机科学中的核心领域,它关乎如何高效地存储和处理信息,以及设计和实现高效的计算过程。这份“数据结构与算法分析...所以,这份笔记对于学习和复习数据结构与算法分析来说,是一份宝贵的资源。
这个压缩包“数据结构和算法课件笔记代码.zip”包含两部分主要内容:课件和代码。这些资源可以帮助学习者深入理解数据结构的原理和算法的实现。 首先,让我们详细讨论数据结构。数据结构是组织和存储数据的方式,以...
在“清华大学内部数据结构讲解”中,你可能会学到这些数据结构的实现细节,包括如何在C++或Java中创建和操作这些结构。此外,还会深入讨论各种操作的时间复杂度和空间复杂度,这是理解算法效率的关键。 接下来,会...
复习资料中可能还包括了编程语言与数据结构的结合,如C++或Java中的指针和对象,以及如何使用这些语言实现各种数据结构。理解数据结构的抽象数据类型(ADT)和其实现,比如用数组实现栈和队列,用链表实现集合和映射...
这个名为"2011数据结构其中.zip"的压缩包文件可能包含了一位学生或教师在2011年关于数据结构课程的学习资料,其中的文档"2011数据结构其中.doc"很可能是课程笔记、作业、讲义或者复习材料。 数据结构的基本概念包括...
数据结构与算法是计算机科学的基础,对于理解和设计高效的软件系统至关重要。这个压缩包文件很可能包含了一系列关于这个主题的教程、笔记、练习题或者代码示例,帮助学习者深入理解这一领域。 数据结构是组织和存储...
总的来说,《LeetCode刷题笔记》不仅记录了个人在LeetCode上的学习过程,也是对数据结构和算法的系统复习。通过刷题,我们可以不断提升自己的编程思维,提高解决问题的能力,为职场竞争增添砝码。无论是初学者还是...