二叉树的基本遍历

很多情况下,我们可能需要像遍历数组一样遍历树,从而拿出树中存储的每一个元素,由于树状结构和线性结构不一样,它没有办法从头开始依次向后遍历,所以存在如何遍历,也就是按照什么样的搜索路径进行遍历的问题

我们把树简单的画作上图的样子,由一个根节点,一个左子树,一个右子树组成,那么按照根节点什么时候被访问,我们可以把二叉树的遍历分类为一下三种方式

  1. 前序遍历:先访问根节点,然后再访问左子树,最后访问右子树
  2. 中序遍历:先访问左子树,然后再访问根节点,最后访问右子树
  3. 后序遍历:先访问左子树,然后再访问右子树,最后访问根节点

前序遍历

我们需要在创建树的代码上,添加前序遍历的API

public Queue<key> preErgodic():使用前序遍历,获取整个树中的所有键

private void preErgodic(Node x,Queue<Key> keys):使用前序遍历,把指定树x中的所有键放入keys队列中

实现过程中,我们通过前序遍历,把每个节点的键取出来,放入到队列中返回即可

实现步骤
  1. 把当前节点的key放入到队列中
  2. 找到当前节点的左子树,如果不为空,递归遍历左子树
  3. 找到当前节点的右子树,如果不为空,递归遍历右子树
代码实现
/**
   * 前序遍历*/
  /**
   * 获取整个树中所有的键
   */
  public Queue<Key> preErgodic() {
    Queue<Key> keys = new Queue<Key>();
    preErgodic(root, keys);
    return keys;
  }

  /**
   * 获取指定树x中的所有键,放到keys队列中
   */
  private void preErgodic(Node x, Queue<Key> keys) {
    if (x == null) {
      return;
    }
    //把x节点的key放入到keys队列中
    keys.enqueue(x.key);
    //递归遍历x节点的左子树
    if (x.left != null) {
      preErgodic(x.left, keys);
    }
    //递归遍历x节点的右子树
    if (x.right != null) {
      preErgodic(x.right, keys);
    }
  }

中序遍历

我们需要在创建树的代码上,添加中序遍历的API

public Queue<Key> midErgodic():使用中序遍历,获取整个树中的所有键

private void midErgodic(Node x,Queue<Key> keys):使用中序遍历,把指定树x中的所有键放入到keys队列中

实现步骤
  1. 找到当前节点的左子树,如果不为空,递归遍历左子树
  2. 把当前节点的key放入到队列中
  3. 找到当前节点的右子树,如果不为空,递归遍历右子树
代码实现
/**
   * 中序遍历*/
  /**
   * 获取整个树中的所有键
   */
  public Queue<Key> midErgodic() {
    Queue<Key> keys = new Queue<>();
    midErgodic(root, keys);
    return keys;
  }

  /**
   * 获取指定树x中的所有键,放到keys队列中
   */
  private void midErgodic(Node x, Queue<Key> keys) {
    if (x == null) {
      return;
    }
    //递归遍历x节点的左子树
    if (x.left != null) {
      midErgodic(x.left, keys);
    }
    //把x节点的key放入到keys队列中
    keys.enqueue(x.key);
    //递归遍历x节点的右子树
    if (x.right != null) {
      midErgodic(x.right, keys);
    }
  }

后序遍历

我们需要在创建树的代码上,添加后序遍历的API

public Queue<Key> afterErgodic():使用后序遍历,获取整个树中的所有键

private void afterErgodic(Node x,Queue<Key> keys):使用后序遍历,把指定树x中的所有键放入到keys队列中

实现步骤
  1. 找到当前节点的左子树,如果不为空,递归遍历左子树
  2. 找到当前节点的右子树,如果不为空,递归遍历右子树
  3. 把当前节点的key放入到队列中
代码实现
/**
   * 后序遍历*/
  /**
   * 获取整个树中的所有键
   */
  public Queue<Key> afterErgodic() {
    Queue<Key> keys = new Queue<>();
    afterErgodic(root, keys);
    return keys;
  }

  /**
   * 获取指定树x中的所有键,放到keys队列中
   */
  private void afterErgodic(Node x, Queue<Key> keys) {
    if (x == null) {

      return;
    }
    //递归遍历x节点的左子树
    if (x.left != null) {
      afterErgodic(x.left, keys);
    }
    //递归遍历x节点的右子树
    if (x.right != null) {
      afterErgodic(x.right, keys);
    }
    //把x节点的key放入到keys队列中
    keys.enqueue(x.key);
  }

二叉树的层序遍历

