本程序实现了基本的对排序二叉树的增和删。
public class SortTreeTest {
public static void main(String[] args) {
SortTree tree = new SortTree(10); // 初始化一个root并且给一个value
tree.add(7);
tree.add(15);
tree.add(12);
tree.add(16);
tree.add(7);
tree.add(8);
tree.add(4);
tree.add(13);
tree.read();
System.out.println("root.value = " + tree.getRoot().getValue());
tree.delete(10);
System.out.println("---------after delete---------");
tree.read();
System.out.println("root.value = " + tree.getRoot().getValue());
}
}
class SortTree {
private Node root;
private int size;
public SortTree(int v) {
root = new Node(v);
size = 1;
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int Size() {
return size;
}
public void add(int value) {
if (root == null)
return;
Node indexRoot = getRoot();
Node parent = indexRoot;
int indexValue = 0;
while (indexRoot != null) {
indexValue = indexRoot.getValue();
parent = indexRoot;
if (value < indexValue) {
indexRoot = indexRoot.getLeft();
} else if (value > indexValue) {
indexRoot = indexRoot.getRight();
} else {
return;
}
}
Node newNode = new Node(value);
if (value < indexValue) {
parent.setLeft(newNode);
} else if (value > indexValue) {
parent.setRight(newNode);
} else {
return;
}
newNode.setParent(parent);
size++;
}
public void read() { // 中序遍历
read(root);
}
public void read(Node node) {
if (node.getLeft() != null) {
read(node.getLeft());
}
if (node != null) {
System.out.println(node.getValue());
}
if (node.getRight() != null) {
read(node.getRight());
}
}
public void delete(int value) {
if (root == null)
return;
Node indexRoot = getRoot();
Node parent = indexRoot;
int indexValue = indexRoot.getValue();
while (indexValue != value && indexRoot != null) {
parent = indexRoot;
if (value < indexValue) {
indexRoot = indexRoot.getLeft();
} else if (value > indexValue) {
indexRoot = indexRoot.getRight();
}
if (indexRoot != null) {
indexValue = indexRoot.getValue();
}
}
if (indexRoot == null) {
return;
}
// no any nodes
if (indexRoot.getLeft() == null && indexRoot.getRight() == null) {
if (parent.getLeft() == indexRoot) { // if is leftNode
parent.setLeft(null);
} else { // if is rightNode
parent.setRight(null);
}
return;
}
// has only left node
if (indexRoot.getLeft() != null && indexRoot.getRight() == null) {
if (indexRoot == this.getRoot()) { // if deleted is root
setRoot(indexRoot.getLeft());
indexRoot = null;
} else {
parent.setLeft(indexRoot.getLeft());
indexRoot.getLeft().setParent(parent);
indexRoot = null;
}
return;
}
// has only right node
if (indexRoot.getLeft() == null && indexRoot.getRight() != null) {
if (indexRoot == this.getRoot()) { // if deleted is root
setRoot(indexRoot.getRight());
indexRoot = null;
} else {
parent.setRight(indexRoot.getRight());
indexRoot.getRight().setParent(parent);
indexRoot = null;
}
return;
}
// has two node
if (indexRoot.getLeft() != null && indexRoot.getRight() != null) {
// 找到删除节点的后继节点
Node afterNode = indexRoot.getRight();
Node afterFather = indexRoot;
while (afterNode.getLeft() != null) {
afterFather = afterNode;
afterNode = afterNode.getLeft();
}
if (afterFather == indexRoot) {
parent.setRight(afterNode);
afterNode.setParent(parent);
afterNode.setLeft(indexRoot.getLeft());
indexRoot.getLeft().setParent(afterNode);
if (indexRoot == this.getRoot()) { //if delete is root
setRoot(afterNode);
}
} else {
//比较复杂
if(afterNode.getRight()!= null) {
afterFather.setLeft(afterNode.getRight());
afterNode.getRight().setParent(afterFather);
}else {
afterFather.setLeft(null);
}
afterNode.setRight(indexRoot.getRight());
indexRoot.getRight().setParent(afterNode);
parent.setRight(afterNode);
afterNode.setParent(parent);
afterNode.setLeft(indexRoot.getLeft());
indexRoot.getLeft().setParent(afterNode);
if(indexRoot == this.getRoot()) {
this.setRoot(afterNode);
}
}
indexRoot = null;
}
}
}
忘记了放Node类,补上。
//Node类
public class Node {
private Node left;
private Node right;
private int value;
private Node parent;
public Node(int v) {
this.value = v;
}
public Node() {
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
}
输出:
4
7
8
10
12
13
15
16
root.value = 10
---------after delete---------
4
7
8
12
13
15
16
root.value = 12
分享到:
相关推荐
java使用jtree动态实现二叉树,包含二叉树的插入删除很查找
java基础笔记数据结构-排序二叉树,详细描述了排序二叉树的原理及其实现方式,基础数据结构。
java 常见排序算法的实现 有冒泡、选择、快速、比较等常见的排序算法 还包括二叉树的实现
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
排序二叉树 AVL树 哈夫曼树增删改查Java实现
说明: 可实现:构造树,插入,查找,删除. 通过模式的选择,可以插入值相等的点.但是不建议使用.
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构,还实现了多种排序算法。并且是在J2EE下实现的。
Java基础复习笔记10数据结构-排序二叉树。
分别采用二叉链表和顺序表作存储结构,实现对二叉排序树与平衡二叉树的操作。 重庆理工大学,软件工程系,课程设计。
java编写的二叉树的各种操作,其中包括二叉排序树和平衡二叉树的各项操作,用于学习数据结构,可以运行
/*建立一个排序二叉树*/ if(*p0==NULL) { p1=(struct tree *)malloc(sizeof(struct tree)); p1->num=x;p1->Lchild=NULL;p1->Rchild=NULL; *p0=p1; } else { if(x<(*p0)->num) { insert(&((*p0)-...
用Java实现的堆排序算法,二叉树转换为堆,然后排序
arithmetic java算法冒泡排序、二叉树、数组、链表、队列学习简单示例 private static void mpSoft(String [] data) { for (int i = 0; i ; i++) { System.out.println(Arrays.toString(data)); for (int j = 0; ...
java课程实验,二叉树开发,swing,jtree实现图形界面,功能:二叉树的创建、查找、插入、删除
java中常见排序的所有demo,包含冒泡,选择,插入,快速,堆,希尔,二叉树等
数据结构课设,用c语言编写的单链表, 表达式求值, 二叉树 ,二叉排序树 ,Huffman编码,五个做成菜单,只有一个main函数
排序二叉树的基础代码,包含递归非递归二叉树构建、递归非递归遍历,获取最小最大值。
java常用的排序算法 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序,含鸡尾排序。以及二叉树和拓扑结构!