05二叉搜索树

1、树相关的概念

节点：

树上的每一个元素所在的节点

根节点：

最顶部的节点，如1节点，一棵树最多只有一个根节点

父节点：

一个节点上一层的与该节点连接的节点

子节点：

一个节点下一层的节点

兄弟节点：

同一层的节点

边：

连接父节点和子节点的连线

节点的度：

一个节点子树的个数

树的度：

所有节点度中最大的值

叶子节点：

度为0的节点

层数：

根节点在第一次，根节点的子节点在第二层，以此类推

节点的深度：

从根节点到当前节点唯一路径所经过的节点总数

节点的高度：

从当前节点到最远叶子节点所经历的节点总数

树的深度：

所有节点深度中的最大值

树的高度：

所有节点高度中的最大值

一般来说树的高度等于树的深度。

一棵树可以没有任何节点。

---

2、二叉树及其性质

二叉树的特点：

二叉树中每一个节点的度最大为2左子树和右子树是有顺序的即使只有一个子树，也要区分左右子树

二叉树的性质：

非空二叉树的第i层最多有2^(i-1)个节点在高度为h的二叉树上最多有2^h - 1个节点对于任意一棵非空二叉树，如果叶子节点的个数为n0，度为2的节点的个数为n2，则n0 = n2 + 1假设如果叶子节点的个数为n0，度为2的节点的个数为n2，度为1的节点的个数为n1，则该二叉树节点总数n = n0 + n1 + n2二叉树的边数T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1

真二叉树：

所有节点的度要么为0，要么为2

满二叉树：

所有节点的度要么为0，要么为2，并且所有的叶子节点都应该在最后一层在同样高度的二叉树中，满二叉树的叶子节点最多，并且节点总数最多真二叉树不一定是满二叉树，满二叉树一定是真二叉树

完全二叉树：

叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐完全二叉树从根节点到倒数第二层节点是满二叉树满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树度为1的节点只有左子树度为1的节点数量要么为1要么为0同样节点的二叉树，完全二叉树高度最小假设完全二叉树的高度为h，则总结点数量至少为2^{(h-1)，最多有2}h - 1个节点如果总节点数量为n，则2^(h-1) < n < 2^h - 1,并且h = log2n向下取整再加1

面试题：一个完全二叉树总节点数量为768，问叶子节点的数量是多少？

3、二叉搜索树

二叉搜索树是什么：

假设要在n个动态的整数中搜索某一个数，应该用什么方式？

可以将数据存放在动态数组中，遍历数组进行查找，此时平均时间复杂度为O（n）如果使用二分查找对数组进行查找，此时最坏时间复杂度为O（logn），但是添加和删除元素的平均时间复杂度是O（n）此时需要使用二叉搜索树，添加、删除、查找的最坏时间复杂度都可以优化到O（logn）

对外提供的方法：

代码实现：

属性及静态私有内部类：

private int size; /** *根节点 */ private Node<E> root; /** * 比较器 */ private Comparator comparator; public BinarySearchTree(){ } public BinarySearchTree(Comparator comparator){ this.comparator = comparator; } /** * 定义私有类节点，拥有元素以及左节点和右节点，也就是左子树和右子树,以及父节点 * @param <E> */ 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; } @Override public String toString() { return element.toString() + ",p=" + (parent == null ? null : parent.element); } }

私有类节点的构造方法只需要传入元素和父节点即可，因为在添加元素时会判断左右节点，给相应的位置赋值。

往二叉搜索树里添加元素时，每一个元素都需要进行比较。这里有两种比较方式：

第一种用到了比较器，可以自定义比较规则，用来比较添加元素的与树中已有元素的大小；第二种则是让相互比较的两个元素都实现Comparable接口，调用该接口的compareTo方法进行比较。

在二叉树中的比较方法如下：

