数据结构_二叉排序树（BST）

ゝ一纸荒年。 2023-07-11 15:20 18阅读 0赞

### 文章目录 ###

*  介绍
 *   *  定义节点
     *  定义二叉树
 *  新增节点
 *   *  思路
     *  代码实现
 *  遍历
 *  删除
 *   *  思路
     *   *  删除叶子节点
         *  删除只有一颗子树的节点
         *  删除有两颗子树的节点
     *  代码实现
     *   *  查找节点
         *  查找父节点
         *  删除

# 介绍 #

BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

## 定义节点 ##

public class Node {
        
    	int val;
    	Node left;
    	Node right;
    
    	public Node(int val) {
        
    		super();
    		this.val = val;
    	}
    
    	@Override
    	public String toString() {
        
    		return "Node [val=" + val + "]";
    	}
    }

## 定义二叉树 ##

public class BinarySortTree {
        
    
    	private Node root;
    
    	public Node getRoot() {
        
    		return root;
    	}
    
    	public void setRoot(Node root) {
        
    		this.root = root;
    	}
    }

# 新增节点 #

## 思路 ##

判断新添加节点的值与当前节点值的大小，小向左节点递归，否则右节点递归

## 代码实现 ##

/**
     * 添加节点
     * @param val
     */
    public void add(int val) {
        
    	if (val < this.val) {
        
    		if (this.left == null) {
        
    			this.left = new Node(val);
    		} else {
        
    			this.left.add(val);
    		}
    	} else {
        
    		if (this.right == null) {
        
    			this.right = new Node(val);
    		} else {
        
    			this.right.add(val);
    		}
    	}
    }

/**
     * 添加节点
     * @param val
     */
    public void add(int val) {
        
    	if (root == null) {
        
    		root = new Node(val);
    	} else {
        
    		root.add(val);
    	}
    }

# 遍历 #

中序遍历

/**
     * 中序遍历
     */
    public void infixOrder() {
        
    	if (this.left != null) {
        
    		this.left.infixOrder();
    	}
    	System.out.println(this);
    	if (this.right != null) {
        
    		this.right.infixOrder();
    	}
    }

/**
     * 中序遍历
     */
    public void infixOrder() {
        
    	if (root != null) {
        
    		root.infixOrder();
    	} else {
        
    		System.out.println("null");
    	}
    }

# 删除 #

## 思路 ##

### 删除叶子节点 ###

1.  先找到要删除的结点target
2.  找到target父结点 parent
3.  确定 target是 parent的左子结点还是右子结点
4.  根据前面的情况来对应删除  
    左子结点 parent.left = null  
    右子结点 parent.right = null;

### 删除只有一颗子树的节点 ###

1.  先找到要删除的结点target
2.  找到target的父结点parent
3.  确定target的子结点是左子结点还是右子结点
4.  确定target是parent 的左子结点还是右子结点
5.  如果target有左子结点
    
    1.  如果 target是 parent 的左子结点  
        parent.left = targetNode.left;
    2.  如果 target是 parent 的右子结点  
        parent.right = targetNode.left;
6.  如果target有右子结点
    
    1.  如果 target是 parent 的左子结点  
        parent.left = targetNode.right;
    2.  如果 target是 parent 的右子结点  
        parent.right = targetNode.right
7.  如果target没有parent，是target左节点或右节点为root

### 删除有两颗子树的节点 ###

1.  先找到要删除的结点target
2.  找到target的父结点parent
3.  从target的右子树找到最小的结点
4.  用一个临时变量，将最小结点的值保存
5.  删除该最小结点
6.  target.value = temp

## 代码实现 ##

### 查找节点 ###

/**
     * 查找节点
     * @param val
     * @return
     */
    public Node searchTarget(int val) {
        
    	if (val == this.val) {
        
    		return this;
    	}
    	if (this.left != null && val < this.val) {
        
    		return this.left.searchTarget(val);
    	}
    	if (this.right != null && val >= this.val) {
        
    		return this.right.searchTarget(val);
    	}
    	return null;
    }

/**
     * 查找节点
     * @param val
     * @return
     */
    public Node searchTarget(int val) {
        
    	if (root == null) {
        
    		return null;
    	}
    	return root.searchTarget(val);
    }

### 查找父节点 ###

/**
     * 查找节点的父节点
     * @param val
     * @return
     */
    public Node searchParent(int val) {
        
    	if ((this.left != null && this.left.val == val) || 
    	(this.right != null && this.right.val == val)) {
        
    		return this;
    	}
    	if (this.left != null && val < this.val) {
        
    		return this.left.searchParent(val);
    	}
    	if (this.right != null && val >= this.val) {
        
    		return this.right.searchParent(val);
    	}
    	return null;
    }

/**
     * 查找父节点
     * @param val
     * @return
     */
    public Node searchParent(int val) {
        
    	if (root == null) {
        
    		return null;
    	}
    	return root.searchParent(val);
    }

### 删除 ###

/**
     * 删除节点
     * @param value
     */
    public void del(int val) {
        
    	if (root == null) {
        
    		return;
    	}
    	//查找删除节点，并判断是否存在
    	Node target = searchTarget(val);
    	if (target == null) {
        
    		return;
    	}
    	//如果只有root一个节点
    	if (root.left == null & root.right == null) {
        
    		root = null;
    		return;
    	}
    	//查找删除节点父节点
    	Node parent = searchParent(val);
    	//删除节点为叶子节点
    	if (target.left == null && target.right == null) {
        
    		if (parent.left != null && parent.left == target) {
        
    			parent.left = null;
    		} else {
        
    			parent.right = null;
    		}
    		//删除有两个子节点的节点
    	} else if (target.left != null && target.right != null) {
        
    		Node temp = target.right;
    		while (temp.left != null) {
        
    			temp = temp.left;
    		}
    		del(temp.val);
    		target.val = temp.val;
    	} else {
         //删除有一个叶子节点的节点
    		if (target.left != null) {
        
    			if (parent != null) {
        
    				if (parent.left == target) {
        
    					parent.left = target.left;
    				} else {
        
    					parent.right = target.left;
    				}
    			} else {
        
    				root = target.left;
    			}
    		} else {
        
    			if (parent != null) {
        
    				if (parent.left == target) {
        
    					parent.left = target.right;
    				} else {
        
    					parent.right = target.right;
    				}
    			} else {
        
    				root = target.right;
    			}
    		}
    	}
    }