java实现二叉搜索树

红太狼 2021-09-24 05:22 295阅读 0赞

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。定义如下

> （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
> （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
> （3）左、右子树也分别为二叉排序树；  
> （4）没有键值相等的结点。

或者说的更简洁一点，就是：**对于每一个节点，它的左节点都比它小，右节点都比它大。**

先创建一个基本的二叉搜索树类

public class BSearch { 
    	private Node rootNode;
    	private class Node { 
    		Node left;
    		Node right;
    		Node parent;
    		int value;
    		public Node(int value, Node parent) { 
    			super();
    			this.value = value;
    			this.parent = parent;
    		}
    	}
    	public void pervPrint() { }
    	public void add() { }
    	public void delete() { }	
    	public void has() { }		
    }

上面的代码创建了一个非常简易的二叉搜索树类。rootNode是根节点，节点为双向的，并提供了前序遍历、插入、删除、查找4个方法。

ps：如果你是来学习如何实现二叉树的，建议只看文字描述，自己写，最后再看我写的。

#### 插入节点 ####

插入节点比较简单，具体做法就是：从根节点开始，根据新插入节点更小/更大，依次向左节点/右节点向下找，找到最后，将新节点插进去。

public boolean add(int newValue) { 
    		if(rootNode == null) { 
    			rootNode = new Node(newValue, null);
    			return true;
    		}
    		Node lastNode = this.findLastNode(newValue);
    		if(newValue == lastNode.value)
    			return false;
    		
    		Node newNode = new Node(newValue, lastNode);
    		if(newValue > lastNode.value) 
    			lastNode.right = newNode;
    		else
    			lastNode.left = newNode;
    		
    		return true;
    	}
    	
    	private Node findLastNode(int e) { 
    		Node temp = rootNode;
    		while(temp != null && temp.value != e) { 
    			if((temp.left == null && temp.right == null) 
    					|| (e > temp.value && temp.right == null)
    					|| (e < temp.value && temp.left == null))
    				return temp;
    			
    			if(e > temp.value)
    				temp = temp.right;
    			else
    				temp = temp.left;
    		}
    		return temp;
    	}

findLastNode还会在我后面的代码中出现几次，它的作用是：输出与输入值相等的节点，若没有相等的，则会输出最接近的点。

#### 前序遍历 ####

public void pervPrint() { 
    		this.pervPrint(this.rootNode);
    		System.out.println();
    	}
    	
    	private void pervPrint(Node node) { 
    		if(node != null) { 
    			System.out.print(node.value + "\t");
    			pervPrint(node.left);
    			pervPrint(node.right);
    		}
    	}

#### 查找 ####

由于findLastNode方法的存在，查找方法简单到只有两行代码

public boolean has(int value) { 
    		Node lastNode = this.findLastNode(value);
    		return !(lastNode == null || lastNode.value != value);
    	}

#### 删除 ####

删除方法是整个算法最麻烦的部分，花的时间比其他所有加一起还多不少。

由于在删除节点后，需要保证二叉树依旧遵循它的特性，需要分情况做处理。

1.  若所删除节点无子节点，直接删除
2.  若删除节点只有单个子节点，则删除节点后需要将它的子节点接到它的位置
3.  若删除节点的左右子节点皆不为空，则删除节点后，将其左子树的最大（最右）节点移到它的位置

注：对于第三种情况，解法不唯一，我只是选用了我认为最简单易懂的方式。

