重构二叉搜索树（继承二叉树）

1、重构二叉搜索树

1.1、设计思想

由于实际项目中常用的二叉树种类有很多（如：二叉搜索树、AVL树、红黑树等），为了提高代码的复用率和可读性，我们可以通过继承二叉树的方式重构这些特殊的二叉树。

因此，我们也可以通过继承二叉树的方式实现二叉搜索树（Binary Search Tree，BST），如下图所示：

其中：

• 二叉树类中存放所有二叉树公共的接口。
• 二叉搜索树类中实现二叉搜索树自己特有的接口。

1.2、类的结构设计

同样地，在编程之前，我们需要先对二叉树类和二叉搜索树类的结构进行设计。

1.2.1、二叉树类设计

二叉树类需要的成员主要包括：

• 树的节点（元素）数量

  private int size;

  size = 元素（Element）数目 = 节点（Node）数目。

• 根节点的引用

  private Node<E> root;

  root指向二叉搜索树的根节点。

• 内部静态节点（Node）类

  由于该节点类仅供二叉搜索树类使用，因此，需将该节点类定义为二叉搜索树类的内部类。该类的成员包括：

  • 该节点内部的泛型元素

    E element;

    泛型元素既可以是基本数据类型，也可以是类的对象。

  • 左子节点的引用

    Node<E> left;

    left指向该节点的左子节点。

  • 右子节点的引用

    Node<E> right;

    right指向该节点的右子节点。

  • 父节点的引用

    Node<E> parent;

    parent指向该节点的父节点。

  • 构造函数

  • 析构函数（Java语言没有）

**注：**内部类的成员可以不写访问权限。

• 用户自定义对节点元素的处理逻辑（抽象类）

  public static abstract class Visitor<E>{
  	boolean isStoped;
  	/**
  	 * 抽象类中的抽象函数类似于接口函数
  	 * @return 如果返回false（默认），就继续遍历;如果返回true，就停止遍历。
  	 */
  	abstract boolean visit(E element);
  }

• 接口函数

1.2.2、二叉搜索树类

二叉搜索树类需要的成员主要包括：

• 自定义节点元素比较器

  private Comparator<E> comparator;

• 构造函数（有形参、无形参）

  通过构造函数，我们可以在新建二叉搜索树时对其节点元素的比较逻辑进行初始化。一方面，我们要构建一个带形参的构造函数，让用户自定义节点元素的比较逻辑；另一方面，我们还要构建一个无形参的构造函数，用来处理用户未定义节点元素的比较逻辑时的情况。

• 接口函数

1.3、接口设计

1.3.1、二叉树类接口设计

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• void clear(); //清空所有元素
• void preorder(); //前序遍历
• void inorder(); //中序遍历
• void postorder()； //后序遍历
• void levelOrder()； //层序遍历
• boolean isComplete(); //是否为完全二叉树
• int height(); //计算二叉树的高度

注：

• 与动态数组的接口相比，二叉树的元素是没有索引（index）这一概念的。
• 用户处理（添加、删除、查找等）的是元素，他们是不关心二叉树内部节点结构的。
• 由于普通二叉树中各节点之间的逻辑关系不明确，因此实际应用中一般不使用普通二叉树存储数据，而是使用继承了该类的特定二叉树（如：二叉搜索树、AVL树、红黑树等）来存储数据，进行元素的增加、删除、查询等操作。

1.3.2、二叉搜索树类接口设计

• void add(E element); //添加元素
• void remove(E element); //删除元素
• boolean contains(E element); //搜索（查找二叉搜索树中是否包含某元素）

2、重新实现二叉搜索树

2.1、编程实现

新建一个项目，在其中：

（1）★实现二叉树

新建一个名称为BinaryTree（包名为：com.atangbiji）的类，用来实现二叉树；

BinaryTree.java文件：

package com.atangbiji;

import java.util.LinkedList;
import java.util.Queue;
import com.atangbiji.printer.BinaryTreeInfo;

