数据结构与算法（第一季）：二叉搜索树

2021-11-04 本文已影响0人萧1帅

一、二叉搜索树

二叉搜索树是二叉树的一种, 是应用非常广泛的一种二叉树, 英文简称为BST
- 又被称为: 二叉查找树、二叉排序树
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一颗二叉搜索树

image

二叉树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具备可比较性
- 比如int、double等
- 如果是自定义类型, 需要指定比较方式
- 不允许为null

二、二叉搜索树的接口设计

// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 清空所有元素
void clear();
// 添加元素
void add(E element);
// 删除元素
void remove(E element);
// 是否包含某元素
boolean contains(E element);
复制代码

注意: 二叉树的元素没有索引的概念

三、二叉搜索树的实现

1、类的设计

创建类BinarySearchTree, 并添加几个属性
- size属性, 用来计算已保存元素个数
- root属性, 用来保存根节点
创建私有类Node, 用来创建节点, 并添加几个属性
- element: 用来保存元素
- left: 保存左子节点
- right: 保存右子节点
- parent: 保存父节点

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        @SuppressWarnings("unused")
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
}
复制代码

2、添加节点

首先, 要保证添加的节点不能为空, 所以需要对null进行处理

// 当element为null时, 抛出异常
private void elementNotNullElement(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be  null");
    }
}
复制代码

此时的add方法如下

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
}
复制代码

当添加第一个元素, 即添加根节点时, 直接添加到root属性即可

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
    if (root == null) {
        root = new Node<>(element, null);
        size++;
    }
}
复制代码

当添加的节点不是根节点时, 需要找到新节点的父节点, 然后再根据元素的大小判断出添加到父节点的left或者right
当新元素 > 节点元素时, 向右查找子节点, 当新元素 < 节点元素时, 向左查找子节点, 伪代码如下

if (新元素 > 节点元素值) {
    找到节点的右子节点
}else if (新元素 < 节点元素值) {
    找到节点的左子节点
}else {
    新元素覆盖旧元素
}
复制代码

首先创建一个方法, 用来返回两个元素的大小, compare方法中的实现, 根据个人的需要而定

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    // 此处判断e1和e2的大小
    return 0;
}
复制代码

实现代码如下, 可以找到root节点的下一个节点

Node<E> node = root;
int cmp = compare(element, node.element);
if (cmp > 0) {
    node = node.right;
}else if (cmp < 0) {
    node = node.left;
}else {
    node.element = element;
    return;
}
复制代码

通过循环, 就可以找到最终添加新节点的父节点, 我们使用parent记录最终的父节点, cmp记录最后一次比较的结果

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
    if (root == null) {
        root = new Node<>(element, null);
        size++;
    }

    // 记录最终添加新节点的父节点
    Node<E> parent = root;
    // 需要查询的节点
    Node<E> node = root;
    // 记录最后一次比较结果
    int cmp = 0;
    while (node != null) {
        // 0: e1等于e2, 正数: e1大于e2, 负数: e1小于e2
        cmp = compare(element, node.element);
        parent = node;
        // cmp大于0, 说明element的值大于当前节点的值, 所以找到当前节点的右子节点
        if (cmp > 0) {
            node = node.right;
        }else if (cmp < 0) {
            // cmp大于0, 说明element的值小于当前节点的值, 所以找到当前节点的左子节点
            node = node.left;
        }else {  // 相等
            node.element = element;
            return;
        }
    }
    // cmp大于0, 说明element的值大于父节点的值, 需要放到右子节点
    if (cmp > 0) {
        parent.right = new Node<>(element, parent);
    }else {
        // cmp小于0, 说明element的值小于父节点的值, 需要放到左子节点
        parent.left = new Node<>(element, parent);
    }
    size++;
}
复制代码

3、节点值的对比

上面定义了方法compare, 用于新添加元素和某个节点元素值的比较
因为二叉搜索树的值必须要有对比性, 所以compare的方法实现如下

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    return ((Comparable<E>)e1).compareTo(e2);
}
复制代码

