今天实现的是一个二叉排序树的实现,我只是实现了add和delete的方法,本实现是保证在单核的情况下进行设计的,不考虑多线程的并发状态。所以说,还请见谅,有什么疑问或者能更好的实现方法的,可以与我联系,欢迎大家一起进行探讨。
package com.util.support;
public class Tree {
TreeNode rootNode;
public void addTree(TreeNode node) {
if (node == null)
throw new IllegalArgumentException();
if (rootNode == null)
rootNode = node;
else {
TreeNode parentNode;
TreeNode current = rootNode;
for (;;) {
parentNode = current;
if (current.data > node.data) {
current = current.rightNode;
if (current == null) {
parentNode.rightNode = node;
return;
}
} else if (current.data < node.data) {
current = current.leftNode;
if (current == null) {
parentNode.leftNode = node;
return;
}
} else if (current.data == node.data) {
return;
}
}
}
}
public void add(int data)
{
if (rootNode == null)
rootNode = new TreeNode(data);
else {
TreeNode parentNode;
TreeNode current = rootNode;
for (;;) {
parentNode = current;
if (current.data < data) {
current = current.rightNode;
if (current == null) {
parentNode.rightNode = new TreeNode(data);
return;
}
} else if (current.data > data) {
current = current.leftNode;
if (current == null) {
parentNode.leftNode = new TreeNode(data);
return;
}
} else if (current.data == data) {
return;
}
}
}
}
public void delete(int data) {
NodeInfo info = queryNode(data);
// 开始对该NodeInfo进行分析
//没有找到
if(info.nofound)
return;
else
{
//如果是根节点
if(info.parentNode == null)
{
//根节点不含有左孩子和右孩子
if(rootNode.leftNode == rootNode.rightNode)
{
rootNode = null;
}else if(rootNode.leftNode == null)//左孩子为空
{
TreeNode temp = rootNode;
rootNode = rootNode.rightNode;
temp.rightNode = null;
}else if(rootNode.rightNode == null)
{
TreeNode temp = rootNode;
rootNode = rootNode.leftNode;
temp.leftNode = null;
}else//这一种最为复杂,我们找到左子树中最大的节点,将其进行代替。
{
deleteNodeSpecial(rootNode);
}
}else{
TreeNode node = info.left ? info.parentNode.leftNode:info.parentNode.rightNode;
if(node.leftNode == node.rightNode)
{
if(info.left) info.parentNode.leftNode = null;
else info.parentNode.rightNode = null;
}else if(node.leftNode == null)
{
if(info.left) info.parentNode.leftNode = node.rightNode;
else info.parentNode.rightNode = node.rightNode;
node.rightNode = null;
}else if(node.rightNode == null)
{
if(info.left) info.parentNode.leftNode = node.leftNode;
else info.parentNode.rightNode = node.leftNode;
node.leftNode = null;
}else {
deleteNodeSpecial(node,info);
}
}
}
}
private void deleteNodeSpecial(TreeNode node,NodeInfo info) {
TreeNode parentNode = node;
TreeNode current = parentNode.leftNode;
while(current.rightNode != null)
{
parentNode = current;
current = current.rightNode;
}
current.rightNode = node.rightNode;
if(info.left) info.parentNode.leftNode = node.leftNode;
else info.parentNode.rightNode = node.leftNode;
node.leftNode = null;
node.rightNode = null;
}
private void deleteNodeSpecial(TreeNode node) {
TreeNode parentNode = node;
TreeNode current = parentNode.leftNode;
while(current.rightNode != null)
{
parentNode = current;
current = current.rightNode;
}
//找到最大的节点 current
parentNode.rightNode = null;
//该节点还有左孩子
if(current.leftNode != null)
{
parentNode.rightNode = current.leftNode;
current.leftNode = null;
}
//进行代替
node.data = current.data;
}
private NodeInfo queryNode(int data) {
NodeInfo info = new NodeInfo();
/**
* 是不是头节点
*/
if (rootNode.data == data) {
info.left = false;
info.parentNode = null;
return info;
}
TreeNode parentNode = rootNode;
for (;;) {
if (parentNode.data < data) {
//没有找到
if(parentNode.rightNode == null){
info.nofound = true;
return info ;
}else if(parentNode.rightNode.data == data){
info.left = false;
info.nofound = false;
info.parentNode = parentNode;
return info;
}else{
parentNode = parentNode.rightNode;
}
}else{
if(parentNode.leftNode == null)
{
info.nofound = true;
return info;
}else if(parentNode.leftNode.data == data)
{
info.left = true;
info.nofound = false;
info.parentNode = parentNode;
return info;
}else{
parentNode = parentNode.leftNode;
}
}
}
}
/**
* 记录一个Node的Info
*
* @author Administrator
*
*/
private final class NodeInfo {
TreeNode parentNode;
boolean left = false;
boolean nofound = false;
}
public TreeNode getRootNode() {
return rootNode;
}
}
下面是测试的代码,测试的思想是,我输入无序的数组,依次进行输入到树中,最后如果tree在add完之后,我们使用的是中序的遍历方法,如果中序的遍历方法是有序的话,证明我们的add的方法是正确的。同理,如果我们随意删除一个节点的值,最后进行中序遍历,如果仍然是有序的证明我们仍然正确。
public static void main(String[] args) {
Tree tree = new Tree();
int[] arrays = new int[] { 128, 137, 145, 55, 532, 99, 12, 3, 1000, 255 };
for(int data : arrays)
{
tree.add(data);
}
//System.out.println(tree.getRootNode().getLeftNode().getData());
printBinaryTree(tree.getRootNode());
System.out.println();
tree.delete(532);
printBinaryTree(tree.getRootNode());
}
/**
* 中序遍历二叉树 那么这个二叉树应该是有序的序列
* @param tree
*/
private static void printBinaryTree(TreeNode root) {
if(root != null)
{
printBinaryTree(root.getLeftNode());
System.out.print(root.getData() + " ");
printBinaryTree(root.getRightNode());
}
}
分享到:
相关推荐
数据结构课程设计作业以二叉排序树实现的教师年终成果管理系统,可读性比较高,包含了二叉排序树中的增删改查的功能实现,并加有基本文件操作,以进行对数据的保存和读取
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)进行数据查找和建树过程的比较。
可以创建一个二叉排序树,插入,删除一个节点,计算树的深度,查找一个值,遍历树
二叉排序树补充概念:左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,且二叉排序树左边的数据小于右边。