栈、队列、链表都有他们各自的好处,同样的也有弊端的存在。
如果我想要一个有序的数组和链表这个当然很好实现。现在我要在这几个数据结构中查找一个值。先说数组,因为是有序的通过二分查找很快的就可以找到。查找的效率还是很高的,但如果要是插入呢,为了保证有序,我要先找到插入位置,然后再将比插入数字大的数字依次向后移动;这时的第一反应就是链表!他打插入速度很快,只要改变指针的指向就可以了。但是链表大查找要从头开始找啊。只有知道了前一个元素的地址才能知道下一个地址。所以链表查找起来又费劲了。这时候就有人引进了树。
树也分很多种,只说特殊的二叉树中的二叉搜索树。
二叉搜索树定义:一个节点的左子节点的关键自值小于这个节点,右子节点的关键字值大于或等于这个父节点。
二叉搜索树插入的时候可以直接改变左树右树的指针指向,查找的时候可以根据排序二叉树的特点。
这就是一个二叉搜索树
现在开始用代码来描述这棵树。先看节点类
package test;
/**
* @author 作者 MarcoSpring
* @version 创建时间:2012-8-3 上午10:13:13
* 树节点类
*/
public class TreeNode {
public int keyValue; //关键字值
public TreeNode leftNode;//左节点
public TreeNode rightNode;//右节点
public TreeNode(){}
public TreeNode(int Key){
this.keyValue = Key;
}
}
代码不多,描述了一个节点的内容。关于二叉搜索树的描述主要从查询节点、添加节点、遍历、最大值、最小值、删除节点来描述。这里不包括存在相等节点的情况。
查询节点:这个比较简单,根据二叉树的定义查询就可以了。看图写代码最方便,
再看代码
public TreeNode search(int Key) {
TreeNode node = root;
// 首先定义一个节点让其指向根,在下面的循环中
// 只要节点值不等于要查找的节点值就进入循环如果没有找到则返回null
while (node.keyValue != Key) {
if (Key < node.keyValue) { // 如果要查找的值小于节点值则指向左节点
node = node.leftNode;
} else { // 否则指向右节点
node = node.rightNode;
}
if (node == null) { // 如果节点为空了则返回null
return null;
}
}
return node;
}
添加节点,添加节点的过程是现搜索再添加。先看图
再看代码
public void insert(int Key) {
TreeNode node = new TreeNode(Key);
// 添加节点之前首先要找到要添加的位置,这样就要记住要添加节点的父节点
// 让父节点的左右指向要添加的节点
if (root == null) { // 如果根结点为空,则根节点指向新节点
root = node;
} else {
TreeNode currentNode = root;// 定义当前节点并指向根节点
TreeNode parentNode;
while (true) { // 寻找节点添加的位置
parentNode = currentNode;
if (Key < currentNode.keyValue) {
currentNode = currentNode.leftNode;
if (currentNode == null) { // 当找到空节点的时候,父节点的左节点指向新节点
parentNode.leftNode = node;
return;
}
} else {
currentNode = currentNode.rightNode;
if (currentNode == null) { // 当找到空节点的时候,父节点的右节点指向新节点
parentNode.rightNode = node;
return;
}
}
}
}
}
遍历树:遍历分为中序遍历(最常用,也最有用),前序遍历,后续遍历。
这里就发一个中序遍历的图,理解了这个前序和后续都很好理解。
再看代码
public void display(TreeNode node) {
if (node != null) {
display(node.leftNode);
System.out.println(node.keyValue + ",");
display(node.rightNode);
}
}
最大值、最小值:这个就不用说了,最大值一直往右走,最小值一直往左走。
直接上代码:
public int max() {
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
node = node.rightNode;
}
return parent.keyValue;
}
public int min() {
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
node = node.leftNode;
}
return parent.keyValue;
}
关于删除节点单独发一篇,因为实在太麻烦了。。。
- 大小: 106.1 KB
- 大小: 108.1 KB
- 大小: 90.7 KB
- 大小: 92.7 KB
分享到:
相关推荐
java基础面试题二叉搜索树的后续遍历序列本资源系百度网盘分享地址
JAVA构建二叉搜索树,前序遍历,中序遍历,后序遍历,插入删除节点...
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 将有序数组转换为二叉搜索树的结果肯定是不唯一的,因为存在...
主要介绍了Java二叉搜索树遍历操作,结合实例形式详细分析了Java二叉搜索树前序、中序、后序、层次、广度优先遍历等相关原理与操作技巧,需要的朋友可以参考下
红黑树、二叉平衡树、二叉排序树的java实现,做了泛型封装,可以装任何对象,其中还附带工具类,可以友好一点地打印树,还有各种遍历树方法的递归实现和非递归实现。
530. 二叉搜索树的最小绝对差 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例: 输入: 1 \ 3 / 2 输出: 1 解释: 最小绝对差为 1,其中 2 和 1 的差的绝对值为 ...
java实现二叉查找树的插入、删除、遍历、查询
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。
//cutIndex左边的结点都是根节点的左子树,右边的结点都是根节点的右子树return verify(postorder, first, cutIndex
本文主要介绍了Java实现二叉搜索树的查找、插入、删除、遍历等内容。具有很好的参考价值,下面跟着小编一起来看下吧
669. 修剪二叉搜索树 给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点...
主要介绍了Java删除二叉搜索树最大元素和最小元素的方法,结合实例形式详细分析了java针对二叉搜索树的基本遍历、查找、判断、删除等相关操作技巧,需要的朋友可以参考下
主要介绍了Java删除二叉搜索树的任意元素的方法,结合实例形式详细分析了java这对二叉搜索树的遍历、查找、删除等相关操作技巧与使用注意事项,需要的朋友可以参考下
主要介绍了Java基于二叉查找树实现排序功能,结合实例形式分析了Java二叉查找树的定义、遍历及排序等相关操作技巧,需要的朋友可以参考下
783. 二叉搜索树节点最小距离 给定一个二叉搜索树的根节点 root,返回树中任意两节点的差的最小值。 示例: 输入: root = [4,2,6,1,3,null,null] 输出: 1 解释: 注意,root是树节点对象(TreeNode object),而不是...
BST-遍历GenericTreeEquality.java - 这是一个使用外部迭代器(无递归)执行二叉搜索树遍历的片段。Delegation.java - 这是一个演示继承到委托转换的片段。
BinarySearchTree 节点插入,遍历算法实现和二叉搜索树中的搜索
线程二叉搜索树(Threaded-BST) 回想一下我们的二叉搜索树 (BST) 模型,叶节点都有空指针。 这似乎是浪费空间。 有人建议可以使用这些空指针来引用有用的东西。 在线程二叉搜索树中,节点的右空指针用于指向节点...
24.后序遍历二叉搜索树。25.二叉树中和为某值的路径.26.复杂链表的复制27.二叉搜索树转换为双向链表.28.打印字符串中所有字符的排列29.数组中出现次数超过一半的数字.30.找出最小的K个数31.连续子数组的最大和.32.从...