Comparable中定义了对比两个对象的方法compareTo, 可以由开发者实现如何对比两个对象

上面这种方法, 属于定义在二叉搜索树BinarySearchTree中默认的对比方式
但是在使用的时候, 可能会出现要自定义对比方式的情况
这时可以使用Comparator来实现外部定义对比方式, Comparator是专门用于实现两个对象对比的协议
定义一个属性Comparator<E> comparator, 并在BinarySearchTree初始化方法中传入外部创建的Comparator对象

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
}
复制代码

此时compare方法的内部实现如下

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    if (comparator != null) {
        return comparator.compare(e1, e2);
    }
    return ((Comparable<E>)e1).compareTo(e2);
}
复制代码

此时在Main函数中可以如下使用二叉搜索树BinarySearchTree, 传入一个对象, 该对象实现了两个元素的对比

public class Main {
    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>(new Comparator<Integer>() {
            // 两个值的对比结果
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }
}
复制代码

四、二叉树的遍历

二叉树常见的遍历有四种
- 前序遍历(Preorder Traversal)
- 中序遍历(Inorder Traversal)
- 后序遍历(Postorder Traversal)
- 层序遍历(Level Order Traversal)

1、代码准备

在Main函数中使用二叉搜索树保存一串元素, 用来遍历使用

public class Main {
    public static void main(String[] args) {
        int[] data = new int[] {7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> tree = new BinarySearchTree<>();

        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
    }
}
复制代码

2、前序遍历

遍历顺序: 根节点、前序遍历左子树、前序遍历右子树

image

遍历顺序: 7、4、2、1、3、5、9、8、11、10、12
代码如下

public void preorder() {
    preorder(root);
}
// 通过递归遍历所有的元素
public void preorder(Node<E> node) {
    if (node == null) return;
    // 先查看根节点
    System.out.println(node.element);
    // 再遍历左子树
    preorder(node.left);
    // 最后遍历右子树
    preorder(node.right);
}
复制代码

3、中序遍历

访问书序: 中序遍历左子树、根节点、中序遍历右子树

image

遍历顺序: 1、2、3、4、5、8、9、10、11、12

代码如下

public void inorder() {
    inorder(root);
}

public void inorder(Node<E> node) {
    if (node == null) return;
    // 先中序遍历左子树
    inorder(node.left);
    // 再访问根节点
    System.out.println(node.element);
    // 最后遍历右子树
    inorder(node.right);
}
复制代码

4、后序遍历

访问顺序: 后序遍历左子树, 后序遍历右子树

image

遍历顺序: 1、3、2、5、4、8、10、12、11、9、7
代码如下

public void postorder () {
    postorder(root);
}
public void postorder(Node<E> node) {
    if (node == null) return;
    // 先遍历左子树
    postorder(node.left);
    // 再遍历右子树
    postorder(node.right);
    // 最后访问根节点
    System.out.println(node.element);
}
复制代码

5、层序遍历

访问顺序: 从上到下, 从左到右依次访问每一个节点

image

遍历顺序: 7、4、9、2、5、8、11、1、3、10、12
实现思路: 使用队列
- 将根节点入队
- 循环执行一下操作, 知道队列为空
  - 将对头节点A出队, 进行访问
  - 将A的左子点入队
  - 将A的有节点入队
代码如下

public void levelOrder() {
    if (root == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    // 当queue为空时停止遍历
    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);
        }
    }
}
复制代码

五、外界获取遍历结果

上面的遍历只是在方法内部打印而已, 但是在实际开发中, 是需要使用者能够获取到遍历结果
所以需要对外抛出遍历的元素

1、定义接口, 用于抛出结果

定义接口, 用来向外界抛出遍历结果

public static interface Visitor<E> {
    void visit(E element);
}
复制代码

2、将`Visitor`作为遍历方法的参数

public static interface Visitor<E> {
    void visit(E element);
}
// 前序遍历
public void preorder(Visitor<E> visitor) {
    preorder(root, visitor);
}
// 通过递归遍历所有的元素
public void preorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先处理根节点
    visitor.visit(node.element);
    // 再遍历左子树
    preorder(node.left, visitor);
    // 最后遍历右子树
    preorder(node.right, visitor);
}

