二叉搜索树

0、引例

思考：如何在n个动态的整数中搜索某个整数？（查看其是否存在）

• 方法一：使用普通的动态数组存放元素。

  • 从第0个位置开始遍历搜索，平均时间复杂度为O(n)。
  • 添加元素的平均时间复杂度为O(1)。
  • 删除元素的平均时间复杂度为O(n)。

• 方法二：使用有序的动态数组存放元素。

  • 利：使用二分搜索，最坏时间复杂度为$O(\log n)$。
  • 弊：为了保持数组的有序性，添加、删除的平均时间复杂度均为O(n)。

  **注：**有序数组中的元素始终是按顺序排列的。因此，需要先将数组中的元素按顺序排列。

• 方法三：使用二叉搜索树存放元素。

  • 添加、删除、搜索的最坏时间复杂度均可优化至：$O(\log n)$。

1、二叉搜索树（Binary Search Tree）

1.1、概念

若一个二叉树满足：

• 任意一个节点的值都大于其左子树所有节点的值。
• 任意一个节点的值都小于其右子树所有节点的值。

则称此二叉树为“二叉搜索树”。

注：

• 二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为BST。
• 二叉搜索树又被称为：二叉查找树、二叉排序树。

1.2、特点

• 二叉搜索树各节点的左右子树也是一颗二叉搜索树。

• 二叉搜索树存储的元素必须具备可比较性。

  • 二叉搜索树存储的元素既可以是基本数据类型（如：int、double等），也可以是自定数据类型（如：类类型）。
  • 若存储元素为自定义类型，则需要我们指定比较方式。如：Person类具有年龄、身高等成员变量，我们可以指定按年龄进行比较，年龄比较小的Person在左边，年龄比较大的Person在右边。
  • 存储元素不允许为null。

• 二叉搜索树没有键值相等的节点，值相等的情况需要根据具体需求自行处理。

• 二叉搜索树可以大大提高搜索数据的效率。

2、二叉搜索树的设计

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语言没有）

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

• 接口函数

**注：**因为二叉搜索树不需要预先分配内存，所以BinarySearchTree不用写构造函数。

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

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

2.2、接口设计

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• void clear(); //清空所有元素
• void add(E element); //添加元素
• void remove(E element); //删除元素
• boolean contains(E element); //搜索（查找二叉搜索树中是否包含某元素）

注：

• 与动态数组的接口相比，二叉树的元素是没有索引（index）这一概念的。
• 用户处理（添加、删除、查找等）的是元素，他们是不关心二叉树内部节点结构的。

3、二叉搜索树的实现

3.1、编程实现

新建一个项目，在其中：

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

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

③接口实现，我们这里直接考虑节点元素均为泛型的情况。

（1）定义私有成员变量

BinarySearchTree.java文件：

package com.atangbiji;

public class BinarySearchTree<E> {

	private int size;	//链表存放元素的数量
	private Node<E> root;	//根节点的引用
	
	//内部静态节点类
	private 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;
		}
	}
}

**注：**由于一般情况下，某一节点的父节点一定存在，而其左节点或右节点可能不存在。因此，我们在设计内部静态节点类的构造函数时，只选择将父节点作为其形参。

（2）实现size()接口

BinarySearchTree.java文件：

/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	return size;	//直接返回size成员变量即可
}

（3）实现isEmpty()接口

BinarySearchTree.java文件：

/*
 * 是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	return size == 0;	//size为0为空，否则不为空
}

（4）实现clear()接口

BinarySearchTree.java文件：

/*
 * 清空所有元素
 * @param
 * @return 
 * */
public void clear() {
	root = null;
	size = 0;
}

（5）实现add(E element)接口

a、元素是否为空？

在添加元素前需要先检查元素是否为空。

BinarySearchTree.java文件：

/*
 * 检查元素是否为空
 * @param
 * @return 
 * */
private void elementNotNullCheck(E element) {
	if (element == null) {
		throw new IllegalArgumentException("element must not null !");
	}
}

b、节点元素的比较

因为二叉搜索树的节点元素必须具备可比较性，所以我们需要自定义节点元素的比较函数。

• 当节点元素为数字等基本数据类型时，我们可以直接比较两者大小。
• 当节点元素为对象时，我们可以通过Java语言自带的Comparable接口和Comparator接口来自定义对象的比较逻辑。

实际应用中，我们可以使用如下三种方法来自定义节点元素对象的比较逻辑。其中：

①Comparable接口法（方法一）主要处理节点元素数据类型相同，且只有一套比较逻辑的情况；

②Comparator接口法（方法二）主要处理节点元素数据类型相同，但可能具有多套比较逻辑的情况；

③方法三则是方法一和方法二的完美结合，同时兼顾了节点元素可能具有一套或多套比较逻辑的情况，也是我们推荐使用的实现方法。