public int compare(E e1, E e2){ if (comparator == null){ //如果比较器为null，则说明按照元素自己的比较规则来进行比较 return ((Comparable<E>)e1).compareTo(e2); } //程序到此处说明比较器不为空，则按照比较器中的规则来进行比较 return comparator.compare(e1, e2); }

如果使用无参构造创建二叉搜索树，则将传入的元素强转为Comparable类型进行比较（前提是这个元素的类必须实现该接口）。

如果使用有参构造创建二叉搜索树，则需要传入比较器为参数，调用该比较器进行比较，比较器可以使用匿名内部类的方式传入。如下,自定义比较方法，按照名称来进行比较。

BinarySearchTree<User> tree = new BinarySearchTree<>(new Comparator() { @Override public int compare(Object o1, Object o2) { return ((User)o2).getAge() - ((User)o1).getAge(); } });

添加方法：

public void add(E element){ //先检查参数是否为空 checkElement(element); if (root == null){ //此时说明是第一个节点 root = new Node<>(element, null); size++; }else { Node<E> parent = root; Node<E> node = root; int result = 0; while (node != null){ result = compare(element, node.element); parent = node; if (result < 0){ //寻找左子树 node = node.left; }else if (result > 0){ //寻找右子树 node = node.right; }else { //相等则覆盖 node.element = element; return; } } //在这里添加节点 Node<E> newNode = new Node<>(element, parent); if (result > 0){ parent.right = newNode; }else { parent.left = newNode; } size++; } } public void checkElement(E element){ if (element == null){ throw new IllegalArgumentException("element can't be null!"); } }

添加的元素不能为空，因此首先调用checkElement方法进行元素检查

然后判断要添加的节点是否为根节点，如果是根节点则让root指向新创建的节点。

如果不是根节点，则使用while循环让该元素与树中节点中的元素进行比较

先声明两个变量parent和node

parent用来保存while循环中的父节点，以用于后面给父节点的left或者right赋值。每次循环中的都是parent都与node相等

node用来表示树中用于比较的节点。

当node为空时，说明该位置没有子树了，元素应该被放在这个位置，此时while循环结束。

新建一个元素，指定parent为循环中保存的parent

还应声明一个result变量，用来记录要往左子树还是右子树添加元素。

删除方法：

分析：

分为三种情况，删除度为0，1，2的节点。

先说删除度为0的节点，也就是叶子节点

只需要让该节点的父节点的right或者left指向null即可。

注意：如果父节点为null，则说明删除的是根节点，也是叶子节点，只需要让root=null即可。

删除度为1的节点

先判断该节点是父节点的左节点还是右节点，然后让该节点的父节点的right或者left指向该节点的子节点。

删除度为2的节点

一个节点的度为2，在二叉搜索树中，该节点左边的所有节点的值都小于该节点，右边的所有节点的值都大于该节点，因此只要找到该节点的前驱节点或者后继节点，将前驱/后继节点中的值赋给要删除的节点，然后删除前驱/后继节点即可。

前驱节点：中序遍历中，一个节点的前一个节点

后继节点：中序遍历中，一个节点的后一个节点

前驱节点怎么获得：

将该节点前面的所有节点都遍历到，其中遍历到的最后一个节点就是前驱节点。

如果左子树不为空，那么左子树中最大的节点就是左子树中最右边的节点。

node.left.right.right…

如果左子树为空，那么就找比他小的父节点

如本图中，找9的前驱节点，9是10的左子树，10是13的左子树，证明这些数字都比9大，因此当遇到比9小的父节点时就是9的前驱节点，13的父节点为8，13是8的右子树，因此当某一个祖父节点是其父节点的右子树时，这个父节点就是要找的前驱节点。

代码：

private Node<E> predesessor(Node<E> node){ //节点为空直接返回null if (node == null) return null; //第一种情况，左子树不为空 if (node.left != null){ node = node.left; while (node.right != null){ node = node.right; } return node; } while (node.parent != null && node != node.parent.right){ node = node.parent; } return node.parent; }

后继节点的获得方式刚好于前驱节点相反

private Node<E> successor(Node<E> node){ if (node == null) return null; if (node.right != null){ node = node.right; while (node.left != null){ node = node.left; } return node; } while (node.parent != null && node != node.parent.left){ node = node.parent; } return node.parent; }

删除方法的代码实现

public void remove(E element){ if (element == null) return; size--; remove(node(element)); }

对外提供的方法，在内部调用了私有的删除方法，因为删除涉及到节点，节点对外界来说是不可见的。

private Node<E> node(E element){ Node<E> node = root; while (node != null){ int result = compare(element, node.element); if (result == 0) { return node; }else if (result < 0){ node = node.left; }else { node = node.right; } } return null; }

在这里先根据传入的元素获取节点，根据元素大小的比较来找到节点。

private void remove(Node<E> node){ if (node == null) return; if (node.right != null && node.left != null){ //说明要删除度为2的节点 //找到前驱或者后继节点 Node<E> pre = predesessor(node); node.element = pre.element; node = pre; } //程序走到这里说明有两种可能： //1.要删除的节点度为1或者0 //2.要删除的节点度为2，前面已经将要删除的节点替换为前驱节点，这里只需要删除前驱节点即可，前驱节点的度只能为1或者0 //因此代码可以放到一起 //这里用来判断应该用要删除的节点到底存在左节点还是右节点，又或者是没有节点， //如果有左或者右节点，那么用左/右节点取代原来的节点如果没有节点，那么不管三目运算符取哪一个结果，这个替换节点都为null Node<E> replacement = node.right == null ? node.left : node.right; if (replacement == null){ //说明要删除的节点为叶子节点 if (node.parent == null){ //说明要删除的节点为根节点，并且是叶子节点 root = null; }else if (node == node.parent.right){ node.parent.right = null; }else { node.parent.left = null; } }else { //说明度为1，让替换节点的parent指向要删除节点的parent replacement.parent = node.parent; if (node.parent == null){ //说明该节点为根节点 root = replacement; }else if(node == node.parent.left){ node.parent.left = replacement; }else { node.parent.right = replacement; } } }

---

4、二叉树的遍历

前序遍历：

先访问根节点的值，再访问左右子树

public void preorderTraver(Visitor visitor){ preorderTraver(root, visitor); } /** * 前序遍历的实现，使用递归 * @param node */ private void preorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null) return; //前序首先访问根节点 visitor.visit(node.element); //访问左右子树 preorderTraver(node.left, visitor); preorderTraver(node.right, visitor); }

中序遍历：

先访问左子树上的节点，再访问根节点，最后访问右节点

/** * 中序遍历，按照从小到大的顺序 */ public void inorderTraver(Visitor visitor){ inorderTraver(root, visitor); } private void inorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null) return; //中序遍历首先访问左子树 inorderTraver(node.left, visitor); //然后访问自己 visitor.visit(node.element); //最后访问右子树 inorderTraver(node.right, visitor); }

后序遍历：

先访问左右子树，然后再访问根节点

public void postorderTraver(Visitor visitor){ postorderTraver(root, visitor); } /** * 后序遍历的实现，使用递归 * @param node */ private void postorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null) return; //前序首先访问左右树 postorderTraver(node.left, visitor); postorderTraver(node.right, visitor); //再访问根节点 visitor.visit(node.element); }

层序遍历：

按照从上到下从左到右一层一层的方式进行遍历。

这里需要使用到队列，用到了先进先出的原则。

首先让根节点入队，然后进行访问时让根节点出队，获取根节点的值，最后让根节点的左右节点入队，使用循环的方式循环此操作，每当一个节点出队后就将该节点的左右节点加入到队列中去。

public void LevelOrderTraver(Visitor visitor){ if (visitor == null || root == null) return; //使用while循环以及队列来访问每一层的元素 Node<E> node = root; Queue<Node<E>> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ Node<E> eNode = queue.poll(); visitor.visit(eNode.element); if (eNode.left != null) queue.offer(eNode.left); if (eNode.right != null) queue.offer(eNode.right); } }

注意点:

如果要想让外界使用遍历的结果，我们在这里应该给外界定义一个接口使用，让外界自定义遍历结果的处理方法。

/** * 对外提供遍历的接口，支持前中后层四种遍历方式 */ public static interface Visitor<E>{ //外界调用者可以自定义对遍历结果的处理方式 void visit(E element); }

当外界需要进行遍历时，需要实现该接口，自己实现方法来自定义处理方式。

每一种遍历方式都有一个visitor参数

public void LevelOrderTraver(Visitor visitor) public void postorderTraver(Visitor visitor) public void inorderTraver(Visitor visitor) public void preorderTraver(Visitor visitor)

将每一个遍历结果交给visit方法进行处理。

visitor.visit(eNode.element);

遍历接口的增强：

需求：

有时候只需要遍历到某一个元素就停止遍历，这时候不需要遍历所有元素，该如何实现这个需求呢？

将Visitor接口变为抽象类定义一个布尔类型成员变量stop，并且将visit的返回值类型变为boolean在重写visit方法时可以根据需求改变返回值为true或者false在每种前中后序三种遍历方法中使用成员变量stop接收visit方法的返回值在每次执行visit方法前根据stop的值判断是否停止遍历。在每次进行递归调用前根据stop的值判断是否停止递归。

改进之后的代码：

public static abstract class Visitor<E>{ //定义一个成员遍历，当stop为true时，停止遍历 boolean stop; //外界调用者可以自定义对遍历结果的处理方式 abstract boolean visit(E element); } /** * 前序遍历对外提供的方法 */ public void preorderTraver(Visitor visitor){ preorderTraver(root, visitor); } /** * 前序遍历的实现，使用递归 * @param node */ private void preorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null || visitor.stop) return; //前序首先访问根节点 visitor.stop = visitor.visit(node.element); //访问左右子树 preorderTraver(node.left, visitor); preorderTraver(node.right, visitor); } /** * 中序遍历，按照从小到大的顺序 */ public void inorderTraver(Visitor visitor){ inorderTraver(root, visitor); } private void inorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null || visitor.stop) return; //中序遍历首先访问左子树 inorderTraver(node.left, visitor); if (visitor.stop) return;//如果上一个递归中stop变为了true，那么下面就不应该再进行元素的打印了 //然后访问自己 visitor.stop = visitor.visit(node.element); //最后访问右子树 inorderTraver(node.right, visitor); } /** * 后序遍历对外提供的方法 */ public void postorderTraver(Visitor visitor){ postorderTraver(root, visitor); } /** * 后序遍历的实现，使用递归 * @param node */ private void postorderTraver(Node<E> node, Visitor visitor){ if (node == null || visitor == null || visitor.stop) return; //前序首先访问左右树 postorderTraver(node.left, visitor); postorderTraver(node.right, visitor); //再访问根节点 if (visitor.stop) return;//如果上一个递归中stop变为了true，那么下面就不应该再进行元素的打印了 visitor.stop = visitor.visit(node.element); } /** * 层序遍历，使用迭代的方式 * @param visitor */ public void LevelOrderTraver(Visitor visitor){ if (visitor == null || root == null) return; //使用while循环以及队列来访问每一层的元素 Node<E> node = root; Queue<Node<E>> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ Node<E> eNode = queue.poll(); boolean stop = visitor.visit(eNode.element); if (stop) return; if (eNode.left != null) queue.offer(eNode.left); if (eNode.right != null) queue.offer(eNode.right); } }