// 中序遍历
public void inorder(Visitor<E> visitor) {
    inorder(root, visitor);
}
public void inorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先中序遍历左子树
    inorder(node.left, visitor);
    // 再处理根节点
    visitor.visit(node.element);
    // 最后遍历右子树
    inorder(node.right, visitor);
}

// 后序遍历
public void postorder (Visitor<E> visitor) {
    postorder(root, visitor);
}
public void postorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先遍历左子树
    postorder(node.left, visitor);
    // 再遍历右子树
    postorder(node.right, visitor);
    // 最后处理根节点
    visitor.visit(node.element);
}

// 层序遍历 
public void levelOrder(Visitor<E> visitor) {
    if (root == null) return;
    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);
        }
    }
}
复制代码

3、外界使用

public class Main {
    public static void main(String[] args) {
        int[] data = new int[] {7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> tree = new BinarySearchTree<>();

        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
        // 前序遍历
        tree.preorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 中序遍历
        tree.inorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 后序遍历
        tree.postorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 层序遍历
        tree.levelOrder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
    }
}
复制代码

六、树状打印二叉树

可以使用前序遍历、中序遍历、后序遍历来树状打印二叉树
以中序遍历为例

public String toString() {
    StringBuffer sb = new StringBuffer();
    stringBufferTree(sb, root, "");
    return sb.toString(); 
}

private void stringBufferTree(StringBuffer sb, Node<E> node, String prefix) {
    if (node == null) return;
    stringBufferTree(sb, node.left, prefix + "L-");
    sb.append(prefix).append(node.element).append("\n");
    stringBufferTree(sb, node.right, prefix +  "R-");
}
复制代码

执行代码

public class Main {
    public static void main(String[] args) {
        Integer data[] = new Integer[] {
            7, 4, 9, 2, 1, 3, 5, 9, 8, 11, 10, 12
        };
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
        System.out.println(tree);
    }
}
复制代码

打印结果如下

L-L-L-1
L-L-2
L-L-R-3
L-4
L-R-5
7
R-L-8
R-9
R-R-L-10
R-R-11
R-R-R-12
复制代码

七、计算二叉树的高度

1、递归

二叉树高度 = 根节点高度 = MAX(左子节点高度, 右子节点高度) + 1
以此类推, 可以使用递归计算二叉树的高度

public int height() {
    return height(root);
}

public int height(Node<E> node) {
    if (node == null) return 0;
    // 左子节点或右子节点中高度最高的值 + 1
    return 1 + Math.max(height(node.left), height(node.right));
}
复制代码

2、迭代

可以使用层序循环遍历的方式, 计算树的高度
层序循环遍历, 使用了队列的方式
- 首先将根节点入队
- 根节点出队, 根节点的左右子节点入队, 既第二层的所有节点入队
- 每一个节点出队, 都会将它的左右子节点入队, 以此类推
- 当第二层所有节点出队后, 第三层所有节点都已经入队
- 一开始就用变量elementCount记录每一层的节点个数, 初始值是1, 即根节点入队
- 根节点出队, elementCount--, 第二层节点入队, 此时队列中保存所有第二层节点, 使用elementCount记录第二层节点数量
- 第二层开始出队, 每出队一个节点, elementCount--, 当elementCount == 0时, 说明第二层节点全部出队, 此时第三层节点已经全部入队, 再用elementCount记录第三层所有节点个数
- 以此类推, 当最后队列为空时, 经历过几次elementCount == 0, 就说明二叉树有几层

/**
 * 使用层序遍历的方式, 计算树的高度
 */
public int height() {
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    // 当前队列中节点个数
    int elementCount = 1;
    // 树的高度
    int height = 0;
    while (!queue.isEmpty()) {
        // 取出节点
        Node<E> node = queue.poll();
        // 队列中节点个数-1
        elementCount--;
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        // 当 elementCount = 0, 说明当前层的节点遍历编程
        if (elementCount == 0) {
            // 记录下一层节点个数
            elementCount = queue.size();
            // 高度+1
            height++;
        }
    }
    return height;
}
复制代码

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

image

使用队列进行层次循环, 进行判断
如果树为空, 返回false
如果树不为空，开始层序遍历二叉树(用队列)
- 如果 node.left != null，将 node.left 入队
- 如果 node.left == null && node.right != null，返回 false
- 如果 node.right != null，将 node.right 入队
- 如果 node.right == null
  - 那么后面遍历的节点应该都为叶子节点，才是完全二叉树
  - 否则返回 false
- 遍历结束，返回 true

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();