具体实现方法如下：

方法一：Comparable接口法

①新建一个Person类，添加成员变量：age、name，按“Shift+Alt+S”键，通过弹出菜单快速生成构造函数。

Person.java文件：

package com.atangbiji;

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

②新建一个Comparable接口类，在其中自定义一个int compareTo(E e) 接口函数，用作节点元素间的相互比较。

Comparable.java文件：

package com.atangbiji;

public interface Comparable<E> {
	//待实现接口函数
	int compareTo(E e);
}

③在Person类中实现Comparable接口类中的int compareTo(E e)接口函数。

我们这里假定年龄大的人所对应的节点元素大。

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;
	}

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

④在BinarySearchTree类中继承Comparable接口类。

BinarySearchTree.java文件：

package com.atangbiji;
public class BinarySearchTree<E extends Comparable> {
    
}

此时，我们便可以在节点元素的比较函数中调用int compareTo(E e)接口函数了。

BinarySearchTree.java文件：

/*
 * 节点元素比较函数
 * @param: e1,e2
 * @return: 返回等于0表示：e1 = e2; 返回大于0表示：e1 > e2; 返回小于0表示：e1 < e2.
 * */
private int compare(E e1,E e2) {
	//调用节点元素比较接口
	return e1.compareTo(e2);
}

需要说明的是：由于上述方法的比较逻辑是在Person类内部实现的，所以无论你创建多少个二叉搜索树的对象，它们的Person对象的比较逻辑都将是同一种逻辑，即：Person对象只能是年龄大的节点元素大。

方法二：Comparator（比较器）接口法

对于节点数据类型相同的二叉搜索树，由于不同的二叉搜索树对象可能需要不同的比较逻辑（如：对于节点元素均为Person对象的二叉搜索树，有的二叉搜索树假定年龄大的人所对应的节点元素大，而有的二叉搜索树假定年龄大的人所对应的节点元素小）。为了满足这种不同二叉搜索树对象间比较逻辑的个性化需求，我们可以让用户在Person类外部使用不同的比较器来实现不同的比较逻辑。然后在新建二叉搜索树对象时，将相应的比较器作为形参传入，用来初始化对象。具体实现过程如下：

①新建一个Comparator接口类，在其中自定义一个int compare(E e1, E e2)接口函数，用作节点元素间的相互比较。

Comparator.java文件：

package com.atangbiji;

public interface Comparator<E> {
	//待实现接口函数
	int compare(E e1, E e2);
}

②在BinarySearchTree类中定义一个Comparator私有变量，并通过一个有形参的构造函数对其初始化。

BinarySearchTree.java文件：

private Comparator<E> comparator;	//自定义节点元素比较器
//二叉搜索树类的构造函数（用来处理用户自定义节点元素的比较逻辑时的情况）
public BinarySearchTree(Comparator<E> comparator) {
	this.comparator = comparator;
}

③在Person类中按“Shift+Alt+S”键自动生成成员变量的get和set方法，供其它类调用。

Person.java文件：

//成员变量的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;
}

④新建一个PersonComparator1类，在其内部实现比较器逻辑：年龄大的人所对应的节点元素大。

PersonComparator1.java文件：

package com.atangbiji;

public class PersonComparator1 implements Comparator<Person> {

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

⑤新建一个PersonComparator2类，在其内部实现与PersonComparator1相反的比较器逻辑：年龄大的人所对应的节点元素小。

PersonComparator2.java文件：

package com.atangbiji;

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

⑥此时BinarySearchTree类不需要再继承Comparable接口类。

BinarySearchTree.java文件：

public class BinarySearchTree<E>{
    
}

此时，我们便可以在节点元素的比较函数中通过Comparator比较器调用int compare(E e1, E e2)接口函数了。

BinarySearchTree.java文件：

/*
 * 元素比较函数
 * @param: e1,e2
 * @return： 返回等于0表示：e1 = e2; 返回大于0表示：e1 > e2; 返回小于0表示：e1 < e2.
 * */
private int compare(E e1,E e2) {
	//调用节点元素比较接口
	return comparator.compare(e1, e2);
}

⑦这样在新建二叉搜索树对象时，我们便可以将自定义的比较逻辑（PersonComparator1或PersonComparator2）通过相应的Comparator比较器作为形参传入。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		
		/*
		 * 节点元素为对象的二叉搜索树
		 * */
		PersonComparator1 cmp1 = new PersonComparator1();
		BinarySearchTree<Person> bst1 = new BinarySearchTree<>(cmp1);
		//将各元素依次添加到二叉搜索树
		bst1.add(new Person(12, "Tom"));
		bst1.add(new Person(15, "Jim"));
		