为了便于理解，附上两张图（出处 [https://www.jianshu.com/p/ff4b93b088eb][https_www.jianshu.com_p_ff4b93b088eb]  
）  
![在这里插入图片描述][2020042815462692.png]  
![在这里插入图片描述][20200428154655101.png]

由于是双向节点，移位写的有点难看

private Node findMaxNode(Node root) { 
    		Node temp = root;
    		while(temp.right != null) 
    			temp = temp.right;
    		return temp;
    	}
    	
    	public boolean delete(int value) { 
    		Node lastNode = this.findLastNode(value);
    		if(lastNode == null || lastNode.value != value)//can't find value,return false
    			return false;
    		
    		Node parent = lastNode.parent;
    		if(lastNode.left == null && lastNode.right == null) { //if delete node has no child
    			if(parent != null) { 
    				if(parent.left == lastNode)
    					parent.left = null;
    				else 
    					parent.right = null;
    			}else { 
    				this.rootNode = null;
    			}
    			
    			lastNode = null;
    			
    		}else if(!(lastNode.left != null && lastNode.right != null)) { //if delete node has one child
    			Node next = lastNode.left == null ? lastNode.right : lastNode.left;
    			
    			lastNode.left = null;lastNode.right = null;//lastNode.parent = null;
    			
    			//lastNode = next;
    			next.parent = lastNode.parent;
    			
    			if(parent != null) { 
    				if(lastNode.parent.left == lastNode) { 
    					lastNode.parent.left = next;
    				}else { 
    					lastNode.parent.right = next;
    				}
    			}else { 
    				this.rootNode = next;
    			}
    			
    		}else { //if delete node has two child
    			Node thisLeftNode = lastNode.left;
    			Node leftMaxNode = this.findMaxNode(thisLeftNode);
    			
    			leftMaxNode.left = lastNode.left;
    			leftMaxNode.right = lastNode.right;
    			lastNode.left.parent = leftMaxNode;
    			lastNode.right.parent = leftMaxNode;
    			
    			if(leftMaxNode.parent.left == leftMaxNode) { 
    				leftMaxNode.parent.left = null;
    			}else { 
    				leftMaxNode.parent.right = null;
    			}
    			
    			if(parent != null) { 
    				if(lastNode.parent.left == lastNode) { 
    					lastNode.parent.left = leftMaxNode;
    				}else { 
    					lastNode.parent.right = leftMaxNode;
    				}
    			}else { 
    				this.rootNode = leftMaxNode;
    			}
    			
    			lastNode = null;
    		}
    		
    		return true;
    	}

最后附上完整代码

public class BSearch { 
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		BSearch bs = new BSearch();
    		bs.add(5);
    		bs.add(3);
    		bs.add(9);
    		bs.add(7);
    		bs.add(10);
    		bs.add(6);
    		bs.add(8);
    		bs.pervPrint();
    		System.out.println(bs.has(6));
    		System.out.println(bs.delete(6));
    		bs.pervPrint();
    	}
    	
    	private Node rootNode;
    
    	public void pervPrint() { 
    		this.pervPrint(this.rootNode);
    		System.out.println();
    	}
    	
    	private void pervPrint(Node node) { 
    		if(node != null) { 
    			System.out.print(node.value + "\t");
    			pervPrint(node.left);
    			pervPrint(node.right);
    		}
    	}
    	
    	public boolean add(int newValue) { 
    		if(rootNode == null) { 
    			rootNode = new Node(newValue, null);
    			return true;
    		}
    		Node lastNode = this.findLastNode(newValue);
    		if(newValue == lastNode.value)
    			return false;
    		
    		Node newNode = new Node(newValue, lastNode);
    		if(newValue > lastNode.value) 
    			lastNode.right = newNode;
    		else
    			lastNode.left = newNode;
    		
    		return true;
    	}
    	
    	public boolean has(int value) { 
    		Node lastNode = this.findLastNode(value);
    		return !(lastNode == null || lastNode.value != value);
    	}
    	
    	private Node findLastNode(int e) { 
    		Node temp = rootNode;
    		while(temp != null && temp.value != e) { 
    			if((temp.left == null && temp.right == null) 
    					|| (e > temp.value && temp.right == null)
    					|| (e < temp.value && temp.left == null))
    				return temp;
    			
    			if(e > temp.value)
    				temp = temp.right;
    			else
    				temp = temp.left;
    		}
    		return temp;
    	}
    	
    	private Node findMaxNode(Node root) { 
    		Node temp = root;
    		while(temp.right != null) 
    			temp = temp.right;
    		return temp;
    	}
    	
    	public boolean delete(int value) { 
    		Node lastNode = this.findLastNode(value);
    		if(lastNode == null || lastNode.value != value)//can't find value,return false
    			return false;
    		
    		Node parent = lastNode.parent;
    		if(lastNode.left == null && lastNode.right == null) { //if delete node has no child
    			if(parent != null) { 
    				if(parent.left == lastNode)
    					parent.left = null;
    				else 
    					parent.right = null;
    			}else { 
    				this.rootNode = null;
    			}
    			
    			lastNode = null;
    			
    		}else if(!(lastNode.left != null && lastNode.right != null)) { //if delete node has one child
    			Node next = lastNode.left == null ? lastNode.right : lastNode.left;
    			
    			lastNode.left = null;lastNode.right = null;//lastNode.parent = null;
    			
    			//lastNode = next;
    			next.parent = lastNode.parent;
    			
    			if(parent != null) { 
    				if(lastNode.parent.left == lastNode) { 
    					lastNode.parent.left = next;
    				}else { 
    					lastNode.parent.right = next;
    				}
    			}else { 
    				this.rootNode = next;
    			}
    			
    		}else { //if delete node has two child
    			Node thisLeftNode = lastNode.left;
    			Node leftMaxNode = this.findMaxNode(thisLeftNode);
    			
    			leftMaxNode.left = lastNode.left;
    			leftMaxNode.right = lastNode.right;
    			lastNode.left.parent = leftMaxNode;
    			lastNode.right.parent = leftMaxNode;
    			
    			if(leftMaxNode.parent.left == leftMaxNode) { 
    				leftMaxNode.parent.left = null;
    			}else { 
    				leftMaxNode.parent.right = null;
    			}
    			
    			if(parent != null) { 
    				if(lastNode.parent.left == lastNode) { 
    					lastNode.parent.left = leftMaxNode;
    				}else { 
    					lastNode.parent.right = leftMaxNode;
    				}
    			}else { 
    				this.rootNode = leftMaxNode;
    			}
    			
    			lastNode = null;
    		}
    		
    		return true;
    	}
    	
    	private class Node { 
    		Node left;
    		Node right;
    		Node parent;
    		int value;
    		public Node(int value, Node parent) { 
    			super();
    			this.value = value;
    			this.parent = parent;
    		}
    	}
    	
    }

[https_www.jianshu.com_p_ff4b93b088eb]: https://www.jianshu.com/p/ff4b93b088eb
[2020042815462692.png]: /images/20210923/41cf2a3fb77f424ab623c02fff125d13.png
[20200428154655101.png]: /images/20210923/9758eb994ff246319d6ebea65f10ad90.png