二叉排序树介绍

二叉排序树是什么

二叉排序树（Binary Search Tree，BST）是一种二叉树，它的每个节点包含一个关键字和一个值。对于任何一个节点，它的左子树中的所有节点的关键字都小于该节点的关键字，而它的右子树中的所有节点的关键字都大于该节点的关键字。

二叉排序树的主要特点是，它可以支持快速的查找、插入和删除操作。由于二叉排序树的中序遍历是有序的，因此可以方便地进行范围查询和排序操作。

下面是二叉排序树的一些基本性质：

1. 对于任何一个节点，它的左子树中的所有节点的关键字都小于该节点的关键字，而它的右子树中的所有节点的关键字都大于该节点的关键字。
2. 对于任何一个节点，它的左子树和右子树都是二叉排序树。
3. 对于任何一个节点，它的左子树中的最大关键字小于该节点的关键字，它的右子树中的最小关键字大于该节点的关键字。
4. 对于任何一个节点，它的左子树和右子树的高度差不超过1。

二叉排序树的查找、插入和删除操作的时间复杂度取决于树的高度，因此为了保证二叉排序树的平衡，可以使用平衡二叉树（如AVL树、红黑树等）来替代二叉排序树。

代码实现

class binarySearchTree {

    class Node{
      private  int data;
      Node leftChild;
      Node rightChild;

      Node(int value){
        this.data=value;
        leftChild=null;
        rightChild=null;
      }

      public Node getLeftChild(){return leftChild;}
      public Node getRightChild(){return rightChild;}
      public int  getData(){return data;}
      public void setData(int value) {this.data=value;}
      public void setLeftChild(Node left){this.leftChild=left;}
      public void setRightChild(Node right){this.rightChild=right;}
    }

	private Node root;

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

	boolean delete(int value, Node currentNode) {
        if (root == null) {
            return false;
        } 
        Node parent = null; 
        while(currentNode != null && (currentNode.getData() != value)) {
            parent = currentNode;
            if (currentNode.getData() > value)
                currentNode = currentNode.getLeftChild();
            else
                currentNode = currentNode.getRightChild();
        }
        if(currentNode == null) {
            return false;
        }
        else if(currentNode.getLeftChild() == null && currentNode.getRightChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(null);
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
				parent.setLeftChild(null);
                return true;
             }
            else{
                parent.setRightChild(null);
                return true;
            }
        } else if(currentNode.getRightChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(currentNode.getLeftChild());
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
                parent.setLeftChild(currentNode.getLeftChild());
                return true;
            }
            else{
                parent.setRightChild(currentNode.getLeftChild());
                return true;
            }
        }
        else if(currentNode.getLeftChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(currentNode.getRightChild());
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
                parent.setLeftChild(currentNode.getRightChild());
                return true;
            }
            else{
                parent.setRightChild(currentNode.getRightChild());
                return true;
            }
        }
        else {
            Node leastNode = findLeastNode(currentNode.getRightChild());
            int temp = leastNode.getData();
            delete(temp, root);
            currentNode.setData(temp);
            return true;
        }
    }

	private Node findLeastNode(Node currentNode) {
		Node temp = currentNode;
		while (temp.getLeftChild() != null) {
			temp = temp.getLeftChild();
		}
		return temp;
	}

	public boolean add(int value) {

		if (isEmpty()) {
			root = new Node(value);
			return true;
		}

		Node currentNode = root;

		while (currentNode != null) {
			Node leftChild = currentNode.getLeftChild();
			Node rightChild = currentNode.getRightChild();

			if (currentNode.getData() > value) {
				if (leftChild == null) {
					leftChild = new Node(value);
					currentNode.setLeftChild(leftChild);
					return true;
				}
				currentNode = leftChild;
			} else {
				if (rightChild == null) {
					rightChild = new Node(value);
					currentNode.setRightChild(rightChild);
					return true;
				}
				currentNode = rightChild;
			} 
		} 
		return false;
	}

	public boolean isEmpty() {
		return root == null; 
	}

	public void printTree(Node current) {
		if (current == null) return;
		System.out.print(current.getData() + ",");
		printTree(current.getLeftChild());
		printTree(current.getRightChild());

	}
}