所谓的层序遍历,就是从根节点(第一层)开始,依次向下,获取每一层所有节点的值

那么层序遍历的结果就是:$EBGADFHC$

我们需要在创建树的代码上,添加层序遍历的API

public Queue<Key> layerErgodic():使用层序遍历,获取整个树中的所有键

实现步骤
  1. 创建队列,存储每一层的节点
  2. 使用循环从队列中弹出一个节点

    • 获取当前节点的key
    • 如果当前节点的左子节点不为空,则把左子节点放入到队列中
    • 如果当前节点的右子节点不为空,则把右子节点放入到队列中
代码实现
/**
   * 使用层序遍历,获取整个树中的所有键
   */
  public Queue<Key> layerErgodic() {
    //定义两个队列,分别存储树中的键和树中的节点
    Queue<Key> keys = new Queue<>();
    Queue<Node> nodes = new Queue<>();
    //默认往队列中放入根节点,从根节点开始找
    nodes.enqueue(root);
    //开始循环,当nodes这个队列清空时,就退出循环
    while (!nodes.isEmpty()) {
      //从nodes队列中弹出一个节点,获取当前节点的key,把key放入到keys中
      Node n = nodes.dequeue();
      keys.enqueue(n.key);
      //判断当前节点的左节点是否为空,如果不为空,把当前节点的左节点放入到nodes队列中
      if (n.left != null) {
        nodes.enqueue(n.left);
      }
      //判断当前节点的右节点是否为空,如果不为空,把当前节点的右节点放入到nodes队列中
      if (n.right != null) {
        nodes.enqueue(n.right);
      }
    }
    return keys;
  }

遍历测试代码

public static void main(String[] args) {
    //创建树对象
    BinaryTree<String, String> stringStringBinaryTree = new BinaryTree<>();
    //往树中添加数据,进行前序遍历测试
    stringStringBinaryTree.put("E", "5");
    stringStringBinaryTree.put("B", "2");
    stringStringBinaryTree.put("G", "7");
    stringStringBinaryTree.put("A", "1");
    stringStringBinaryTree.put("D", "4");
    stringStringBinaryTree.put("F", "6");
    stringStringBinaryTree.put("H", "8");
    stringStringBinaryTree.put("C", "3");
    //前序遍历
    //Queue<String> keys = stringStringBinaryTree.preErgodic();
    //中序遍历
    //Queue<String> keys = stringStringBinaryTree.midErgodic();
    //后序遍历
    //Queue<String> keys = stringStringBinaryTree.afterErgodic();
    //层序遍历
    Queue<String> keys = stringStringBinaryTree.layerErgodic();
    for (String key : keys) {
      String value = stringStringBinaryTree.get(key);
      System.out.println(key + "=" + value);
    }
  }

二叉树的最大深度问题

需求

给定一棵树,请计算树的最大深度(树的根节点到最远叶子节点的最长路径上的节点数)

上面这棵树的最大深度为4

实现

我们需要在创建树的代码上,添加求最大深度的API

public int maxDepth():计算整个树的最大深度

private int maxDepth(Node x):计算指定树x的最大深度

实现步骤
  1. 如果根节点为空,则最大深度为$0$
  2. 计算左子树的最大深度
  3. 计算右子树的最大深度
  4. 当前树的最大深度$=$左子树的最大深度和右子树的最大深度中的较大者$+1$
代码实现
/**
   * 二叉树的最大深度问题*/
  /**
   * 获取整个树的最大深度
   */
  public int maxDepth() {
    return maxDepth(root);
  }

  /**
   * 获取指定树x的最大深度
   */
  private int maxDepth(Node x) {
    //如果节点为null,则最大深度为0
    if (x == null) {
      return 0;
    }
    //定义两个变量,x左子树的最大深度,x右子树的最大深度
    int maxL = 0, maxR = 0;
    //计算x节点左子树的最大深度
    if (x.left != null) {
      maxL = maxDepth(x.left);
    }
    //计算x节点右子树的最大深度
    if (x.right != null) {
      maxR = maxDepth(x.right);
    }
    //将两个最大深度进行比较,取较大值+1并进行返回
    return maxL > maxR ? maxL + 1 : maxR + 1;
  }

测试代码

