4.3 二叉排序树

简介

1. 二叉排序树的构造
2. 查找二叉排序树中的对应节点
3. 删除二叉排序树中的某一节点

代码

/*** 二叉排序树（binary sort tree BST）* 1. 构造二叉排序树* 2. 查找对应节点* 3. 删除二叉树节点* （1）删除叶子节点* （2）删除只有一棵子树的节点* （3）删除有两棵子树的节点* @author dxt**/
public class BinarySortTreeDemo {
    public static void main(String[] args) {
    int[] arr = {
    6, 3, 5, 1, 2, 9, 7};/** 6* / \* 3 9* / \ / * 1 5 7 * \ * 2*///1. 依据数组数据构造一棵二叉排序树BinarySortTree bst = new BinarySortTree();for(int i=0; i<arr.length; i++) {
    bst.add(new Node(arr[i]));}//2. 中序遍历二叉排序树System.out.println("中序遍历：");bst.infixOrder();System.out.println("前序遍历：");//3. 前序遍历二叉排序树bst.preOrder();//4. 测试删除节点System.out.println("测试删除节点：");bst.deleteNode(6);bst.infixOrder();//测试2int[] arr2 = {
    1, 2, 3, 4, 5};BinarySortTree bst2 = new BinarySortTree();for(int i=0; i<arr2.length; i++) {
    bst2.add(new Node(arr2[i]));}System.out.println("中序遍历：");bst2.infixOrder();System.out.println("前序遍历");bst2.preOrder();bst2.deleteNode(1);System.out.println("中序遍历：");bst2.infixOrder();}
}
/*** 二叉排序树* @author dxt**/
class BinarySortTree{
    private Node root;//构造二叉排序树public void add(Node node) {
    if(root == null) {
    root = node;}else {
    root.add(node);}}//中序遍历public void infixOrder() {
    if(root == null) {
    System.out.println("二叉排序树为空");return;}//中序遍历root.infixOrder();}//前序遍历public void preOrder() {
    if(root == null) {
    System.out.println("二叉排序树为空");return;}root.preOrder();}//查找节点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);}}/*** 返回以 node 为根节点的二叉排序树中 最小节点 的值，并删除此最小节点* @param node* @return*/public int delRightTreeMin(Node node) {
    Node target = node;//循环查找左节点while(target.left != null){
    target = target.left;}int value = target.value;this.deleteNode(value);	//删除最小节点return value;}/*** 删除节点* 1. 删除叶子节点* （1）找到 待删除的节点* （2）找到 此节点的父节点* （3）判断 待删除的节点 是其父节点的 左子节点 还是 右子节点，将对应子节点置空* 2. 删除只有一棵子树的节点* （1）找到 待删除的节点 targetNode* （2）找到 此节点的父节点 parent* （3）判断 targetNode 是 parent 的 左子节点 还是 右子节点* 如果是 左子节点* [1] 如果 targetNode 的 子树 是 左子树* parent.left = targetNode.left* [2] 如果 targetNode 的 子树 是 右子树* parent.left = targetNode.right* 如果是 右子节点* [1] 如果 targetNode 的 子树 是 左子树* parent.right = targetNode.left* [2] 如果 targetNode 的 子树 是 右子树* parent.right = targetNode.right* 3. 删除有两棵子树的节点* （1）找到 待删除的节点 targetNode* （2）找到 此节点的父节点 parent* （3）从 targetNode 的 右子树中找 最小的节点，使用临时变量 temp 保存此最小节点的值* （4）删除这个最小节点(最小节点肯定是叶子节点，即删除叶子节点)* （5）设置 targetNode的值为temp* 4. 某些特殊情况处理* （1）树为空* （2）删除的节点为根节点* @param value 删除值为value的节点*/public void deleteNode(int value) {
    if(this.root == null) {
    return;}else {
    //1. 需要先去找到要删除的节点Node targetNode = this.search(value);//如果没有找到要删除的节点，直接返回if(targetNode == null) {
    return;}//2.1 当BST只有一个节点（left==null && right==null）且程序执行到此处时，说明要删除的节点是根节点if(root.left == null && root.right == null) {
    root = null;return;}//如果要删除的节点是根节点，且根节点有两棵子树，这种情况会第3步中，第二个判断分支中被实现//如果要删除的节点是根节点，且此根节点 只有左子树 或 只有右子树// !(root.left != null && root.right != null) 表示有一个子节点不为空，或两个子节点都为空，但两个子节点//都为空的情况我们已经在之前进行判断了if(targetNode == root && !(root.left != null && root.right != null)) {
    if(root.left != null) {
    root = root.left;}else {
    root = root.right;}return;}//2.2 找到要删除节点的父节点（不是根节点，就会有父节点）Node parent = this.searchParent(value);//3 叶子节点 双子树节点 单子树节点if(targetNode.left == null && targetNode.right == null) {
    	//叶子节点//判断targetNode是父节点的左子节点还是右子节点if(parent.left != null && parent.left.value == value) {
    	//左子节点parent.left = null;}else if(parent.right != null && parent.right.value == value){
    parent.right = null;}}else if(targetNode.left != null && targetNode.right != null) {
    	//要删除的节点有 左 右 两棵子树//对于int min = this.delRightTreeMin(targetNode.right);targetNode.value = min;}else {
    	//排除了叶子节点 和 有两棵子树的节点，此条件下targetNode只有一棵子树//如果targetNode 是 parent 节点的 左子节点if(parent.left.value == value) {
    //如果targetNode的子树是左子树if(targetNode.left != null) {
    parent.left = targetNode.left;}else if(targetNode.right != null) {
    parent.left = targetNode.right;}}else if(parent.right.value == value){
    	//如果targetNode是parent节点的右子节点//如果targetNode的子树是左子树if(targetNode.left != null) {
    parent.right = targetNode.left;}else if(targetNode.right != null) {
    	//是右子树parent.right = targetNode.right;}}}}}
}
/*** 节点类* @author dxt**/
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 infixOrder() {
    if(this.left != null) {
    this.left.infixOrder();}System.out.println(this);if(this.right != null) {
    this.right.infixOrder();}}//前序遍历, 中序输出 和 前序输出 可以唯一确定一棵二叉树public void preOrder() {
    System.out.println(this);if(this.left != null) {
    this.left.preOrder();}if(this.right != null) {
    this.right.preOrder();}}//查找节点,即查找节点值位value的节点public Node search(int value) {
    if(value == this.value) {
    return this;}else if(value < this.value) {
    	//向左子树进行查找if(this.left != null) {
    return this.left.search(value);}else {
    return null;}}else {
    if(this.right != null) {
    return this.right.search(value);}else {
    return null;}}}//查找一个节点的父节点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;}}}@Overridepublic String toString() {
    return "Node: " + this.value;}
}