二分搜索树及其遍历(Java)

矫情吗；* 2023-07-01 14:55 83阅读 0赞

# 二分搜索树 #

*  二分搜索树是一颗二叉树
 *  二分搜索树每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值
 *  任意一个节点的每棵子树都满足二分搜索树的定义

**二分搜索树是一种具备可比较性的树，左孩子 < 当前节点 < 右孩子。这种可比较性为我们提供了一种高效的查找数据的能力**。

**BST.java（二分搜索树）**

//二分搜索树，不包含重复元素  
    //使用泛型，并要求该泛型必须实现Comparable接口
    public class BST<E extends Comparable<E>> {
        
    	private class Node {
         // 节点类
    		public E e;// 元素
    		public Node left, right;// 左孩子、右孩子
    
    		public Node(E e) {
        
    			// TODO Auto-generated constructor stub
    			this.e = e;
    			left = null;
    			right = null;
    		}
    	}
    
    	private Node root;// 根节点
    	private int size;// 元素个数
    
    	public BST() {
        
    		// TODO Auto-generated constructor stub
    		root = null;
    		size = 0;
    	}
    
    	public int size() {
        
    		return size;
    	}
    
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    
    	// 二分搜索树添加元素e
    	public void add(E e) {
        
    		root = add(root, e);// 调用下面的私有add方法
    	}
    
    	// 返回插入节点后的二分搜索树的根，递归算法
    	private Node add(Node node, E e) {
        
    		// TODO Auto-generated method stub
    		// 如果节点为空，那么这个位置就应该插入元素e
    		if (node == null) {
         // 递归调用的终止条件，直到找到null位置完成插入
    			size++;
    			return new Node(e);
    		}
    		if (e.compareTo(node.e) < 0) {
        // e小于node.e，再对左子树进行递归
    			node.left = add(node.left, e);
    		} else if (e.compareTo(node.e) > 0) {
        // e大于node.e，再对右子树进行递归
    			node.right = add(node.right, e);
    		}
    		return node;
    	}
    
    	// 二分搜索树查询是否有元素e
    	public boolean contains(E e) {
        
    		return contains(root, e);// 调用下面私有的contains方法
    	}
    
    	// 查看以node为根节点的二分搜索树是否包含元素e，递归算法
    	private boolean contains(Node node, E e) {
        
    		// TODO Auto-generated method stub
    		if (node == null)// 如果node为空，不包含e
    			return false;
    		if (e.compareTo(node.e) == 0)// 找到了元素e
    			return true;
    		else if (e.compareTo(node.e) < 0)// 如果e小于node.e,在左子树中进行递归查询
    			return contains(node.left, e);
    		else                  // 即e.compareTo(node.e) > 0 如果e大于node.e,在右子树中进行递归查询
    			return contains(node.right, e);
    	}
    
    	// 前序遍历
    	public void preOrder() {
        
    		preOrder(root);
    	}
    
    	// 前序遍历以root为根的二分搜索树，递归算法
    	private void preOrder(Node node) {
        
    		// TODO Auto-generated method stub
    		if (node == null) {
         // 如果树根节点为空，则return，递归终止条件
    			return;
    		}
    		System.out.println(node.e);//遍历根节点
    		preOrder(node.left);// 遍历左子树
    		preOrder(node.right);// 遍历右子树
    	}
    	//中序遍历
    	public void inOrder() {
        
    		inOrder(root);
    	}
    
    	private void inOrder(Node node) {
        
    		// TODO Auto-generated method stub
    		if (node == null) {
        
    			return;
    		}
    		inOrder(node.left);
    		System.out.println(node.e);
    		inOrder(node.right);
    	}
    
    	// 后序遍历
    		public void outOrder() {
        
    			outOrder(root);
    		}
    
    		private void outOrder(Node node) {
        
    			// TODO Auto-generated method stub
    			if (node == null) {
        
    				return;
    			}
    			outOrder(node.left);
    			outOrder(node.right);
    			System.out.println(node.e);
    		}
    		
    	// 二分搜索树的层序遍历 非递归算法
    	public void levelOrder() {
        
    		Queue<Node> q = new LinkedList<>();
    		q.add(root);// 入队根节点
    		while (!q.isEmpty()) {
        // 队列不为空
    			Node cur = q.remove();// 出队
    			System.out.println(cur.e);// 访问
    			if (cur.left != null)
    				q.add(cur.left);// 入队左子树根节点
    			if (cur.right != null)
    				q.add(cur.right);// 入队右子树根节点
    		}
    	}
    }

**测试（main）**

public class Main {
        
    	public static void main(String[] args) {
        
    		BST<Integer> bst = new BST<>();
    		int [] nums = {
        8,5,9,6,4,2};
    		for (int num : nums) {
        
    			bst.add(num);
    		}
    		System.out.println("前序遍历");
    		bst.preOrder();
    		System.out.println("中序遍历");
    		bst.inOrder();
    		System.out.println("后序遍历");
    		bst.outOrder();
    		System.out.println("层序遍历");
    		bst.levelOrder();
    	}
    }

**测试结果**  
![在这里插入图片描述][20200126125045547.png]

[20200126125045547.png]: https://img-blog.csdnimg.cn/20200126125045547.png