数据结构——二叉排序树（Java代码实现）

向右看齐 2023-02-11 12:30 1阅读 0赞

二叉排序树: BST: (Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。  
特别说明:如果有相同的值，可以将该节点放在左子节点或右子节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
创建二叉树添加节点构建排序树且遍历

首先需要构建节点类，存放单个数据。节点类当中实现添加节点的方法和遍历方法。在二叉树类当中根据root节点进行添加和遍历。

class BSTree { 
    	private Node root;
    
    	public void add(Node node) { 
    		if (root == null) { 
    			root = node;
    		} else { 
    			root.add(node);
    		}
    	}
    
    	public void DLR() { 
    		if (root != null) { 
    			root.DLR();
    		} else { 
    			System.out.println("树空，无法遍历");
    		}
    	}
    }
    
    class Node { 
    	int value;
    	Node left;
    	Node right;
    
    	public Node(int value) { 
    		this.value = value;
    	}
    
    	// 添加节点
    	public void add(Node node) { 
    		if (node == null) { 
    			return;
    		}
    		// 当前传入节点和子树节点的关系
    		if (node.value < this.value) { 
    			if (this.left == null) { 
    				this.left = node;
    			} else { 
    				this.left.add(node);
    			}
    		} else { 
    			if (this.right == null) { 
    				this.right = node;
    			} else { 
    				this.right.add(node);
    			}
    		}
    	}
    
    	// 前序遍历
    	public void DLR() { 
    		System.out.println(this);
    		if (this.left != null) { 
    			this.left.DLR();
    		}
    		if (this.right != null) { 
    			this.right.DLR();
    		}
    	}
    
    	@Override
    	public String toString() { 
    		return "Node[value = " + value + "]";
    	}
    }

对代码进行测试：使用上图的数组进行测试，在构建好了的二叉排序树如上图，其前序遍历的结果是：`10,5,2,4,6,8,9,15`

public class BST { 
    	public static void main(String[] args) { 
    		int[] arr = {  10, 5, 6, 2, 4, 8, 9, 15 };
    		BSTree bst = new BSTree();
    		for (int i = 0; i < arr.length; i++) { 
    			bst.add(new Node(arr[i]));
    		}
    		bst.DLR();
    	}
    }

运行记过如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
二叉树删除节点

在删除节点的时候有三种情况：

1.  删除叶子节点  
    1. 找到要删除的节点  
    2. 直接删除节点，把父节点的next指向空（判断next是左右的那个指针）
2.  删除只有一棵子树的节点
3.  删除有俩棵子树的节点

代码实现：在node节点类当中添加俩个方法：

// 找到目标节点
    	public Node search(int value) { 
    		if (this.value == value) { 
    			return this;
    		} else if (value < this.value) { 
    			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 { 
    				System.out.println("该节点没有父节点！");
    				return null;
    			}
    		}
    	}

然后在BSTree类当中编写delete删除的方法。以及node节点类当中的方法进行调用，和一个查找最小值的方法，

public Node search(int value) { 
    		if (root == null) { 
    			System.out.println("空树");
    			return null;
    		} else { 
    			return root.search(value);
    		}
    	}
    
    	public Node searchParent(int value) { 
    		if (root == null) { 
    			return null;
    		} else { 
    			System.out.println("父节点：" + root.searchParent(value));
    			return root.searchParent(value);
    		}
    	}
    
    	public void delete(int value) { 
    		if (root == null) { 
    			return;
    		} else { 
    			Node target = search(value);
    			// 是否找到目标节点
    			if (target == null) { 
    				return;
    			}
    			// 只有一个节点,直接删除这个节点
    			if (root.left == null && root.right == null) { 
    				root = null;
    			}
    			// 查找目标节点的父节点
    			Node targetParent = searchParent(value);
    
    			// 删叶子节点
    			if (target.left == null && target.right == null) { 
    				// 判断目标节点是父节点的左右？
    				if (targetParent.left != null && targetParent.left.value == value) { 
    					targetParent.left = null;
    				}
    				if (targetParent.right != null && targetParent.right.value == value) { 
    					targetParent.right = null;
    				}
    			} else if (target.left != null && target.right != null) { 
    				int minValue = deleteMin(target.right);
    				target.value = minValue;
    			} else { 
    				// 目标节点有左子树
    				if (target.left != null) { 
    					// 目标节点是父节点的左右？
    					if (targetParent != null) { 
    						if (targetParent.left.value == value) { 
    							targetParent.left = target.left;
    						} else { 
    							targetParent.right = target.left;
    						}
    					} else { 
    						root = target.left;
    					}
    				} else { 
    					if (targetParent != null) { 
    						if (targetParent.left.value == value) { 
    							targetParent.left = target.right;
    						} else { 
    							targetParent.right = target.right;
    						}
    					} else { 
    						root = target.right;
    					}
    				}
    			}
    		}
    	}
    
    	public int deleteMin(Node node) { 
    		Node targetNode = node;
    		// 循环查找左子树,会找到最小值
    		while (targetNode.left != null) { 
    			targetNode = targetNode.left;
    			// targetnode指向最小的值
    		}
    		delete(targetNode.value);
    		return targetNode.value;
    	}

进行测试：分别删除不同情况的节点：

public static void main(String[] args) { 
    		int[] arr = {  10, 5, 6, 2, 4, 8, 9, 15 };
    		BSTree bst = new BSTree();
    		for (int i = 0; i < arr.length; i++) { 
    			bst.add(new Node(arr[i]));
    		}
    		// bst.searchParent(8);
    		// bst.search(10);
    		bst.DLR();
    		System.out.println("删除 ：");
    		bst.delete(4); // 删叶子节点 => 10 5 2 6 8 9 15
    		bst.delete(6); // 删只有一棵子树的节点 10 5 2 8 9 15
    		bst.delete(5);// 删除有两棵子树的节点 10 8 2 9 15
    		bst.DLR();
    	}

如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200523204919898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200524111053757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200524184212611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70