		PersonComparator2 cmp2 = new PersonComparator2();
		BinarySearchTree<Person> bst2 = new BinarySearchTree<>(cmp2);
		//将各元素依次添加到二叉搜索树
		bst2.add(new Person(12, "Tom"));
		bst2.add(new Person(15, "Jim"));
	}
}

通过这种方法，我们便实现了不同二叉搜索树对象间比较逻辑的个性化定制。

★ 方法三：将Comparable接口与Comparator接口完美结合

方法二虽然实现了不同二叉搜索树对象间比较逻辑的个性化定制，但它要求我们每次在创建二叉搜索树对象的同时都要传入一个自定义的Comparator比较器。实际应用中，对于节点数据类型相同的二叉搜索树，虽然不同的二叉搜索树对象可能会出现不同的比较逻辑，但出现这种情况的概率很低。即：节点数据类型相同的二叉搜索树一般具有相同的（只有一套）比较逻辑。

因此，对于节点数据类型相同的二叉搜索树：

• 当它们的节点元素具有相同的比较逻辑时（大多数情况），我们希望在节点元素类内部使用Comparable接口实现比较逻辑，这样我们在新建二叉搜索树对象时就不用再传入比较器了；
• 当它们的节点元素具有多套比较逻辑时（极少数情况），我们在节点元素类外部使用Comparator比较器实现比较逻辑，并在新建二叉搜索树对象时将其作为形参传入。

为了让我们设计的二叉搜索树兼顾上述两种比较逻辑，我们将方法一中的Comparable接口与方法二中的Comparator接口综合起来，为用户提供两套构造函数（有形参和无形参）。

其中：

• 有形参的构造函数用来处理用户自定义节点元素的比较逻辑时的情况；
• 无形参的构造函数用来处理用户未定义节点元素的比较逻辑时的情况。

具体实现过程如下：

①在BinarySearchTree类中再定义一个无形参的构造函数，用来处理用户未定义节点元素的比较逻辑时的情况。

BinarySearchTree.java文件：

//二叉搜索树类的构造函数（用来处理用户未定义节点元素的比较逻辑时的情况）
public BinarySearchTree() {
	this(null);
}

②考虑到当用户自定义节点元素的比较逻辑时，我们没必要让节点元素类（如：Person）内部再实现Comparable接口了。只有当用户未定义节点元素的比较逻辑时，我们才需要在节点元素类（如：Person）内部实现Comparable接口。因此，BinarySearchTree类也不需要再继承Comparable接口类。即：

BinarySearchTree.java文件：

public class BinarySearchTree<E>{
    
}

③在Person对象类内部将默认的比较逻辑定义为：假定年龄大的人所对应的节点元素大。

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;
	}	
}

④此时，我们便可以在节点元素的比较函数中根据创建二叉树搜索树时是否自定义节点元素的比较逻辑（comparator是否为空）来分类处理。当用户自定义了节点元素的比较逻辑时，则在节点元素类外部使用Comparator比较器实现比较逻辑；当用户未定义节点元素的比较逻辑时，则将节点元素强制转换为可比较的对象（Comparable接口）。

BinarySearchTree.java文件：

/*
 * 元素比较函数
 * @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);
}

**注：**使用这种方法，当用户未定义节点元素的比较逻辑（即comparator == null）时，若节点元素类（如：Person）内部没有实现Comparable接口，则Java会抛出接口异常，如下图所示。

若出现此类异常，我们在节点元素类（如：Person）内部实现Comparable接口即可。

⑤由于Java语言在java.util包中自带了Comparable与Comparator接口类。因此，我们可以在项目中删除前面自定义的这两个接口类，并将它们分别替换为Java自带的同名接口。即：在相应类中导入java.util.Comparator接口类。

BinarySearchTree.java文件：

import java.util.Comparator;

PersonComparator1.java文件：

import java.util.Comparator;

PersonComparator2.java文件：

import java.util.Comparator;

⑥这样我们设计的二叉搜索树便可以同时满足用户自定义比较逻辑和未定义比较逻辑的情况。（当用户未定义时采用默认的比较逻辑）

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		
		/*
		 * 节点元素为对象的二叉搜索树
		 * */

		//自定义比较逻辑1
		PersonComparator1 cmp1 = new PersonComparator1();
		BinarySearchTree<Person> bst1 = new BinarySearchTree<>(cmp1);
		//将各元素依次添加到二叉搜索树
		bst1.add(new Person(12, "Tom"));
		bst1.add(new Person(15, "Jim"));
		
		//自定义比较逻辑2
		PersonComparator2 cmp2 = new PersonComparator2();
		BinarySearchTree<Person> bst2 = new BinarySearchTree<>(cmp2);
		//将各元素依次添加到二叉搜索树
		bst2.add(new Person(12, "Tom"));
		bst2.add(new Person(15, "Jim"));
		
		//默认比较逻辑
		BinarySearchTree<Person> bst3 = new BinarySearchTree<>();
		//将各元素依次添加到二叉搜索树
		bst3.add(new Person(12, "Tom"));
		bst3.add(new Person(15, "Jim"));
	}
}