public static void main(String[] args) {
    //创建树对象
    BinaryTree<String, String> stringStringBinaryTree = new BinaryTree<>();
    //往树中添加数据,进行前序遍历测试
    stringStringBinaryTree.put("E", "5");
    stringStringBinaryTree.put("B", "2");
    stringStringBinaryTree.put("G", "7");
    stringStringBinaryTree.put("A", "1");
    stringStringBinaryTree.put("D", "4");
    stringStringBinaryTree.put("F", "6");
    stringStringBinaryTree.put("H", "8");
    stringStringBinaryTree.put("C", "3");
    //测试求最大深度方法
    int maxDepth = stringStringBinaryTree.maxDepth();
    System.out.println("此树的最大深度为:" + maxDepth);
  }

折纸问题

需求

请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开,此时折痕是凹下去的,即折痕凸起的方向指向纸条的背面,如果从纸条的下边向上连续对折2次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕,下折痕和上折痕

给定一个输入参数$N$,代表纸条都从下向上连续对折$N$次,请从上到下打印所有折痕的方向

例如:$N=1$时,打印:$down$;$N=2$时,打印:$down,down,up$

分析

我们把对折后的纸翻过来,让粉色那面朝下,这时把第一次对折产生的折痕看做是根节点,那么第二次对折产生的下折痕就是该节点的左子节点,而第二次对折产生的上折痕就是该节点的右子节点,这样我们就可以使用树型数据结构来描述对折后产生的折痕

这棵树有这样的特点:

  1. 根节点为下折痕
  2. 这是一棵满二叉树
  3. 对折的次数$=$这棵树的深度
  4. 每一个节点的左子节点为下折痕
  5. 每一个节点的右子节点为上折痕
构建深度为N的折痕树
  1. 第一次对折,只有一条折痕,创建根节点
  2. 如果不是第一次对折,则使用队列保存根节点
  3. 层序遍历队列

    • 从队列中拿出一个节点
    • 如果这个节点的左子节点不为空,则把这个左子节点添加到队列中
    • 如果这个节点的右子节点不为空,则把这个右子节点添加到队列中
    • 判断当前节点的左子节点和右子节点都不为空,如果是,则需要为当前节点创建一个值为$down$的左子节点,一个值为$up$的右子节点

##### 代码实现

public static void main(String[] args) {
    //模拟折纸过程,生成以第一个折痕为根节点的树
    Node<String> threeFold = createTree(3);
    //遍历树,打印出每一个折痕节点
    printTree(threeFold);
  }

  /**
   * 通过模拟对折N次,产生一个深度为N的树
   */
  private static Node<String> createTree(int N) {
    //因为最后要返回一个Node类型的节点,所以我们定义一个String类型的根节点
    Node<String> root = null;
    for (int i = 0; i < N; i++) {
      //情况1:当前是第一次对折,创建根节点
      if (i == 0) {
        root = new Node<String>("down", null, null);
      } else {
        //情况2:当不是第一次对折时
        //定义一个辅助的队列,通过层序遍历的思想,找到叶子节点,为叶子节点添加子节点,因为只会在叶子节点添加,这是因为不会在上面层数添加
        Queue<Node> nodes = new Queue<>();
        nodes.enqueue(root);
        //循环遍历队列
        while (!nodes.isEmpty()) {
          //从队列中弹出一个节点
          Node<String> deNode = nodes.dequeue();
          //如果此节点有左子节点,则将左子节点放入到队列中
          if (deNode.left != null) {
            nodes.enqueue(deNode.left);
          }
          //如果此节点有右子节点,则将右子节点放入到队列中
          if (deNode.right != null) {
            nodes.enqueue(deNode.right);
          }
          //如果此节点既没有左子节点,也无右子节点,则证明已经找到了最下面一层的叶子节点,为其添加左子节点和右子节点即可
          if (deNode.left == null && deNode.right == null) {
            //左子节点为下折痕down
            deNode.left = new Node<String>("down", null, null);
            //右子节点为上折痕up
            deNode.right = new Node<String>("up", null, null);
          }
        }
      }
    }
    return root;
  }

  /**
   * 打印树中的每一个节点到控制台
   */
  public static void printTree(Node<String> root) {
    //使用中序遍历进行遍历
    if (root == null) {
      return;
    }
    //打印左子树的每一个节点
    if (root.left != null) {
      printTree(root.left);
    }
    //打印当前节点;
    System.out.print(root.item + ",");
    //打印右子树的每一个节点
    if (root.right != null) {
      printTree(root.right);
    }
  }

  /**
   * 创建树的节点类
   */
  private static class Node<T> {

    //存储元素
    public T item;
    //左子节点
    public Node left;
    //右子节点
    public Node right;

    public Node(T item, Node left, Node right) {
      this.item = item;
      this.left = left;
      this.right = right;
    }
  }
Last modification:June 16th, 2021 at 12:08 am