//继承二叉树类
@SuppressWarnings("unchecked")//镇压警告
public class BinaryTree<E> implements BinaryTreeInfo{
	
	protected int size;	//二叉树存放元素的数量
	protected Node<E> root;	//根节点的引用
	
	//内部静态节点类
	protected static class Node<E> {
		E element;	//该节点内部的泛型元素
		Node<E> left;	//左子节点的引用
		Node<E> right;	//右子节点的引用
		Node<E> parent;	//父节点的引用
		
		//构造函数
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		//是否为叶子节点
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
		//是否有两个子节点
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
	}
	
	//用户自定义对节点元素的处理逻辑（抽象类）
	public static abstract class Visitor<E>{
		boolean isStoped;
		/**
		 * 抽象类中的抽象函数类似于接口函数
		 * @return 如果返回false（默认），就继续遍历;如果返回true，就停止遍历。
		 */
		abstract boolean visit(E element);
	}
	
	/*
	 * 元素的数量
	 * @param
	 * @return 
	 * */
	public int size() {
		return size;	//直接返程size成员变量即可
	}
	
	/*
	 * 是否为空
	 * @param
	 * @return 
	 * */
	public boolean isEmpty() {
		return size == 0;	//size为0为空，否则不为空
	}
	
	/*
	 * 清空所有元素
	 * @param
	 * @return 
	 * */
	public void clear() {
		root = null;
		size = 0;
	}
	

	/*
	 * 第一套遍历接口【用户可自定义对节点元素的处理逻辑】
	 * */
	
	//二叉树的前序遍历接口【用户可自定义对节点元素的处理逻辑】
	public void preorder(Visitor<E> visitor) {
		preorder(root,visitor);
	}
	/*
	 * 二叉树的前序遍历（递归调用）
	 * @param: node,visitor
	 * @return
	 * */
	private void preorder(Node<E> node, Visitor<E> visitor)  {
		//递归基（如果本次遍历状态返回true，就停止递归；否则，继续递归）
		if (node == null || visitor == null || visitor.isStoped) 
			return;
		
		//先访问根节点的值，并记录下一次遍历状态
		visitor.isStoped = visitor.visit(node.element);
		//再前序遍历左子树
		preorder(node.left,visitor);
		//最后前序遍历右子树
		preorder(node.right,visitor);
	}
	
	//二叉树的中序遍历接口【用户可自定义对节点元素的处理逻辑】
	public void inorder(Visitor<E> visitor) {
		inorder(root,visitor);
	}
	/*
	 * 二叉树的中序遍历（递归调用）
	 * @param: node,visitor
	 * @return
	 * */
	private void inorder(Node<E> node, Visitor<E> visitor)  {
		//递归基（如果本次遍历状态返回true，就停止递归；否则，继续递归）
		if (node == null || visitor == null || visitor.isStoped) 
			return;
		
		//先前序遍历左子树
		inorder(node.left,visitor);
		//如果在当前节点的左子树中遍历到了用户想要停止的节点，那么同样要停止递归
		if (visitor.isStoped) return;
		//再访问根节点的值，并记录下一次遍历状态
		visitor.isStoped = visitor.visit(node.element);
		//最后前序遍历右子树
		inorder(node.right,visitor);
	}

	//二叉树的后序遍历接口【用户可自定义对节点元素的处理逻辑】
	public void postorder(Visitor<E> visitor) {
		postorder(root,visitor);
	}
	/*
	 * 二叉树的后序遍历（递归调用）
	 * @param: node,visitor
	 * @return
	 * */
	private void postorder(Node<E> node, Visitor<E> visitor)  {
		//递归基（如果本次遍历状态返回true，就停止递归；否则，继续递归）
		if (node == null || visitor == null || visitor.isStoped) 
			return;
		
		//先前序遍历左子树
		postorder(node.left,visitor);
		//最后前序遍历右子树
		postorder(node.right,visitor);
		//如果在当前节点的左子树或右子树中遍历到了用户想要停止的节点，那么同样要停止递归
		if (visitor.isStoped) return;
		//再访问根节点的值，并记录下一次遍历状态
		visitor.isStoped = visitor.visit(node.element);
	}
	