注：当节点元素为Java内置的很多数据类型（如：Integer、Double、String等）时，我们之所以不需要自定义节点元素的比较逻辑是因为：它们在底层实现时已经帮我们实现了comparable比较接口。

附：通过匿名类自定义比较逻辑

方法二和方法三中用户自定义的节点元素比较逻辑类是通过创建PersonComparator1和PersonComparator2类的方法实现的。实际应用中，为了简化代码，我们也可以通过创建匿名类的方法来实现自定义的比较逻辑。

Main.java文件：

BinarySearchTree<Person> bst4 = new BinarySearchTree<>(new Comparator<Person>() {
		//自定义比较逻辑
		@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"));

c、值相等元素的处理

当新添加元素的值与树中某一节点的值相等时，我们可以选择直接返回（不处理），也可以选择让新元素覆盖旧的值。实际应用中，应根据具体需求自行处理。

由于添加的节点元素对象可能不完全相等。即：定义比较逻辑的成员变量的值相同，但其它成员变量的值不同的情况。如：依次添加两个“age=12，name=Tom”、“age=12，name=Jack”的Person对象。为了保证各节点均为最新元素，我们这里选择让新元素覆盖旧的值。即：

BinarySearchTree.java文件：

node.element = element;//让新元素覆盖旧的值

d、★在哪添加新元素？

通过分析我们可以发现：

• 若二叉搜索树添加的是第一个结点，则直接给根节点指针赋值；

• 若添加新元素不是第一个结点，则只需：

  ①从根节点开始，将新增元素的值e1与当前节点的值e2进行比较。若e1>e2，则再将e1与当前节点的右子节点进行比较；若e1<e2，则再将e1与当前节点的左子节点进行比较；若e1=e2，则让新元素覆盖旧的值。直到找到待添加元素的父节点为止（即：直到待比较节点不存在为止）；
  
  ②创建新节点；
  
  ③将新节点添加到其父节点的左侧或右侧，让其成为父节点的左子节点（e1<e2）或右子节点（e1>e2）；
  
  ④size++。

  如图下所示：

注：

• 二叉搜索树新添加的节点一定会成为树的叶子节点，但它的父节点不一定是叶子节点。
• 当新添加元素的值与树中所有节点的值均不相等时，完成添加操作后，新添加的元素一定会成为树的叶子节点。新添加元素的左右子节点一定为空，即不存在任何子树。
• 永远不会出现将在树的中间断开，在其中插入新元素后，再分别将其与前面的父节点和后面的子树连接的情况。

BinarySearchTree.java文件：

/*
 * 添加元素
 * @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++;
}

（6）获取前驱和后继节点

a、获取一个节点的前驱节点

前驱节点（predecessor）：指中序遍历时的前一个节点。

注：

• 前驱节点的定义适用于所有的二叉树。
• 若二叉树是二叉搜索树，则前驱节点就是前一个比它小的节点。

**示例：**对于如下图所示的二叉搜索树，节点6、13、8、7、11、9、1的前驱节点分别是：5、12、7、6、10、8、null。

对于所有的二叉树，通过分析我们可以发现：

• 当node.left != null时，predecessor = node.left.right.right.right...，直到找到node左子树的最右边（right == null）时终止，并返回该节点。
• 当node.left == null && node.parent != null时，predecessor = node.parent.parent.parent...，直到找到node是在哪个节点的右子树中（直到找到的节点在其父节点的右子树中）时终止，并返回该节点（的父节点）。
• 当node.left == null && node.parent == null时，该节点没有前驱节点。（如：没有左子树的根节点）

**注：**如果一个节点的度为2，那么它的前驱节点的度只可能是1和0。

BinarySearchTree.java文件：

@SuppressWarnings("unused")
/*
 * 获取某一节点的前驱节点
 * @param node
 * @return
 * */
private 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;
}

b、获取一个节点的后继节点

后继节点（successor）：指中序遍历时的后一个节点。

注：

• 后继节点的定义适用于所有的二叉树。
• 若二叉树是二叉搜索树，则后继节点就是后一个比它大的节点。

**示例：**对于如下图所示的二叉搜索树，节点1、8、4、7、6、3、11的后继节点分别是2、9、5、8、7、4、null。

对于所有的二叉树，通过分析我们可以发现：

• 当node.right != null时，successor = node.right.left.left.left...，直到找到node右子树的最左边（left == null）时终止，并返回该节点。
• 当node.right == null && node.parent != null时，successor = node.parent.parent.parent...，直到找到node是在哪个节点的左子树中（直到找到的节点在其父节点的左子树中）时终止，并返回该节点（的父节点）。
• 当node.right == null && node.parent == null时，，该节点没有后继节点。（如：没有右子树的根节点）

**注：**如果一个节点的度为2，那么它的后继节点的度只可能是1和0。

BinarySearchTree.java文件：

@SuppressWarnings("unused")
/*
 * 获取某一节点的后继节点
 * @param node
 * @return
 * */
private 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;
}

