二叉查找树是对树的一个经典的应用,下面使用Java实现对二叉查找树的各种实现,其中私有方法使用递归实现,然后公有方法调用私有方法,下面上代码
首先是作为二叉树的节点的类
package com.bird.four;
/**
* @category 二叉查找树的节点
* @author Bird
*
*/
public class BinaryNode {
Comparable<Object> element;//节点存储的数据
BinaryNode left;//二叉树的左孩子
BinaryNode right;//二叉树的右孩子
BinaryNode(Comparable<Object> theElement){
this(theElement,null,null);
}
BinaryNode(Comparable<Object> theElement, BinaryNode lt, BinaryNode rt){
element = theElement;
left = lt;
right = rt;
}
}
下面是二叉查找树的实现
package com.bird.four;
/**
* @category 二叉查找树的实现
* @author Bird
*
*/
public class BinarySearchTree {
private BinaryNode root;//二叉树的根节点
public BinarySearchTree(){
root = null;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
private Comparable<Object> elementAt(BinaryNode t){
return t == null ? null : t.element;
}
/**
*
* @param x 需要查找的数据域
* @param t 初始为根节点,递归表示各个节点
* @return 找到的节点的引用
*/
private BinaryNode find(Comparable<Object> x, BinaryNode t){
if(t == null)
return null;
if(x.compareTo(t.element) < 0)
return find(x,t.left);
else if(x.compareTo(t.element) > 0)
return find(x,t.right);
else
return t;
}
/**
* 寻找最小的节点直接一次向左递归就可以
* @param t
* @return
*/
private BinaryNode findMin(BinaryNode t){
if(t == null)
return null;
else if(t.left == null)
return t;
return findMin(t.left);
}
/**
* 同理,求最大值只需向右,但是不用递归
* @param t
* @return
*/
private BinaryNode findMax(BinaryNode t){
if(t != null)
while(t.right != null)
t = t.right;
return t;
}
/**
* 插入算法的实现,递归找到位置后插入
* @param x
* @param t
* @return
*/
private BinaryNode insert(Comparable<Object> x, BinaryNode t){
if(t == null)
t = new BinaryNode(x,null,null);
else if(x.compareTo(t.element) < 0)
t.left = insert(x,t.left);
else if(x.compareTo(t.element) > 0)
t.right = insert(x,t.right);
else
;
return t;
}
/**
* 删除算法,其实现在使用懒惰删除,就是将需要删除的节点给一个标记
* @param x
* @param t
* @return
*/
private BinaryNode remove(Comparable<Object> x, BinaryNode t){
if(t==null)
return t;
if(x.compareTo(t.element) < 0)
t.left = remove(x,t.left);
else if(x.compareTo(t.element) > 0)
t.right = remove(x,t.right);
else if(t.left != null && t.right != null){//有两个孩子
t.element = findMin(t.right).element;
t.right = remove(x,t.right);
}
else
t = (t.left != null) ? t.left : t.right;
return t;
}
private void printTree(BinaryNode t){
if(t != null){
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
public Comparable<Object> find(Comparable<Object> x){
return elementAt(find(x,root));
}
public Comparable<Object> findMin(){
return elementAt(findMin(root));
}
public Comparable<Object> findMax(){
return elementAt(findMax(root));
}
public void insert(Comparable<Object> x){
root = insert(x,root);
}
public void remove(Comparable<Object> x){
root = remove(x,root);
}
public void printTree(){
printTree(root);
}
}
分享到:
相关推荐
Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...
内容简介《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
11.4.4 时间界的证明 11.5 伸展树 小结 练习 参考文献 第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下删除 12.3 确定性跳跃...
数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将...
课程内容第一章: 数据结构与算法概述; 算法分析; 冒泡排序; 选择排序; 插入排序; 希尔排序; 归并排序;第二章: 快速排序; 排序稳定性分析; 顺序表; 链表;第三章: 栈; 队列; 符号表; 二叉查找树;第...
.算法与数据结构基本概念 (1)数据、数据对象和数据结构 ...6.算法分析与设计基础 (1)分治与递归的关系 (2)贪心算法的思想 (3)回溯与分支限界算法的比较 (4)算法时间和空间复杂度的简单分析
Java数据结构试题及解析 1 下列数据结构中,能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析:二分法查找只适用于顺序存储的有序表。在此所说的有序表是指...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼...
5.7 二叉查找树 5.8 选拔树 5.9 森林 5.10 不相交集合的表示 5.11 二叉树的计数 5.12 参考文献和选读材料 第6章 图 6.1 图的抽象数据类型 6.2 图的基本操作 6.3 最小代价生成树 6.4 最短路径和迁移闭包 ...
数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角...
1.4 算法分析 108 1.4.1 科学方法 108 1.4.2 观察 108 1.4.3 数学模型 112 1.4.4 增长数量级的分类 117 1.4.5 设计更快的算法 118 1.4.6 倍率实验 121 1.4.7 注意事项 123 1.4.8 处理对于输入的...
1.4 算法分析 108 1.4.1 科学方法 108 1.4.2 观察 108 1.4.3 数学模型 112 1.4.4 增长数量级的分类 117 1.4.5 设计更快的算法 118 1.4.6 倍率实验 121 1.4.7 注意事项 123 1.4.8 处理对于...
《数据结构与算法分析-Java语言描述 第二版》 《Java数据结构和算法.(中文第二版)》 《算法导论中文版》 《剑指Offer》 练习题 经典算法大全 leetcode 学习进度 ####递归 递归 cn.diyai.recursion.Recursion ...