	/*
	 * 二叉树的层序遍历接口（队列实现）【用户可自定义对节点元素的处理逻辑】
	 * @param: Visitor<E>用户自定义的对节点元素的处理逻辑
	 * @return
	 * */
	public void levelOrder(Visitor<E> visitor) {
		if (root == null || visitor == null) 
			return;
		//使用Java自带的队列
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);//根节点入队
		
		while (!queue.isEmpty()) {
			//头结点出队
			Node<E> node = queue.poll();
			//在此处通过自定义的接口将节点元素传出，供用户在二叉树类的外部自定义节点元素的处理逻辑
			//若如果接口函数返回true，则直接返回，停止遍历。否则，继续遍历。
			if (visitor.visit(node.element)) {
				return;
			};
			
			if (node.left != null) {
				//左子节点入队
				queue.offer(node.left);
			}
			
			if (node.right != null) {
				//右子节点入队
				queue.offer(node.right);
			}
		}
	}
	
	
	/*
	 * 第二套遍历接口【用户不可以自定义对节点元素的处理逻辑】
	 * */
	
	//前序遍历二叉树【用户不可以自定义对节点元素的处理逻辑】
	public void preorderTraversal() {
		preorderTraversal(root);
	}	
	/*
	 * 前序遍历（递归调用）
	 * @param: node
	 * @return
	 * */
	private void preorderTraversal(Node<E> node)  {
		//递归基
		if (node == null) 
			return;
		
		//先访问根节点的值
		System.out.println(node.element);
		//再前序遍历左子树
		preorderTraversal(node.left);
		//最后前序遍历右子树
		preorderTraversal(node.right);
	}

	//中序遍历二叉树【用户不可以自定义对节点元素的处理逻辑】
	public void inorderTraversal() {
		inorderTraversal(root);
	}	
	/*
	 * 中序遍历（递归调用）
	 * @param: node
	 * @return
	 * */
	private void inorderTraversal(Node<E> node)  {
		//递归基
		if (node == null) 
			return;

		//先中序遍历左子树
		inorderTraversal(node.left);
		//再访问根节点的值
		System.out.println(node.element);
		//最后中序遍历右子树
		inorderTraversal(node.right);
	}
	
	//后序遍历二叉树【用户不可以自定义对节点元素的处理逻辑】
	public void postorderTraversal() {
		postorderTraversal(root);
	}	
	/*
	 * 后序遍历（递归调用）
	 * @param: node
	 * @return
	 * */
	private void postorderTraversal(Node<E> node)  {
		//递归基
		if (node == null) 
			return;

		//先后序遍历左子树
		postorderTraversal(node.left);
		//再后序遍历右子树
		postorderTraversal(node.right);
		//最后访问根节点的值
		System.out.println(node.element);
	}

	
	/*
	 * 层序遍历二叉树（队列实现）【用户不可以自定义对节点元素的处理逻辑】
	 * @param: 
	 * @return
	 * */
	public void levelOrderTraversal() {
		if (root == null) 
			return;
		//使用Java自带的队列
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);//根节点入队
		
		while (!queue.isEmpty()) {
			//头结点出队
			Node<E> node = queue.poll();
			System.out.println(node.element);
			
			if (node.left != null) {
				//左子节点入队
				queue.offer(node.left);
			}
			
			if (node.right != null) {
				//右子节点入队
				queue.offer(node.right);
			}
		}
	}
	
	/*
	 * 获取某一节点的前驱节点
	 * @param node
	 * @return
	 * */
	protected Node<E> predecessor(Node<E> node) {
		if (node == null) return null;
		
		// 前驱节点在左子树当中（left.right.right.right....）
		Node<E> p = node.left;
		if (p != null) {
			while (p.right != null) {
				p = p.right;
			}
			return p;
		}
		
		// 从父节点、祖父节点中寻找前驱节点
		while (node.parent != null && node == node.parent.left) {
			node = node.parent;
		}

		// 若node.parent == null或 node == node.parent.right
		return node.parent;
	}

	/*
	 * 获取某一节点的后继节点
	 * @param node
	 * @return
	 * */
	protected Node<E> successor(Node<E> node) {
		if (node == null) return null;
		
		// 前驱节点在左子树当中（right.left.left.left....）
		Node<E> p = node.right;
		if (p != null) {
			while (p.left != null) {
				p = p.left;
			}
			return p;
		}
		
		// 从父节点、祖父节点中寻找前驱节点
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}

		return node.parent;
	}

	/*
	 * 判断一棵树是否为完全二叉树（层序遍历）
	 * @param
	 * @return
	 * */
	public boolean isComplete() {
		if (root == null) return false;
		
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		boolean leaf = false;//是否要求为叶子节点
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (leaf && !node.isLeaf()) 
				return false;	
			if (node.hasTwoChildren()) {
				queue.offer(node.left);
				queue.offer(node.right);
			} else if (node.left == null && node.right != null) {
				return false;
			} else { // 后面遍历的节点都必须是叶子节点
				leaf = true;
				if (node.left != null) {
					queue.offer(node.left);
				}
			}
		}		
		return true;
	}

	/*
	 * 判断一棵树是否为完全二叉树（层序遍历）
	 * @param
	 * @return
	 * */
	public boolean isComplete2() {
		if (root == null) return false;
		
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);

		boolean leaf = false;//是否要求为叶子节点
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (leaf && !node.isLeaf()) 
				return false;
			
			if (node.left != null) {
				queue.offer(node.left);
			} else if (node.right != null) { // node.left == null && node.right != null
				return false;
			}
			
			if (node.right != null) {
				queue.offer(node.right);
			} else { // node.right == null
				leaf = true;
			}
		}
		return true;
	}
	
	/*
	 * 计算二叉树的高度（递归调用）
	 * @param:
	 * @return
	 * */
	public int height() {
		//二叉树的高度 = 跟节点的高度
		return height(root);
	}
	
	/*
	 * 计算二叉树中某一个节点的高度（递归调用）
	 * @param: node
	 * @return
	 * */
	private int height(Node<E> node) {
		if (node == null) return 0;
		//当前节点的高度 = 当前节点左右子节点高度的较大者 + 1
		return 1 + Math.max(height(node.left), height(node.right));
	}
	
	/*
	 * 计算二叉树的高度（层序遍历）
	 * @param: node
	 * @return
	 * */
	public int height2() {
		if (root == null) return 0;
		
		// 树的高度
		int height = 0;
		// 存储着每一层的元素数量
		int levelSize = 1;
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			levelSize--;
			
			if (node.left != null) {
				queue.offer(node.left);
			}
			
			if (node.right != null) {
				queue.offer(node.right);
			}

			//当每一层节点全部出栈时，栈内元素刚好全部是下一层的所有节点
			if (levelSize == 0) {
				levelSize = queue.size();
				height++;
			}
		}
		
		return height;
	}
	
	/*
	 * 打印二叉树中的所有元素（重写toString()函数）
	 * @param: 	 
	 * @return:
	 * */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		
		//中序遍历二叉树
		toString(root,sb,"");
		
		return sb.toString();
	}
	
	/*
	 * 二叉树的中序遍历 + 字符串拼接（递归调用）
	 * @param: node, sb , prefix
	 * @return
	 * */
	private void toString(Node<E> node, StringBuilder sb, String prefix) {
		//递归基
		if (node == null) 
			return;
		//中序遍历 + 拼接前缀
		toString(node.left, sb, prefix + "L---");
		sb.append(prefix).append(node.element).append("\n");
		toString(node.right, sb, prefix + "R---");
	}
	
	
	/*
	 * 使用小码哥MJ封装的二叉树打印接口
	 * */
	@Override
	public Object root() {
		// 根节点是谁？
		return root;
	}

	@Override
	public Object left(Object node) {
		// 如何查找左节点？
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		// 如何查找右节点？
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		// 如何打印单个节点？
		return ((Node<E>)node).element;
	}
    
}

