java实现二叉排序树的创建、添加删除结点、遍历等操作

绝地灬酷狼 2023-03-14 10:43 20阅读 0赞

## 源代码 ##

package BinarySortTree;
    
    public class BinarySortTreeDemo { 
    	
    	public static void main(String[] args) { 
    		
    		int[] arr = { 7, 3, 10, 12, 5, 1, 9};
    		BinarySortTree binarySortTree = new BinarySortTree();
    		for(int i = 0; i < arr.length; i++) { 
    			binarySortTree.add(new Node(arr[i]));
    		}
    		System.out.println("删除前:");
    		binarySortTree.infixOrder();
    		binarySortTree.delNode(9);
    		System.out.println("删除后:");
    		binarySortTree.infixOrder();
    	}
    }
    
    class BinarySortTree{ 
    	private Node root;
    	
    	// 添加节点
    	public void add(Node node) { 
    		if(root == null) { 
    			root = node;
    		}else { 
    			root.add(node);
    		}
    	}
    	
    	// 查找要删除的节点 
    	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 delNode(int value) { 
    		// 根结点为空,说明这是一棵空树
    		if(root == null) { 
    			return;
    		}else { 
    			Node target = search(value);
    			// 如果没有查找到该结点,直接返回
    			if(target == null) { 
    				return;
    			}
    			// 如果只有树根
    			if(root.getLeft() == null && root.getRight() == null) { 
    				root = null;
    				return;
    			}
    			
    			Node parent = searchParent(value);
    			// 如果要删除的结点是叶子结点
    			if(target.getLeft() == null && target.getRight() == null) { 
    				// 判断要删除的结点是父结点的左子结点还是右子结点
    				if(parent.getLeft() != null && parent.getLeft().getValue() == value) { 
    					parent.setLeft(null);
    				}else if (parent.getRight() != null && parent.getRight().getValue() == value) { 
    					parent.setRight(null);
    				}
    
    			}
    		}
    	}
    	
    	// 中序遍历 
    	public void infixOrder() { 
    		if(root != null) { 
    			root.infixOrder();
    		}else { 
    			System.out.println("这是一棵空树!");
    		}
    	}
    }
    
    class Node{ 
    	private int value;
    	private Node left;
    	private Node right;
    	
    	public Node(int value) { 
    		this.value = value;
    	}
    	
    	// 查找要删除的结点
    	public Node search(int value) { 
    		if(value == this.value) { 
    			return this;
    		}else if (value < this.value) { 
    			// 如果左子结点为空，说明查找不到了
    			if(this.getLeft() == null) { 
    				return null;
    			}
    			// 否则递归向左查找
    			return this.getLeft().search(value);
    		}else { 
    			if(this.getRight() == null) { 
    				return null;
    			}
    			return this.getRight().search(value);
    		}
    	}
    	
    	// 查找要删除结点的父结点 
    	public Node searchParent(int value) { 
    		if((this.getLeft() != null && this.getLeft().value == value) ||
    				(this.getRight() != null && this.getRight().value == value))
    		{ 
    			return this;
    		}else { 
    			if (this.getLeft() != null && value < this.getValue()) { 
    				return this.getLeft().searchParent(value);
    			}else if(this.getRight() != null && value >= this.getValue()){ 
    				return this.getRight().searchParent(value);
    			}else { 
    				return null;
    			}
    		}
    	}
    	
    	// 添加节点
    	public void add(Node node) { 
    		// 如果比当前节点小，挂到左边
    		if(node.getValue() < this.getValue()) { 
    			if(this.getLeft() == null) { 
    				this.setLeft(node);
    			}else { 
    				// 如果当前节点左边不为空，递归挂到左边的左边
    				this.getLeft().add(node);
    			}
    		}else { 
    			if(this.getRight() == null) { 
    				this.setRight(node);
    			}else { 
    				this.getRight().add(node);
    			}
    		}
    	}
    	
    	// 中序遍历 
    	public void infixOrder() { 
    		if(this.getLeft() != null) { 
    			this.getLeft().infixOrder();
    		}
    		System.out.println(this);
    		if(this.getRight() != null) { 
    			this.getRight().infixOrder();
    		}
    	}
    
    	public int getValue() { 
    		return value;
    	}
    
    	public void setValue(int value) { 
    		this.value = value;
    	}
    	
    	public Node getLeft() { 
    		return left;
    	}
    
    	public void setLeft(Node left) { 
    		this.left = left;
    	}
    
    	public Node getRight() { 
    		return right;
    	}
    	
    	public void setRight(Node right) { 
    		this.right = right;
    	}
    	
    	@Override
    	public String toString() { 
    		return "Node [value=" + value + "]";
    	}
    }