        // 当leaf == true时, 后面的所有节点都必须是叶子节点, 否则返回false
        if (leaf && (node.left != null || node.right != null)) return false;

        if (node.left != null) {
            // node.left != null && node.right == null
            // node.left != null && node.right != null
            queue.offer(node.left);
        }else if (node.right != null) {
            // node.left == null && node.right != null
            return false;
        }

        if (node.right != null) {
            // node.left != null && node.right != null
            queue.offer(node.right);
        }else {
            // node.left == null && node.right == null
            // node.left != null && node.right == null
            leaf = true;
        }
    }
    return true;
}
复制代码

九、翻转二叉树

示例

输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1
复制代码

二叉树TreeNode如下

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x; 
    }
}
复制代码

1、前序遍历实现翻转二叉树

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;
}
复制代码

2、中序遍历实现翻转二叉树

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;
}
复制代码

3、后序遍历实现翻转二叉树

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;
}
复制代码

4、层序遍历实现翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    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;
}
复制代码

十、前驱节点和后继节点

1、前驱节点

前驱节点: 中序遍历时的前一个节点

image

private Node<E> predecessor(Node<E> node) {
    if (node == null) return node;

    if (node.left != null) {
        Node<E> p = node.left;
        // predecessor = node.left.right.right.right...
        while (p.right != null) {
            p = p.right;
        }
        // p.right == null
        return p;
    }

    // node.left == null
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }

    // node.parent == null, 说明没有前驱节点
    // node == node.parent.right, 说明node的前驱节点是node.parent
    return node.parent;
}
复制代码

2、后继节点

后继节点: 中序遍历时的后一个节点

image

private Node<E> successor(Node<E> node) {
    if (node == null) return node;

    if (node.right != null) {
        Node<E> p = node.right;
        // predecessor = node.right.left.left.left...
        while (p.left != null) {
            p = p.left;
        }
        // p.left == null
        return p;
    }

    // node.right == null
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }

    // node.parent == null, 说明没有后继节点
    // node == node.parent.left, 说明node的后继节点是node.parent
    return node.parent;
}
复制代码

十一、删除节点

1、删除节点-叶子节点

当删除叶子节点时, 这个节点有三种可能
- 父节点的左子节点
- 父节点的右子节点
- 根节点
所以删除叶子节点时, 在判断是那种节点后, 直接删除即可

image

2、删除节点-度为1的节点

当需要删除的节点的度为1时, 将该节点的子节点代替需要删除的节点即可
也可要区分三种可能
- 父节点的左子节点
- 父节点的右子节点
- 根节点

image

3、删除节点-度为2的节点

删除度为2的节点, 分为两步即可
- 先用前驱或后继节点的值覆盖原节点的值
- 然后删除相应的前驱或者后继节点
注意: 一个节点的度为2, 那么它的前驱或者后继节点的度只可能是1和0, 所以也就是删除度为1的节点或者删除叶子节点

image

4、删除节点-代码实现

查找element对应的节点, 代码如下

private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        // 返回值等于0, e1 == e2, 返回正数, e1 > e2, 返回负数, e1 < e2
        int cmp = compare(element, node.element);
        // element == node.element, 返回node
        if (cmp == 0) return node;
        if (cmp > 0) {
            // element > node.element, node = node.right
            node = node.right;
        }else {
            // element > node.element, node = node.left
            node = node.left;
        }
    }
    return null;
}
复制代码

删除element对应的节点