**注：**在父类和子类都能够访问的成员变量和方法应当设置为protected类型。

（2）★实现二叉搜索树

新建一个名称为BinarySearchTree（包名为：com.atangbiji）的类，用来实现二叉搜索树；

BinarySearchTree.java文件：

package com.atangbiji;

import java.util.Comparator;

@SuppressWarnings("unchecked")//镇压警告
public class BinarySearchTree<E> extends BinaryTree<E>{

	//自定义节点元素比较器
	private Comparator<E> comparator;	
	
	//二叉搜索树类的构造函数（用来处理用户未定义节点元素的比较逻辑时的情况）
	public BinarySearchTree() {
		this(null);
	}
	
	//二叉搜索树类的构造函数（用来处理用户自定义节点元素的比较逻辑时的情况）
	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	/*
	 * 添加元素
	 * @param: element
	 * @return 
	 * */
	public void add(E element) {
		elementNotNullCheck(element);
		
		//添加第一个节点
		if (root == null) {
			root = new Node<>(element,null);
			size++;
			return;
		}
		
		//添加的不是第一个节点
		//1、找到待添加元素的父节点
		Node<E> node = root;
		
		Node<E> parent = null;//定义待添加元素的父节点
		int cmp = 0;//新增元素与当前节点的比较结果
		while (node != null) {
			//将新增元素的值与当前节点的值进行比较
			cmp = compare(element, node.element);
			parent = node;//保存待添加元素的父节点
			
			if (cmp > 0) {
				//将待添加元素与当前节点的右子节点进行比较
				node = node.right;
			}else if (cmp < 0) {
				//将待添加元素与当前节点的左子节点进行比较
				node = node.left;
			}else {	//相等
				node.element = element;//让新元素覆盖旧的值
				return;
			}
		}
		
		//2、创建新节点
		Node<E> newNode = new Node<>(element, parent);
		//3、判断将新元素插入到父节点左子节点还是右子节点
		if (cmp > 0) {
			parent.right = newNode;
		} else if (cmp < 0) {
			parent.left = newNode;
		}
		
		//4、二叉搜索树存放元素的数量+1
		size++;
	}
	