（7）实现remove(E element)接口

a、删除叶子节点

如果待删除的节点是叶子节点，那么直接删除即可。具体地：

• 若待删除叶子节点是其父节点的左子节点（node == node.parent.left），则只需让该叶子节点的父节点的左子树为空（node.parent.left = null）即可。
• 若待删除叶子节点是其父节点的右子节点（node == node.parent.right），则只需让该叶子节点的父节点的右子树为空（node.parent.right= null）即可。
• 若待删除叶子节点的父节点为空（node.parent == null），则该节点为根节点，只需让root = null即可。

b、删除度为1的节点

**如果待删除节点的度为1，那么要删除该节点只需：用其子节点替代该节点的位置即可。**具体地：

• 若待删除节点是其父节点的左子节点，则只需让：

  • node.child.parent = node.parent ；
  • node.parent.left = node.child即可。

• 若待删除节点是其父节点的右子节点，则只需让：

  • node.child.parent = node.parent ；
  • node.parent.right = node.child即可。

• 若待删除节点node是根节点。则只需让：

  • root = node.child；
  • node.child.parent = null即可。

c、删除度为2的节点

为了不破坏二叉搜索树的性质，如果待删除节点的度为2，那么要删除该节点只需：

• 先用该节点的前驱（或后继）节点的值覆盖该节点的值（不是删除该节点，是值覆盖）；
• 然后再删除该节点的原来的前驱（或后继）节点即可。

注：

• 如果一个节点的度为2，那么它的前驱和后继节点的度只可能是1和0。
• 删除度为2的待删除节点的前驱（或后继）节点，即转化为删除上述度为1的节点或叶子节点。
• 当删除度为2的节点时，真正被删除的其实是该节点的前驱（或后继）节点。
• 二叉搜索树删除某一个节点后仍然是一颗二叉搜索树。

BinarySearchTree.java文件：

/*
 * 删除元素
 * @param element
 * @return
 * */
public void remove(E element) {
	//删除该元素所在的节点
	remove(node(element));
}

/*
 * 查找元素所在的节点
 * @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 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;
		}
	}
}

**注：**用户处理（添加、删除、查找等）的是元素，他们是不关心二叉树内部节点结构的。

（8）实现contains(E element)接口

如：查找二叉搜索树中是否存在节点元素为4的节点。

BinarySearchTree.java文件：

/*
 * 查找二叉搜索树中是否包含某元素
 * @param element
 * @return
 * */
public boolean contains(E element) {
	//查找元素所在的节点是否存在
	return node(element) != null;
}

（9）打印二叉搜索树中的所有元素

为了更加直观地展示二叉（搜索）树，我们可以将二叉（搜索）树中的所有元素打印出来。

方法一：（中序）遍历打印法

在Java中，当我们要打印某一个对象时，系统内部其实是通过调用toString()方法来实现的。默认情况下，打印的是该对象的类名。为了打印二叉（搜索）树中的所有元素，我们只需重写（也称覆盖）toString()方法，并在其中完成二叉（搜索）树的中序遍历和字符串的拼接工作即可。

注：Java中字符串拼接建议使用StringBuilder类。

BinarySearchTree.java文件：

/*
 * 打印二叉搜索树中的所有元素（重写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封装的二叉树打印接口（使用简单、显示更直观）（源码：https://github.com/CoderMJLee/BinaryTrees）。

使用它只需：

① 下载小码哥MJ封装的二叉树打印工具

②让BinaryTreeInfo类实现BinaryTreeInfo接口类。

BinarySearchTree.java文件：

public class BinarySearchTree<E> implements BinaryTreeInfo{

}

③在其内部重写相应的接口函数。

BinarySearchTree.java文件：

/*
 * 使用小码哥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;
}

④这样，我们就可以直接调用MJ封装的二叉树打印接口来打印二叉搜索树中的所有元素了。

main.java文件：

/*
 * 节点元素为数字的二叉搜索树
 * */
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("使用MJ封装的接口打印二叉搜索树: \n");
BinaryTrees.println(bst);

**注：**当节点元素为自定义对象时，为了使打印结果更直观，我们还需要在自定义节点元素类（如：Person类）中重写toString()函数。

Person.java文件：

@Override
public String toString() {
	return name + "(age="+ age +")";//自定义对象节点的打印内容
}

3.2、接口测试

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

