java数据结构之搜索二叉树
本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下
搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树相同。
代码实现：
public class node {
int data;
public node left, right=null;
public node(int data) {
this.data = data;
}
public node(int data, node left, node right) {
this.data = data;
this.right = right;
this.left = left;
}
//二叉搜索树
public static void insert(node root, node node) {
if (root.data >= node.data) {
if (root.right != null) {
insert(root.right, node);
}else{
root.right=node;
}
} else {
if (root.left != null) {
insert(root.left,node);
}else {
root.left=node;
}
}
}
//前序遍历
public static void before(node root) {
if (root == null) {
return;
}
System.out.println("data:" + root.data);
before(root.left);
before(root.right);
}
//中序遍历
public static void mid(node root) {
if (root == null) {
return;
}
mid(root.left);
System.out.println("data:" + root.data);
mid(root.right);
}
//后序遍历
public static void after(node root) {
if (root == null) {
return;
}
after(root.left);
after(root.right);
System.out.println("data:" + root.data);
}
public static boolean search(int target, node root) {
if(root == null) {
return false;
}
if (root.data > target) {
search(target, root.left);
} else if (root.data < target) {
search(target, root.right);
} else {
return true;
}
return false;
}
}
node.java中：data 节点存放的数据，left，right 左右子节点
before() after() mid()为三种前序遍历，中序遍历，后序遍历。关键方法 insert() search()
insert():参数：root node root为你的根节点，node为你要插入的节点。递归调用insert()当递归到某个节点的右节点为空时表示可以插入数据
流程：
这里有六个节点作为示例：圆中为数据，简单的一个节点。选定3为根节点，随机插入0 2 1 4 5 6
第一步，根节点3，第二步分别插入021 比三大的数跟这个类似，不做展示了。
插入0的时候没有问题，放在3的左边，插入2的时候，递归，2<3,2>0先看当前节点（也就是3）的右边是否有数据，为什么不看当前节点左子节点的数据，因为，当前节点的左子节点一定比当前节点大，所以只找当前节点右边的数据。当右边节点为空的时候，才会插入数据，这样2就插入完成了，现在轮到1了，对于1，跟上面类似..
但是这样会造成一个问题：这样的查找效率很低，对于这样特定的数据，所以要使用平衡二叉树中的旋转，重新选定节点来平衡二叉树。关于二叉树的文章，过几天发布。
主函数：
public class main {
public static void main(String[] args) {
node root = new node(0);
node root1 = new node(2);
node root2 = new node(1);
node root3 = new node(3);
node root4 = new node(4);
node root5 = new node(5);
node root6 = new node(6);
node.insert(root3,root);
node.insert(root3,root2);
node.insert(root3,root1);
node.insert(root3,root4);
node.insert(root3,root5);
node.insert(root3,root6);
node.mid(root3);
boolean i= node.search(10,root3);
System.out.println(i);
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
Java二叉树的四种遍历方式详解
二叉树的四种遍历方式: 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次. 四种遍历方式分别为:先序遍历.中序遍历.后序遍历.层序遍历. 遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法, 首先要声明结点TreeNode类,代码如下: public class TreeNode { public int data; public TreeNode leftC
-
Java实现红黑树(平衡二叉树)的详细过程
目录 前言 红黑二叉查找树 2-3树 2-3树的插入操作 实现红黑二叉树 结尾 前言 在实现红黑树之前,我们先来了解一下符号表. 符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/ 符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap
-
Java数据结构最清晰图解二叉树前 中 后序遍历
目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!
-
带你了解Java数据结构和算法之二叉树
目录 1.树 2.二叉树 3.查找节点 4.插入节点 5.遍历树 6.查找最大值和最小值 7.删除节点 ①.删除没有子节点的节点 ②.删除有一个子节点的节点 ③.删除有两个子节点的节点 ④.删除有必要吗? 8.二叉树的效率 9.用数组表示树 10.完整的BinaryTree代码 11.哈夫曼(Huffman)编码 ①.哈夫曼编码 ②.哈夫曼解码 12.总结 1.树 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个
-
Java中关于二叉树的概念以及搜索二叉树详解
目录 一.二叉树的概念 为什么要使用二叉树? 树是什么? 树的相关术语! 根节点 路径 父节点 子节点 叶节点 子树 访问 层(深度) 关键字 满二叉树 完全二叉树 二叉树的五大性质 二.搜索二叉树 插入 删除 hello, everyone. Long time no see. 本期文章,我们主要讲解一下二叉树的相关概念,顺便也把搜索二叉树(也叫二叉排序树)讲一下.我们直接进入正题吧!GitHub源码链接 一.二叉树的概念 为什么要使用二叉树? 为什么要用到树呢?因为它通常结合了另外两种数据结
-
Java数据结构之平衡二叉树的原理与实现
目录 1 平衡二叉树的概述 2 平衡二叉树的实现原理 2.1 单旋转 2.2 双旋转 2.3 总结 3 平衡二叉树的构建 3.1 类架构 3.2 查找的方法 3.3 检查是否平衡的方法 3.4 插入的方法 3.5 查找最大值和最小值 3.6 删除的方法 4 平衡二叉树的总结 平衡二叉树(AVL树),顾名思义,是一颗很“平衡”的树,它的平衡是相对于排序二叉树来说的.为了避免极端情况下二叉搜索树节点分布不均匀,甚至退化为链表,影响查找效率,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子
-
Java数据结构二叉树难点解析
前言 本章,我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看--二叉树怎们遍历 什么是线索二叉树 首先我们来了解一下什么是线索二叉树? 定义:一个二叉树通过如下的方法"穿起来":所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱. 再看一下为什么要有线索二叉树? 顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快. 线索二叉树能线性地遍历二
-
一篇文章彻底弄懂Java中二叉树
目录 一.树形结构 1.1 相关概念 1.2树的表示形式 1.3树的应用:文件系统管理(目录和文件) 二.二叉树 2.1相关概念 2.2 二叉树的基本形态 2.3 两种特殊的二叉树 2.4 二叉树的性质 2.5 二叉树的存储 2.6 二叉树的基本操作 2.6.1二叉树的遍历 2.6.2 二叉树的基本操作 总结 一.树形结构 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.它具有以下的特点:
-
Java 数据结构中二叉树前中后序遍历非递归的具体实现详解
目录 一.前序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 二.中序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 三.后序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 一.前序遍历 1.题目描述 给你二叉树的根节点 root ,返回它节点值的 前序 遍历. 2.输入输出示例 示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1
-
java数据结构之搜索二叉树
本文实例为大家分享了java数据结构之搜索二叉树的具体代码,供大家参考,具体内容如下 搜索二叉树的定义是:在一个二叉树上,左节点一定比父节点小,右节点一定比父节点大,其他定义跟二叉树相同. 代码实现: public class node { int data; public node left, right=null; public node(int data) { this.data = data; } public node
-
Java数据结构学习之二叉树
1 背景知识:树(Tree) 在之前的笔记中,我们介绍的链表.栈.队列.数组和字符串都是以线性结构来组织数据的.本篇笔记要介绍的树采用的是树状结构,这是一种非线性的数据组织形式. 树结构由节点和边构成,且不存在环.我们曾在线性表型的数据结构中介绍过循环链表和循环队列,这两种数据结构使得存储容器中的元素形成一个闭环,具体可参看"数据结构学习笔记"系列的相关博文,链接贴在下面: 链表:https://www.jb51.net/article/215278.htm 队列:https://ww
-
C++数据结构之搜索二叉树的实现
目录 零.前言 1.概念 2.作用 3.迭代实现 (1)查找 (2)插入 (3)删除 4.递归实现 (1)查找 (2)插入 (3)删除 5.key/value模型的应用 (1)对应查找 (2)判断出现次数 6.总结 零.前言 了解搜索二叉树是为了STL中的map和set做铺垫,我们所熟知的AVL树和平衡搜索二叉树也需要搜索二叉树的基础,本文就来建立一棵搜索二叉树. 1.概念 搜索二叉树又称为二叉排序树,它或者是一棵空树,或者具有如下性质: 1.若其左子树不为空,则左子树上所有节点的值都小于根节点
-
Java 数据结构进阶二叉树题集下
目录 1.对称二叉树 2.创建并遍历二叉树 3.二叉树中两节点最近公共祖先 4.二叉搜索树与双向链表 5.根据前序和中序遍历结果创建二叉树 6.二叉树创建字符串 7.非递归实现二叉树前序遍历 8.非递归实现二叉树后序遍历 1.对称二叉树 [OJ链接] 分为以下几种情况: 二叉树为空,是对称二叉树 二叉树不为空,其左子树或者右子树为空,不是对称二叉树 二叉树不为空,左右子树都为空,是对称二叉树 二叉树不为空,左右子树不为空,左右子节点值不同,不是对称二叉树 二叉树不为空,左右子树不为空,左右子节点
-
Java 数据结构进阶二叉树题集上
目录 1.二叉树的遍历 (1)前.中.后序遍历 (2)层序遍历 2.获取树中子结点的个数 3.获取二叉树的高度 4.判断是不是完全二叉树 5.判断两个树是否相同 6.另一棵树的子树 7.判断平衡二叉树 二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解.(上)中的题偏向于基础,后面(下)中的题机会比较难. 1.二叉树的遍历 (1)前.中.后序遍历 这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码.以前序遍历为例: 如果根节点root为
-
Java数据结构之红黑树的真正理解
真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O
-
Java数据结构学习之树
一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的