java学习之—二叉树
2024-10-06 22:54:36
package com.data.java.towtree; import java.io.IOException; /**
* 二叉树
* @Title: uminton
*/ class Node{
public int iData; //数据用作关键值
public double dData; //其他数据
public Node leftChild; //左子节点
public Node rightChild; //右子节点 public Node() {
} public Node(int iData, double dData) {
this.iData = iData;
this.dData = dData;
} public void displayNode(){
System.out.print("{");
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} public class Tree { private Node root; //根节点 public Node getRoot() {
return root;
} /**
* 查找一个数据
* @param key
* @return
*/
public Node find(int key){
Node current = root; //把跟节点设置为当前节点
while (current.iData != key){ //循环查找
if(key < current.iData){ //如果小于就去当前树的左边子节点
current = current.leftChild; //把子节点赋给当前节点
}else { //如果大于就去当前树的右边子节点
current = current.rightChild;//把子节点赋给当前节点
}
if(current == null){ //到达序列的末端没有找到节点，表明他不存在，返回空
return current;
}
}
return current; //循环条件相等，循环结束，找到结果。
} /**
* 添加一个数据
* @param id
* @param dd
*/
public void insert(int id, double dd) {
Node newNode = new Node(id, dd); //先创建一个新节点
if(root == null){ //如果跟节点为空，表示树，没有数据，直接赋值给根节点
root = newNode;
}else {
Node current = root; //根节点赋值给当前节点，用于查找
Node parent; //父节点，用来存储遇到的最后一个不是null的节点，因为curent在查找的过程中会变成null，
// 才能发现发现查找过得上一个节点没有子节点
while (true){ //循环查找
parent = current; //用来存储遇到的最后一个不是null的节点
if (id < current.iData){ //如果小于就去当前树的左边子节点
current = current.leftChild;
if(current == null){ //到达序列的末端没有找到节点，表明他不存在
parent.leftChild = newNode; //把新的节点赋值给父节点的左子节点
return; //直接返回，结束循环
}
}else {
current = current.rightChild;
if(current == null){
parent.rightChild = newNode;
return;
}
}
}
}
} /**
* 删除一个数据
* @param key
* @return
*
* 删除节点要考虑的三种情况
* 1，该节点是叶节点
* 2，该节点有一个子节点
* 3，该节点有二个子节点
*/
public boolean delete(int key){
Node current = root;
Node parent = root;
boolean isLeftChild = true; //记录是左节点还是右节点
while(current.iData != key){ //循环为了找到要删除的节点，循环条件如果相等就是找到了，退出循环
parent = current; //保存要删除的父节点
if(key < current.iData){
isLeftChild = true;
current = current.leftChild;
}else {
isLeftChild = false;
current = current.rightChild;
}
if(current == null){ //查找到末端，都没有找到，返回false
return false;
}
}
/**************************情况1开始*********************************/
if(current.leftChild == null && current.rightChild == null) { //判断是否没有子节点，也就是该节点是叶节点
if (current == root) { //如果是根节点，直接赋值为null
root = null;
} else if (isLeftChild) { //判断是否是左节点
parent.leftChild = null; //用上面保存的父节点找子节点，直接赋值为null
} else {
parent.rightChild = null;
}
/**************************情况1结束*********************************/ /**************************情况2开始*********************************/
}else if (current.rightChild == null){ //判断左边等null或右边等于null
if(current == root){ //如果是根节点，直接赋值为null
root = current.leftChild;
}else if (isLeftChild){ //判断是否是左节点
parent.leftChild = current.leftChild;//用上面保存的父节点找子节点，直接赋值为null
}else {
parent.rightChild = current.leftChild;
}
}else if (current.leftChild == null){ //下面同理
if(current == root){
root = current.rightChild;
}else if (isLeftChild){
parent.leftChild = current.rightChild;
}else {
parent.rightChild = current.rightChild;
}
/**************************情况2结束*********************************/ /**************************情况3开始*********************************/
}else { //上面都不成立，表明该节点有两个子节点。
Node successor = getSuccessor(current); //取得后继者
if(current == root){ //如果是根节点，直接赋值为后继者
root = successor;
}else if (isLeftChild){ //判断是否是左节点
parent.leftChild = successor; //用上面保存的父节点找子节点，直接赋值为后继者
}else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
/**************************情况3结束*********************************/
return true;
} /**
* 中序遍历树
* @param localRoot
*/
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData);
inOrder(localRoot.rightChild);
}
} /**
* 查找最小值
* @return
*/
public Node minNumber(){
Node current = root;
Node last = null;
while (current != null){
last = current;
current = current.leftChild;
}
return last;
} /**
* 获取删除节点的后继者
* @param delNode
* @return
* 算法：程序找到要删除的节点的右子节点，（它的关键字值一定比要删除的节点的值大）然后转到右子节点的左子节点（若果有的话）
* 然后到这个左子节点的左子节点，以此类推，这个路径的最后一个左子节点就是要删除节点的后继者
* 若果删除节点右子节点没有左子节点，它就是后继者
*/
private Node getSuccessor(Node delNode) {
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; //删除节点右子节点
while (current != null){
successorParent = successor; //保留后继者的父节点
successor = current; //后继者
current = current.leftChild; //循环查找左子节点
}
if(successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
} class TreeApp{
public static void main(String[] args) throws IOException {
Tree treTree = new Tree();
treTree.insert(38,1.5);
treTree.insert(65,1.5);
treTree.insert(40,1.5);
treTree.insert(50,1.5);
treTree.insert(55,1.5);
treTree.insert(30,1.5);
treTree.insert(90,1.5);
treTree.insert(25,1.6);
treTree.insert(70,1.7);
treTree.insert(20,1.7);
treTree.insert(80,1.7); treTree.delete(65); }
}
最后删除有点复杂，没怎么搞懂见谅。
最新文章
- Redis数据结构详解(一)
- 找回消失的ASUS显卡
- SVN学习安装总结
- 【转】深入PHP FTP类的详解
- 《Java程序员面试宝典》读书笔记1
- LFS: Interface eth0 doesn't exist
- Java反射机制深度剖析
- 【19道XSS题目】不服来战！
- 源码浅谈(二)：java中的 Integer.parseInt(String str)方法
- Codeforces1153F Serval and Bonus Problem 【组合数】
- Sprint 冲刺第三阶段第二天
- atcoder A - Frog 1（DP）
- 搭建HBase+thrift+php环境
- 对事件委托绑定click的事件的解绑
- spring @Transactional 声明式事务
- [6] 胶囊体(Capsule)图形的生成算法
- 征信接口调用，解析（xml）
- Flask实战第57天：UEditor编辑器集成以及配置上传文件到七牛
- js实现选项卡切换
- 成都夏季招聘会IT行业缺口大！
热门文章
- c++ STL之unordered_map
- [Feature] Compare the effect of different scalers
- kettle记录集(Merge Join)使用
- Servlet(2)：Requset/Response Encoding and Filter
- TypeScript01 编译环境的搭建、字符串特性、类型特性
- B. Grow The Tree Codeforces Round #594 (Div. 2)
- 【计算机】hosts设置
- day22 subprocess、configeparser、表格操作模块
- WijmoJS 中自定义 React 菜单和列表项模板
- STL pair 常见用法详解