	/*
	 * 删除元素
	 * @param element
	 * @return
	 * */
	public void remove(E element) {
		//删除该元素所在的节点
		remove(node(element));
	}
	
	/*
	 * 查找二叉搜索树中是否包含某元素
	 * @param element
	 * @return
	 * */
	public boolean contains(E element) {
		//查找元素所在的节点是否存在
		return node(element) != null;
	}
	
	/*
	 * 删除节点
	 * @param node
	 * @return
	 * */
	private void remove(Node<E> node) {
		//若该节点不存在，则直接返回
		if (node == null) return;
		
		size--;
		
		//若待删除节点度为2，则先用该节点后继（或前驱）节点的值覆盖该节点的值，然后再删除该节点的原来的后继节点。
		if (node.hasTwoChildren()) { 
			// 找到后继节点
			Node<E> s = successor(node);
			// 用后继（或前驱）节点的值覆盖度为2的节点的值
			node.element = s.element;
			//将后继（或前驱）节点（度一定为1或者0）变成待删除节点，后面统一删除
			node = s;
		}
		
		// 待删除node节点(度为一定为1或0的)的取代者，要么是其左子节点，要么是其右子节点，要么为null
		Node<E> replacement = node.left != null ? node.left : node.right;
		// 统一删除度为1或0的node节点
		if (replacement != null) { // 待删除node是度为1的节点
			// 更改parent
			replacement.parent = node.parent;
			// 更改parent的left、right的指向
			if (node.parent == null) { // 待删除node是度为1的节点并且是根节点
				root = replacement;
			} else if (node == node.parent.left) {
				node.parent.left = replacement;
			} else { // node == node.parent.right
				node.parent.right = replacement;
			}
		} else if (node.parent == null) { // 待删除node是叶子节点并且是根节点
			root = null;
		} else { // 待删除node是叶子节点，但不是根节点
			if (node == node.parent.left) {
				node.parent.left = null;
			} else { // node == node.parent.right
				node.parent.right = null;
			}
		}
	}
	
