二叉树bst删除 删除叶子节点代码
2023-09-14 09:12:09 时间
package tree.bst;
public class bstDemo {
public static void main(String[] args) {
System.out.println("二叉排序树");
BstTree bstTree = new BstTree();
int[] arr = {7,3,10,12,5,1,9,2};
for (int i = 0; i < arr.length; i++) {
bstTree.addNode(new Node(arr[i]));
}
bstTree.infixOrder();
// 删除叶子节点
bstTree.deleteNode(12);
System.out.println("删除后");
bstTree.infixOrder();
}
}
class BstTree
{
private Node root;
public void addNode(Node node)
{
if(root == null){
root = node;
} else {
root.add(node);
}
}
public void infixOrder()
{
if(root == null){
return ;
}
root.infixOrder();
}
public Node search(int value){
if(root == null){
return null;
} else {
return root.search(value);
}
}
public Node searchParent(int value){
if(root == null){
return null;
} else {
return root.searchParent(value);
}
}
public void deleteNode(int value){
if(root == null){
return;
}
// find thi node
Node targetNode = this.search(value);
// 如果没有找到要删除的节点
if(targetNode == null) {
return;
}
// 没有父节点
if(root.left == null && root.right == null){
root = null;
return ;
}
Node parent = searchParent(value);
//叶子节点
if(targetNode.left == null && targetNode.right == null) {
if(parent.left != null && parent.left.value == value){
parent.left = null;
} else if(parent.right != null && parent.right.value == value){
parent.right = null;
}
}
}
}
class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
// find node
public Node search(int value){
if(value == this.value){
return this;
} else if(value < this.value){
// left tree find
if(this.left == null){
return null;
}
return this.left.search(value);
} else {
if(this.right == null){
return null;
}
return this.right.search(value);
}
}
// 查找要删除的节点的父节点
public Node searchParent(int value)
{
if(this.left != null && this.left.value == value
||(this.right!=null && this.right.value==value)){
return this;
} else{
if(value < this.value && this.left !=null){
return this.left.searchParent(value);
} else if(value >=this.value && this.right != null) {
return this.right.searchParent(value);
} else {
return null;
}
}
}
// 添加节点
public void add(Node node){
if(node == null) {
return ;
}
// 添加 left
if(node.value < this.value){
if(this.left == null){
this.left = node;
} else {
this.left.add(node);
}
}
// 添加到right
if(node.value > this.value){
if(this.right == null){
this.right = node;
} else {
this.right.add(node);
}
}
}
// 中序便利
public void infixOrder()
{
if(this.left != null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null){
this.right.infixOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
相关文章
- 二叉树的常见算法
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 226 翻转二叉树
- Java实现 LeetCode 222 完全二叉树的节点个数
- Java实现 LeetCode 222 完全二叉树的节点个数
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- Java实现 LeetCode 94 二叉树的中序遍历
- Lintcode---前序遍历和中序遍历树构造二叉树
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- Leetcode.1379 找出克隆二叉树中的相同节点
- 【数据结构笔记11】数据结构之二叉树的存储结构(顺序存储、二叉链表、三叉链表)
- 面试题 04.03. 特定深度节点链表-二叉树中序遍历反转
- 剑指 Offer 34. 二叉树中和为某一值的路径-dfs法
- 完全二叉树-插入节点并保持仍然是完全二叉树
- [LeetCode] 114. 二叉树展开为链表 ☆☆☆(深度遍历)
- 算法 dfs —— 将二叉树 先序遍历 转为 链表
- 二叉树删除子节点
- 打印二叉树中距离根节点为k的所有节点