Main.java文件：

package com.atangbiji;

import java.util.Comparator;

import com.atangbiji.BinarySearchTree.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);
	}
}

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

4、★ 遍历二叉搜索树

4.1、遍历方式

根据节点访问顺序的不同，二叉树常见的遍历方式有：前序遍历、中序遍历、后序遍历和层序遍历4种。

注：这里介绍的遍历方式适用于所有的二叉树。

（1）前序遍历（递归实现）

所谓前序遍历指的是：根节点放在前面遍历。其节点访问顺序为：①先访问根节点；②再前序遍历左子树；③最后前序遍历右子树。

**注：**步骤②与步骤③可交换。

• 编程实现

BinarySearchTree.java文件：

//前序遍历二叉搜索树【用户不可以自定义对节点元素的处理逻辑】
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);
}

（2）中序遍历（递归实现）

所谓中序遍历指的是：根节点放在中间遍历。其节点访问顺序为：①先中序遍历左子树；②再访问根节点；③最后中序遍历右子树。

**注：**步骤①与步骤③可交换。

通过分析发现：若二叉搜索树采用上述中序遍历，则各节点按从小到大的顺序访问。

同理，若二叉搜索树按先中序遍历右子树、再访问根节点、最后中序遍历左子树的顺序遍历，则各节点按从大到小的顺序访问。

结论：二叉搜索树的中序遍历结果是**从小到大（升序）或从大到小（降序）**顺序访问的。

• 编程实现

BinarySearchTree.java文件：

//中序遍历二叉搜索树【用户不可以自定义对节点元素的处理逻辑】
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);
}

（3）后续遍历（递归实现）

所谓后序遍历指的是：根节点放在后面遍历。其节点访问顺序为：①先后序遍历左子树；②再后序遍历右子树；③最后访问根节点。

**注：**步骤①与步骤②可交换。

• 编程实现

BinarySearchTree.java文件：

//后序遍历二叉搜索树【用户不可以自定义对节点元素的处理逻辑】
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);
}

（4）层序遍历（队列实现）

• 访问顺序：从上往下、从左往右依次访问。
• 层序遍历不再是递归调用。
• 一般使用队列来实现。

**思路：**①将根节点入队；②循环执行如下操作，直到队列为空为止：a.将队头节点A出队，进行访问；b.将A的左子节点入队；c.将A的右子节点入队。

• 编程实现

BinarySearchTree.java文件：

/*
 * 层序遍历二叉搜索树（队列实现）【用户不可以自定义对节点元素的处理逻辑】
 * @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);
		}
	}
}

注：上述层序遍历的代码要达应达到会默写的熟练程度。

4.2、遍历接口设计

4.2.1、编程实现

前面虽然已经实现了二叉树的前序、中序、后序和层序遍历，但它们内部只实现了打印各节点元素的功能。为了满足用户遍历时对节点元素的不同操作需求，我们可以参照“二叉搜索树节点元素的比较”的“Comparator接口法”，在设计遍历接口时，将用户对节点元素的处理逻辑作为形参传入。这样用户便可以在调用遍历接口时在二叉搜索树类的外部自定义节点元素的处理逻辑了。具体实现过程如下：

①在BinarySearchTree类内部自定义一个用户对节点元素的处理逻辑接口。

BinarySearchTree.java文件：

//用户自定义对节点元素的处理逻辑
public static interface Visitor<E>{
	void visit(E element);
}

②新建一个二叉搜索树的层序遍历接口函数，并将其形参设计为用户自定义的对节点元素的处理逻辑接口。

BinarySearchTree.java文件：

/*
 * 二叉搜索树的层序遍历接口（队列实现）【用户可自定义对节点元素的处理逻辑】
 * @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();
		//在此处通过自定义的接口将节点元素传出，供用户在二叉搜索树类的外部自定义节点元素的处理逻辑
		visitor.visit(node.element);
		
		if (node.left != null) {
			//左子节点入队
			queue.offer(node.left);
		}
		
		if (node.right != null) {
			//右子节点入队
			queue.offer(node.right);
		}
	}
}

③类似地，我们可以对二叉搜索树的前序遍历、中序遍历和后序遍历接口进行设计。

BinarySearchTree.java文件：

//二叉搜索树的前序遍历接口【用户可自定义对节点元素的处理逻辑】
public void preorder(Visitor<E> visitor) {
	preorder(root,visitor);
}
/*
 * 二叉搜索树的前序遍历（递归调用）
 * @param: node,visitor
 * @return
 * */