public void remove(E element) {
    // 找到element对应的节点
    Node<E> node = node(element);

    // 数量-1
    size--;

    // 判断node的度, 如果为2, 将node的element赋值为后继节点的element, 并删除后继节点
    // 注意: node的后继节点的度必然是1或者0, 不会是2
    if (node.left != null && node.right != null) {
        // 找到后继节点
        Node<E> s = successor(node);
        // 将node的element赋值为后继节点的element
        node.element = s.element;
        // node指向后继节点, 这样只需要删除node即可
        node = s;
    }
    // 走到这里, node的度只能是1或者是0
    // 找到node的子节点, 左子节点或者右子节点, 或者null
    // 这个子节点会代替node的位置
    Node<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {  // node是度为1的节点
        // 更改replacement的父节点
        replacement.parent = node.parent;

        if (node.parent == null) {  // node是度为1的节点, 并且是根节点
            root = replacement;
        }else if (node == node.parent.left) {   // node是node.parent的左子节点
            node.parent.left = replacement;
        }else { // node == node.parent.right, node是node.parent的右子节点
            node.parent.right = replacement;
        }
    }else if (node.parent == null) {    // node是度为0的节点, 并且是根节点
        root = null;
    }else { // node是度为0的节点, 并且是叶子节点
        if (node == node.parent.left) {
            // node是node.parent的左子节点
            node.parent.left = null;
        }else {
            // node是node.parent的右子节点
            node.parent.right = null;
        }
    }
}
复制代码

十二、清空二叉树

清空二叉树, 只需要将root置为null即可

public void clear() {
    root = null;    // 清空root
}
复制代码

十三、查找元素是否存在

在删除节点中, 已经实现了根据element查找对应节点的方法
只要根据能否找到node, 即可判断元素是否存在

public boolean contains(E element) {
    return node(element) != null;
}
复制代码

数据结构与算法（第一季）：二叉搜索树

一、二叉搜索树

二、二叉搜索树的接口设计

三、二叉搜索树的实现

1、类的设计

2、添加节点

3、节点值的对比

四、二叉树的遍历

1、代码准备

2、前序遍历

3、中序遍历

4、后序遍历

5、层序遍历

五、外界获取遍历结果

1、定义接口, 用于抛出结果

2、将`Visitor`作为遍历方法的参数

3、外界使用

六、树状打印二叉树

七、计算二叉树的高度

1、递归

2、迭代

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

九、翻转二叉树

1、前序遍历实现翻转二叉树

2、中序遍历实现翻转二叉树

3、后序遍历实现翻转二叉树

4、层序遍历实现翻转二叉树

十、前驱节点和后继节点

1、前驱节点

2、后继节点

十一、删除节点

1、删除节点-叶子节点

2、删除节点-度为1的节点

3、删除节点-度为2的节点

4、删除节点-代码实现

十二、清空二叉树

十三、查找元素是否存在

猜你喜欢

热点阅读

数据结构与算法（第一季）：二叉搜索树

一、二叉搜索树

二、二叉搜索树的接口设计

三、二叉搜索树的实现

1、类的设计

2、添加节点

3、节点值的对比

四、二叉树的遍历

1、代码准备

2、前序遍历

3、中序遍历

4、后序遍历

5、层序遍历

五、外界获取遍历结果

1、定义接口, 用于抛出结果

2、将Visitor作为遍历方法的参数

3、外界使用

六、树状打印二叉树

七、计算二叉树的高度

1、递归

2、迭代

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

九、翻转二叉树

1、前序遍历实现翻转二叉树

2、中序遍历实现翻转二叉树

3、后序遍历实现翻转二叉树

4、层序遍历实现翻转二叉树

十、前驱节点和后继节点

1、前驱节点

2、后继节点

十一、删除节点

1、删除节点-叶子节点

2、删除节点-度为1的节点

3、删除节点-度为2的节点

4、删除节点-代码实现

十二、清空二叉树

十三、查找元素是否存在

猜你喜欢

热点阅读

2、将`Visitor`作为遍历方法的参数