本文将讲述二叉排序树的插入和删除的原理及实现
package com.utils;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 二叉排序树,也可以成为二叉查找树
* 它的性质如下:
* 1.若它的左子树不为空,则左子树上所有的节点均小于其根节点
* 2.若它的右子树不为空,则右子树上所有的节点的值均大于根节点
* 3.它的左右子树也分别为二叉排序树
*
* 简单起见,假设树中元素都实现了Comparable接口或者他们可以按自然顺序比较
*/
public class BinarySortTree<E> {
/**
* 根节点
*/
private Entry<E> root = null;
/**
* 树中元素个数
*/
private int size = 0;
public BinarySortTree(){
}
public int size(){
return size;
}
public E getRoot(){
return root==null?null:root.element;
}
/**
* 查找指定元素element是否在树中存在,如果查找失败确认其添加的位置
* 查找成功直接返回
*
* @param t 表示从此节点开始往下查找
* @param f 保存t的父节点
* @param p 若查找成功p指向此数据元素节点,否则返回查找路径上的最后一个节点
*
* 这是递归实现
*/
private boolean searchBST(Entry<E> t,Object element,Entry<E> f,Entry<E> p){
if(t == null){
p = f;
return false;
}
Comparable<? super E> e = (Comparable<? super E>) element;
int cmp = e.compareTo(t.element);
if(cmp < 0){
return searchBST(t.left,element,t,p);
}else if(cmp > 0){
return searchBST(t.right,element,t,p);
}else{
p = t;
return true;
}
}
/**
*
* 这是非递归实现
*/
private boolean searchBST(Object element,Entry[] p){
Comparable<? super E> e = (Comparable<? super E>) element;
Entry<E> parent = root;
Entry<E> pp = null; //保存parent父节点
while(parent != null){
int cmp = e.compareTo(parent.element);
pp = parent;
if(cmp < 0){
parent = parent.left;
}else if(cmp > 0){
parent = parent.right;
}else{
p[0] = parent;
return true;
}
}
p[0] = pp;
return false;
}
/**
* 首先查找二叉排序树,如果找不到指定元素
* 则插入到二叉树中
*/
public boolean add(E element){
Entry<E> t = root;
if(t == null){ //如果根节点为空
root = new Entry<E>(element,null);
size = 1;
return false;
}
Comparable<? super E> e = (Comparable<? super E>) element;
Entry[] p = new Entry[1] ;
if(!searchBST(element,p)){ //查找失败,插入元素
Entry<E> s = new Entry<E>(element,p[0]);
int cmp = e.compareTo((E) p[0].element);
if(cmp < 0){
p[0].left = s;
}
if(cmp > 0){
p[0].right = s;
}
size++;
return true;
}
return false;
}
/**
* 移除节点,同时调整二叉树使之为二叉排序树
* 实现原理:
* 假设要删除的节点为p,其父节点为f,而p是f的左节点
* 分三种情况讨论:
* 1.若p为叶子节点,直接删除
* 2.若p有只有一个左孩子或者一个右孩子,则删除p,使PL或者PR为f的左子树
* 3.若p的左右子树均不为空,由二叉排序树的特点可知在删除p前,中序遍历此二叉树
* 可以得到一个有序序列,在删去p后为了保持其他元素的相对位置不变,可以这样做:
* 令p的直接前驱(或直接后继)替代p,然后删除其直接前驱或直接后继。其直接前驱可由
* 中序遍历的特点获得
*/
public boolean remove(Object o){
Entry[] p = new Entry[1] ;
if(searchBST(o,p)){ //查找成功,删除元素
deleteEntry(p[0]);
return true;
}
return false;
}
private void deleteEntry(Entry<E> p){
size --;
//如果p左右子树都不为空,找到其直接后继,替换p
if (p.left != null && p.right != null) {
Entry<E> s = successor(p);
p.element = s.element;
p = s;
}
Entry<E> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) { //如果其左右子树有其一不为空
replacement.parent = p.parent;
if (p.parent == null) //如果p为root节点
root = replacement;
else if (p == p.parent.left) //如果p是左孩子
p.parent.left = replacement;
else //如果p是右孩子
p.parent.right = replacement;
p.left = p.right = p.parent = null; //p的指针清空
} else if (p.parent == null) { // 如果全树只有一个节点
root = null;
} else { //左右子树都为空,p为叶子节点
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
/**
* 返回以中序遍历方式遍历树时,t的直接后继
*/
static <E> Entry<E> successor(Entry<E> t) {
if (t == null)
return null;
else if (t.right != null) { //往右,然后向左直到尽头
Entry<E> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else { //right为空,如果t是p的左子树,则p为t的直接后继
Entry<E> p = t.parent;
Entry<E> ch = t;
while (p != null && ch == p.right) { //如果t是p的右子树,则继续向上搜索其直接后继
ch = p;
p = p.parent;
}
return p;
}
}
public Iterator<E> itrator(){
return new BinarySortIterator();
}
//返回中序遍历此树的迭代器
private class BinarySortIterator implements Iterator<E>{
Entry<E> next;
Entry<E> lastReturned;
public BinarySortIterator(){
Entry<E> s = root;
if(s !=null){
while(s.left != null){ //找到中序遍历的第一个元素
s = s.left;
}
}
next = s; //赋给next
}
@Override
public boolean hasNext() {
return next!=null;
}
@Override
public E next() {
Entry<E> e = next;
if (e == null)
throw new NoSuchElementException();
next = successor(e);
lastReturned = e;
return e.element;
}
@Override
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
lastReturned = null;
}
}
/**
* 树节点,为方便起见不写get,Set方法
*/
static class Entry<E>{
E element;
Entry<E> parent;
Entry<E> left;
Entry<E> right;
public Entry(E element,Entry<E> parent){
this.element = element;
this.parent = parent;
}
public Entry(){}
}
//just for test
public static void main(String[] args) {
BinarySortTree<Integer> tree = new BinarySortTree<Integer>();
tree.add(45);
tree.add(24);
tree.add(53);
tree.add(45);
tree.add(12);
tree.add(90);
System.out.println(tree.remove(400));
System.out.println(tree.remove(45));
System.out.println("root="+tree.getRoot());
Iterator<Integer> it = tree.itrator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println(tree.size());
}
}
分享到:
相关推荐
数据结构课程设计作业以二叉排序树实现的教师年终成果管理系统,可读性比较高,包含了二叉排序树中的增删改查的功能实现,并加有基本文件操作,以进行对数据的保存和读取
VC6.0环境下,使用C++/C编写,实现了二叉排序树的基本功能。
二叉排序树实现的学生管理 有创建插入 删除 查找等功能
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. 1)编程实现二叉排序树, 包括生成、...
二叉排序树C语言的简单实现,包含如下操作: 1.创建二叉排序树; 2.销毁二叉排序树; 3.清空二叉排序树; 4.插入指点结点至二叉排序树; 5.删除二叉排序树指点结点; 5.获取二叉排序树指定结点; 6.获取二叉排序树根...
二叉排序树实现 数据结构 c++ 严蔚敏 完全是课本上的
这是数据结构实验中的二叉排序树,能够进行动态查找,将数据插入到二叉排序树中,或者从二叉排序树中删除某个元素。主要是查找功能!
【二叉排序树与文件操作】 功能要求: (1)从键盘输入一组学生记录建立二叉排序树; (2)二叉排序树存盘; (3)由文件恢复内存的二叉排序树; (4)中序遍历二叉排序树; (5)求二叉排序树深度; (6)求二叉...
二叉排序树实现代码二叉排序树实现代码二叉排序树实现代码二叉排序树实现代码二叉排序树实现代码二叉排序树实现代码二叉排序树实现代码
二叉排序树的建立 搜索 插入 删除 遍历 等功能的实现 希望对你有所帮助
可以利用二叉排序数按姓名排序,排序后可实现查找,删除,插入,等操作
在电脑里面不知道哪里翻到的ppt,忘记在哪里下的了……不过看起来还是不错的样子O.O
用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T......
ios编程:实现二叉排序树增删改查。 开发环境:windows下codeblocks。
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不少于10个),建立对应二叉排序树;...(2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
可以创建一个二叉排序树,插入,删除一个节点,计算树的深度,查找一个值,遍历树
二叉排序树补充概念:左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,且二叉排序树左边的数据小于右边。