private void preorder(Node<E> node, Visitor<E> visitor)  {
	//递归基
	if (node == null || visitor == null) 
		return;
	
	//先访问根节点的值
	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)  {
	//递归基
	if (node == null || visitor == null) 
		return;
	
	//先前序遍历左子树
	inorder(node.left,visitor);
	//再访问根节点的值
	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)  {
	//递归基
	if (node == null || visitor == null) 
		return;
	
	//先前序遍历左子树
	postorder(node.left,visitor);
	//最后前序遍历右子树
	postorder(node.right,visitor);
	//再访问根节点的值
	visitor.visit(node.element);
}

4.2.2、遍历接口测试

此时，用户在调用遍历接口时，便可以在二叉搜索树类的外部自定义节点元素的处理逻辑，并将其作为形参传入接口函数了。

Main.java文件：

package com.atangbiji;

import com.atangbiji.BinarySearchTree.Visitor;

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 使用MJ封装的接口打印二叉搜索树: \n");
		BinaryTrees.println(bst);
		System.out.println("\n" + "遍历二叉搜索树（全部节点）: \n");
		//调用层序遍历接口
		System.out.println("\n" + "层序遍历二叉搜索树：");
		bst.levelOrder(new Visitor<Integer>() {
			
			@Override
			//在visit接口函数中实现节点元素的处理逻辑
			public void visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
			}
		});
		
		//调用前序遍历接口
		System.out.println("\n" + "前序遍历二叉搜索树：");
		bst.preorder(new Visitor<Integer>() {

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

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

			@Override
			public void visit(Integer element) {
				// TODO Auto-generated method stub
				System.out.print("_" + element + "; ");
			}
		});
	}
}

运行该程序，各节点元素便按照自定义的处理逻辑：按**“_节点元素;”**的格式打印各元素。输出结果如下图所示：

4.3、增强遍历接口

4.3.1、编程实现

前面实现的遍历接口是把二叉树中所有元素都访问一遍。而实际项目中，我们可能只需要遍历二叉树的前面一部分节点。因此，为了提高程序性能，让用户可以随时停止遍历，我们需要对上述遍历接口进行功能增强。具体实现过程如下：

①在BinarySearchTree类内部：

• 先将遍历接口修改成一个抽象类，然后再在该抽象类中添加一个成员变量boolean isStop用来记录是否在当前节点停止遍历。
• 然后再将用户对节点元素的处理逻辑接口修改成一个返回值是boolean类型的抽象函数。如果返回false（默认），就继续遍历；如果返回true，就停止遍历。

BinarySearchTree.java文件：

//用户自定义对节点元素的处理逻辑（抽象类）
public static abstract class Visitor<E>{
	boolean isStoped;
	/**
	 * 抽象类中的抽象函数类似于接口函数
	 * @return 如果返回false（默认），就继续遍历;如果返回true，就停止遍历。
	 */
	abstract boolean visit(E element);
}

②在上述层序遍历接口的基础上，增加判断是否停止遍历功能。

BinarySearchTree.java文件：