	/*
	 * 查找元素所在的节点
	 * @param element
	 * @return node
	 * */
	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(element, node.element);
			//若找到该元素，则返回其所在的节点
			if (cmp == 0) return node;
			//若未找到该元素，则继续在其左右子节点中查找
			if (cmp > 0) {
				//若待查找元素大于该节点元素的值，则继续向右子节点查找
				node = node.right;
			} else { 
				//若待查找元素小于该节点元素的值，则继续向左子节点查找（cmp < 0）
				node = node.left;
			}
		}
		//若所有子树的节点中均未找到该元素，则该元素节点不存在
		return null;
	}

	/*
	 * 节点元素比较函数
	 * @param: e1,e2
	 * @return: 返回等于0表示：e1 = e2; 返回大于0表示：e1 > e2; 返回小于0表示：e1 < e2.
	 * */
	private int compare(E e1,E e2) {
		//若comparator不为空（即：用户自定义了节点元素的比较逻辑），则在节点元素类外部使用Comparator比较器实现比较逻辑。
		if (comparator != null) {
			return comparator.compare(e1, e2);
		}
		//若comparator为空（即：用户未定义节点元素的比较逻辑），则将节点元素强制转换为可比较的对象（Comparable接口）。
		return ((Comparable<E>)e1).compareTo(e2);
	}
	
	/*
	 * 检查元素是否为空
	 * @param
	 * @return 
	 * */
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not null !");
		}
	}
	
}

（3）自定义节点元素对象的比较逻辑

为了与之前项目二叉搜索树的功能保持一致，我们复用之前项目中自定义的节点元素对象的比较逻辑。

Person.java文件：

package com.atangbiji;

public class Person implements Comparable<Person>{
	private int age;
	private String name;
	
	//构造函数
	public Person(int age, String name) {
		this.age = age;
		this.name = name;
	}

	//成员变量的get和set方法
	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	//实现节点元素比较接口
	@Override
	public int compareTo(Person e) {
		//假定年龄大的人所对应的节点元素大
		return age - e.age;
	}
	
	@Override
	public String toString() {
		return name + "(age="+ age +")";
	}
	
}

PersonComparator1.java文件：

package com.atangbiji;

import java.util.Comparator;

public class PersonComparator1 implements Comparator<Person> {

	//实现节点元素比较接口
	@Override
	public int compare(Person e1, Person e2) {
		//假定年龄大的人所对应的节点元素大
		return e1.getAge() - e2.getAge();
	}
	
}

PersonComparator2.java文件：

package com.atangbiji;

import java.util.Comparator;

public class PersonComparator2 implements Comparator<Person> {
	
	//实现节点元素比较接口
	@Override
	public int compare(Person e1, Person e2) {
		//假定年龄大的人所对应的节点元素小
		return e2.getAge() - e1.getAge();
	}
}

（4）使用小码哥MJ封装的二叉树打印接口

为了继续使用小码哥MJ封装的二叉树打印接口，我们复用小码哥MJ封装的二叉树打印工具。

（5）自定义测试类

再新建一个名称为Main（包名为：com.atangbiji）的类，用来调用（测试）自己封装的二叉搜索树。如下图所示：

2.2、接口测试

在Main类中新建多个BinarySearchTree对象，用来测试自己重新封装的二叉搜索树。这里仅以添加、删除、遍历节点元素等为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

import java.util.Comparator;

import com.atangbiji.BinaryTree.Visitor;
import com.atangbiji.printer.BinaryTrees;

public class Main {
	public static void main(String[] args) {
		
		/*
		  * 节点元素为数字的二叉搜索树
		 * */
		Integer data[] = new Integer[] {
				7,4,2,1,3,5,9,8,11,10,12
		};
		
		BinarySearchTree<Integer> bst = new BinarySearchTree<>();
		
		//将各元素依次添加到二叉搜索树
		for(int i = 0; i < data.length; i++){
			bst.add(data[i]);
		}
		System.out.println("一、节点元素为整数的二叉搜索树: \n");
		System.out.println("1、采用（中序）遍历法打印二叉搜索树: \n");
		System.out.println(bst);
		
		System.out.println("2、使用MJ封装的接口打印二叉搜索树: \n");
		BinaryTrees.println(bst);
		
		System.out.println("二叉树高度（递归实现）为: " + bst.height() + "\n");
		System.out.println("二叉树高度（层序遍历实现）为: " + bst.height2() + "\n");
		
		
		/*
		  * 节点元素为对象的二叉搜索树
		 * */

		//自定义比较逻辑1
		PersonComparator1 cmp1 = new PersonComparator1();
		BinarySearchTree<Person> bst1 = new BinarySearchTree<>(cmp1);
		//将各元素依次添加到二叉搜索树
		bst1.add(new Person(12, "Tom"));
		bst1.add(new Person(15, "Jim"));
		bst1.add(new Person(10, "Lucy"));
		bst1.add(new Person(13, "ATang"));
		bst1.add(new Person(18, "Jan"));
		bst1.add(new Person(8, "Lily"));
		
		System.out.println("\n 二、节点元素为对象的二叉搜索树: ");
		System.out.println("\n 1、自定义比较逻辑1（Comparator接口法）：假定年龄大的人所对应的节点元素大 \n");
		BinaryTrees.println(bst1);
		
		//自定义比较逻辑2
		PersonComparator2 cmp2 = new PersonComparator2();
		BinarySearchTree<Person> bst2 = new BinarySearchTree<>(cmp2);
		//将各元素依次添加到二叉搜索树
		bst2.add(new Person(12, "Tom"));
		bst2.add(new Person(15, "Jim"));
		bst2.add(new Person(15, "Jim"));
		bst2.add(new Person(10, "Lucy"));
		bst2.add(new Person(13, "ATang"));
		bst2.add(new Person(18, "Jan"));
		bst2.add(new Person(8, "Lily"));
		
		System.out.println("\n 2、自定义比较逻辑2（Comparator接口法）：假定年龄大的人所对应的节点元素小 \n");
		BinaryTrees.println(bst2);
		
		//默认比较逻辑
		BinarySearchTree<Person> bst3 = new BinarySearchTree<>();
		//将各元素依次添加到二叉搜索树
		bst3.add(new Person(12, "Tom"));
		bst3.add(new Person(15, "Jim"));
		bst3.add(new Person(15, "Jim"));
		bst3.add(new Person(10, "Lucy"));
		bst3.add(new Person(13, "ATang"));
		bst3.add(new Person(18, "Jan"));
		bst3.add(new Person(8, "Lily"));
		
		System.out.println("\n 3、默认比较逻辑（Comparable接口法）：假定年龄大的人所对应的节点元素大 \n");
		BinaryTrees.println(bst3);
		
		
		BinarySearchTree<Person> bst4 = new BinarySearchTree<>(new Comparator<Person>() {

			//自定义比较逻辑3
			@Override
			public int compare(Person arg0, Person arg1) {
				// TODO Auto-generated method stub
				return arg0.getAge() - arg1.getAge();
			}
			
		});
		//将各元素依次添加到二叉搜索树
		bst4.add(new Person(12, "Tom"));
		bst4.add(new Person(15, "Jim"));
		bst4.add(new Person(15, "Jim"));
		bst4.add(new Person(10, "Lucy"));
		bst4.add(new Person(13, "ATang"));
		bst4.add(new Person(18, "Jan"));
		bst4.add(new Person(8, "Lily"));
		
		System.out.println("\n 4、通过匿名类自定义比较逻辑（Comparator接口法）：假定年龄大的人所对应的节点元素大 \n");
		BinaryTrees.println(bst4);
		
		
		System.out.println("\n" + "\n 三、遍历二叉搜索树（全部节点）: ");
		
		System.out.println("\n 使用MJ封装的接口打印二叉搜索树: \n");
		BinaryTrees.println(bst);
		//调用层序遍历接口
		System.out.println("\n" + "1、层序遍历二叉搜索树（全部节点）：");
		bst.levelOrder(new Visitor<Integer>() {
			
			@Override
			//在visit接口函数中实现节点元素的处理逻辑
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				return false;
			}
		});
		