/*
 * 二叉搜索树的层序遍历接口（队列实现）
 * @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);
		}
	}
}

③类似地，对二叉搜索树的前序遍历、中序遍历和后序遍历接口进行修改。

• 在遍历之前判断是否继续本次遍历
• 在访问节点元素时记录下一次遍历的状态。

BinarySearchTree.java文件：

//二叉搜索树的前序遍历接口
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);
}

注：

• 在中序遍历中，如果在当前节点的左子树中遍历到了用户想要停止的节点，那么同样要停止递归；
• 在后序遍历中，如果在当前节点的左子树或右子树中遍历到了用户想要停止的节点，那么同样要停止递归。

4.3.2、增强遍历接口测试

此时，用户在调用遍历增强接口时，便可以在二叉搜索树类的外部自定义节点元素的处理逻辑，将其作为形参传入接口函数，并随时停止遍历了。

Main.java文件：

package com.atangbiji;

import com.atangbiji.BinarySearchTree.Visitor;

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" + "使用MJ封装的接口打印二叉搜索树: \n");
		BinaryTrees.println(bst);		
		System.out.println("\n" + "遍历二叉搜索树（部分节点）: \n");
		//调用层序遍历接口
		System.out.println("\n" + "层序遍历二叉搜索树（部分节点）：");
		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" + "前序遍历二叉搜索树（部分节点）：");
		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" + "中序遍历二叉搜索树（部分节点）：");
		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" + "后序遍历二叉搜索树（部分节点）：");
		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;
			}
		});
	}
}

运行该程序，各节点元素便按照自定义的处理逻辑：按**“_节点元素;”**的格式打印各元素。输出结果如下图所示：

附1：遍历的常见应用（补充接口）

Ⅰ、计算二叉树的高度

方法一：递归实现

思路：

• 当前节点的高度 = 当前节点左右子节点高度的较大者 + 1；
• 二叉树的高度 = 跟节点的高度。

BinarySearchTree.java文件：

/*
 * 计算二叉树的高度（递归调用）
 * @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));
}

方法二：层序遍历实现

思路：

• 二叉树的高度 = 二叉树的层数 = 层序遍历时访问的层数；
• 当每一层节点全部出栈时，栈内元素刚好全部是下一层的所有节点。

BinarySearchTree.java文件：

/*
 * 计算二叉树的高度（层序遍历）
 * @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;
}

Ⅱ、判断一棵树是否为完全二叉树

方法一：层序遍历实现方式1

**思路：**根据完全二叉树的定义可知：

• 如果树为空，返回false；
• 如果树不为空，开始层序遍历二叉树（用队列）
  • 如果node.left!=null && node.right!=null，将node.left、node.right按顺序入队；
  • 如果node.left==null && node.right!=null，返回false；
  • 如果node.left!=null && node.right==null或node.left==null && node.right==null，那么后面遍历的节点应该都为叶子节点，才是完全二叉树 ；否则返回false。

BinarySearchTree.java文件：

/*
 * 判断一棵树是否为完全二叉树（层序遍历）
 * @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;
}

**注：**为了使用方便，我们在内部静态节点类中封装了两个接口函数：一个用于判断该节点是否为叶子节点；一个用于判断该节点是否拥有两个子节点。

BinarySearchTree.java文件：

//内部静态节点类
private 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;
	}
}

方法二：层序遍历实现方式2（推荐）

思路：

• 如果树为空，返回false；
• 如果树不为空，开始层序遍历二叉树（用队列）
  • 如果node.left!=null，那么将node.left入队；
  • 如果node.left==null && node.right!=null，返回false；
  • 如果node.right!=null，那么将node.right入队；
  • 如果node.right==null，那么后面遍历的节点应该都为叶子节点，才是完全二叉树；否则返回false。

BinarySearchTree.java文件：

/*
 * 判断一棵树是否为完全二叉树（层序遍历）
 * @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.left == null && node.right == null
            //或node.left != null && node.right == null
			leaf = true;
		}
	}
	return true;
}

Ⅲ、翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

**思路：**遍历所有节点，把所有节点的左右子节点都交换即可。

方法一：使用前序遍历

public TreeNode invertTree(TreeNode root) {
	//递归基
	if (root == null) 
		return root;
    //交换遍历到节点的左右子节点
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    //再前序遍历左子树
    invertTree(root.left);
    //最后前序遍历右子树
    invertTree(root.right);

	return root;
}

方法二：使用后序遍历

public TreeNode invertTree(TreeNode root) {
	//递归基
	if (root == null) 
		return root;
    //先后序遍历左子树
    invertTree(root.left);
    //再后序遍历右子树
    invertTree(root.right);
	//最后交换遍历到节点的左右子节点
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
	return root;
}

方法三：使用中序遍历

public TreeNode invertTree(TreeNode root) {
	//递归基
	if (root == null) 
		return root;
	//先中序遍历左子树
	invertTree(root.left);
    //再交换遍历到节点的左右子节点
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    //最后中序遍历交换前的右子树(即:交换后的左子树)
    invertTree(root.left);

	return root;
}

方法四：使用层序遍历

public TreeNode invertTree(TreeNode root) {
	if (root == null) 
		return root;
	//使用Java自带的队列
	Queue<TreeNode> queue = new LinkedList<>();
	queue.offer(root);//根节点入队
	
	while (!queue.isEmpty()) {
        //头结点出队
        TreeNode node = queue.poll();
        //交换遍历到节点的左右子节点
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        if (node.left != null) {
            //左子节点入队
            queue.offer(node.left);
        }

        if (node.right != null) {
            //右子节点入队
            queue.offer(node.right);
        }
	}

	return root;
}

附2：根据遍历结果重构二叉树

结论：

• 如果已知**“前序遍历 + 中序遍历”的遍历结果，那么可以保证重构出唯一**的一棵二叉树。

  

• 如果已知**"后序遍历 + 中序遍历"的遍历结果，那么可以保证重构出唯一**的一棵二叉树。

  

• 如果已知**“前序遍历 + 后序遍历”**的遍历结果，那么：

  • 若它是一颗棵真二叉树（即：任意节点的度只能为0或2），则可以保证重构出唯一的一棵二叉树；
  • 否则重构结果不唯一。（即：若存在度为1的节点，则重构结果不唯一）

**示例：**已知某二叉树的前序遍历结果为：4 2 1 3 6 5；中序遍历结果：1 2 3 4 5 6。那么该二叉树的结构一定为：

附：推荐一些神奇的网站

• http://520it.com/binarytrees/
• http://btv.melezinek.cz/binary-search-tree.html
• https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• https://yangez.github.io/btree-js
• https://www.codelike.in

附：小码哥MJ封装的二叉树打印接口

点击下载附件

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

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

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

如何获取源代码？

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

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