		//调用前序遍历接口
		System.out.println("\n" + "2、前序遍历二叉搜索树（全部节点）：");
		bst.preorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				return false;
			}
			
		});
		//调用中序遍历接口
		System.out.println("\n" + "3、中序遍历二叉搜索树（全部节点）：");
		bst.inorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				return false;
			}
			
		});
		//调用后序遍历接口
		System.out.println("\n" + "4、后序遍历二叉搜索树（全部节点）：");
		bst.postorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				return false;
			}
			
		});
		
		
		System.out.println("\n" + "\n 四、遍历二叉搜索树（部分节点）: ");
		
		System.out.println("\n" + "使用MJ封装的接口打印二叉搜索树: \n");
		BinaryTrees.println(bst);
		//调用层序遍历接口
		System.out.println("\n" + "1、层序遍历二叉搜索树（部分节点）：");
		bst.levelOrder(new Visitor<Integer>() {
			
			@Override
			//在visit接口函数中实现节点元素的处理逻辑
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				//若遍历到节点元素等于8，则停止遍历
				return element == 8 ? true : false;
			}
		});
		
		//调用前序遍历接口
		System.out.println("\n" + "2、前序遍历二叉搜索树（部分节点）：");
		bst.preorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				//若遍历到节点元素等于8，则停止遍历
				return element == 8 ? true : false;
			}
			
		});
		//调用中序遍历接口
		System.out.println("\n" + "3、中序遍历二叉搜索树（部分节点）：");
		bst.inorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				//若遍历到节点元素等于8，则停止遍历
				return element == 8 ? true : false;
			}
			
		});
		//调用后序遍历接口
		System.out.println("\n" + "4、后序遍历二叉搜索树（部分节点）：");
		bst.postorder(new Visitor<Integer>() {

			@Override
			public boolean visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
				//若遍历到节点元素等于8，则停止遍历
				return element == 8 ? true : false;
			}
			
		});
		

		System.out.println("\n" + "\n 五、删除二叉搜索树中的元素: ");
		System.out.println("\n" + "使用MJ封装的接口打印二叉搜索树（删除前）: \n");
		BinaryTrees.println(bst);
		
		//先调用删除叶子节点接口
		System.out.println("\n" + "1、先删除元素值为5的叶子节点：");
		bst.remove(5);
		System.out.println("\n" + "使用MJ封装的接口打印二叉搜索树（删除元素值为5的叶子节点后）: \n");
		BinaryTrees.println(bst);
		//再调用删除度为1的节点接口
		System.out.println("\n" + "2、在上述基础上，再删除元素值为4（度为1）的节点：");
		bst.remove(4);
		System.out.println("\n" + "使用MJ封装的接口打印二叉搜索树（再删除元素值为4（度为1）的节点后）: \n");
		BinaryTrees.println(bst);
		//再调用删除度为2的节点接口
		System.out.println("\n" + "3、在上述基础上，再删除元素值为9（度为2）的节点：");
		bst.remove(9);
		System.out.println("\n" + "使用MJ封装的接口打印二叉搜索树（再删除元素值为9（度为2）的节点后）: \n");
		BinaryTrees.println(bst);
		
	}
}

运行该程序，输出结果为：

（本讲完，系列博文持续更新中…… ）

参考文献：
[1] 《恋上数据结构与算法》，小码哥MJ

[2] 《数据结构与算法》，邓俊辉

如何获取源代码？

关注 “阿汤笔迹” 微信公众号，在后台回复关键词 “数据结构与算法设计与实现” ，即可获取项目源代码。

原文地址：http://www.atangbiji.com/2023/08/24/BinarySearchTree2/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。