数据结构之二叉树(一)

本文是二叉树系列的第一篇文章,主要介绍了树的基本概念以及遍历,配有图片、动图和讲解,清晰易懂。

什么是树

直接通过几个示例来形象的说明,官方的定义我就不放了。下图中每个元素叫作“节点”,用来连线相邻节点之间的关系,叫作“父子关系”。

树的相关概念

有三个非常重要但也容易混淆的概念:高度(Height)、深度(Depth)、层(Level)。

概念看着比较晕,还是通过图来说明。

可以类比生活中的“高度”和“深度”来理解和记忆。

在我们的生活中,“高度”这个概念,其实就是从下往上度量,比如我们要度量第10层楼的高度、第13层楼的高度,起点都是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是0。

“深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是0。

“层数”跟深度的计算类似,不过,计数起点是1,也就是说根节点的位于第1层。

二叉树

二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只
有左子节点,有的节点只有右子节点。下面三棵树,都是二叉树。

其中,编号2的二叉树中,叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点。这种二叉树就叫作满二叉树。

编号3的二叉树中,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大。这种二叉树叫作完全二叉树。

相较于满二叉树,完全二叉树的特征就不是那么清晰了,通过下图,再来加深一下理解。

为什么完全二叉树的特征不那么明显,还要定义呢?为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树?如果靠右排列就不能叫完全二叉树了吗?这个定义的由来
或者说目的在哪里?

要理解完全二叉树定义的由来,我们需要先了解,如何表示(或者存储)一棵二叉树?

二叉树的存储

想要存储一棵二叉树,有两种方法,一种是基于指针或者引用的二叉链式存储法,一种是基于数组的顺序存储法。

链式存储法

这是比较简单和直观的存储方式,在算法题中我们会经常看到。如下图所示,每个节点有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

那对应的代码,一般是这样的。

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

顺序存储法

如下图所示,我们把根节点存储在下标i = 1的位置,那左子节点存储在下标2 * i = 2的位置,右子节点存储在2 * i + 1 = 3的位置。以此类推,B节点的左子节点存储在2 * i = 2 * 2 = 4的位置,右子节点存储在2 * i + 1 = 2 * 2 + 1 = 5的位置。

总结一下,如果节点X存储在数组中下标为i的位置,下标为2 * i 的位置存储的就是左子节点,下标为2 * i + 1的位置存储的就是右子节点。反过来,下标为i/2的位置存储就是它的父节点。通过这种方式,我们只要知道根节点存储的位置(一般情况下,为了方便计算子节点,根节点会存储在下标为1的位置),这样就可以通过下标计算,把整棵树都串起来。

上图举的例子是一棵完全二叉树,所以仅仅“浪费”了一个下标为0的存储位置。如果是非完全二叉树,其实会浪费比较多的数组存储空间。如下图所示。

所以,如果某棵二叉树是一棵完全二叉树,那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样,要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因,也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历

到这,重点来了,在算法题中经常会遇到。

如何将所有节点都遍历打印出来呢?经典的方法有三种,前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右子树节点遍历打印的先后顺序。(其实,我更喜欢记成:先根遍历、中根遍历、后根遍历,这样打印的顺序,通过名字就知道了)

  • 前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
  • 中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。
  • 后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。

根据定义以及我们的理解不难得出,二叉树的遍历其实就是一个递归的过程。下面就直接上代码,这部分比较简单,其实就是把顺序更换下。

// 先序遍历
public static void preOrder(TreeNode root){
    if (root==null)return;
    System.out.print(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

// 中序遍历
public static void inOrder(TreeNode root){
    if (root==null)return;
    inOrder(root.left);
    System.out.print(root.val);
    inOrder(root.right);
}

// 后序遍历
public static void postOrder(TreeNode root){
    if (root==null)return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val);
}

掌握了递归版的遍历其实往往还不够,像很多大厂都会有限制,不允许用递归的方式解题,下面,再详细分析和讲解非递归的三种遍历方式的代码。

前序遍历(非递归)

/**
 * 前序遍历(非递归)
 * @param root
 */
public static void preOrderNonRe(TreeNode root){
    if (root==null)return;
    // 因为遍历完中间节点之后,需要找到其左右节点,所以用一个栈进行暂存
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode temp = stack.pop();
        if (temp!=null){
            System.out.print(temp.val);
            // 因为栈是先进后出,所以为了保证是前序遍历的顺序,先放入右节点
            if (temp.right!=null)stack.push(temp.right);
            if (temp.left!=null)stack.push(temp.left);
        }
    }
}

步骤如下:

  1. 首先申请一个新的栈,记为stack;
  2. 将根节点root压入stack中;
  3. 每次从stack中弹出栈顶节点,然后进行打印,如果其右孩子不为空,则将右孩子压入栈中;如果其左孩子不为空,将其压入stack中;
  4. 重复步骤3,直到stack为空。

看下面这个动图,应该更好理解。

中序遍历(非递归)

/**
 * 中序遍历(非递归)
 * @param root
 */
public static void inOrderNonRe(TreeNode root){
    if (root==null)return;
    Stack<TreeNode> stack = new Stack<>();
    // 当前节点
    TreeNode cur = root;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.print(cur.val);
        cur = cur.right;
    }
}

步骤如下:

  1. 申请一个新栈,记为stack,申请一个变量cur,初始时令cur为根节点;
  2. 先把cur节点压入栈中,对以cur节点为根的整棵子树来说,依次把整棵树的左子树压入栈中,即令cur=cur.left;
  3. 不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点记为node,打印node的值,并让cur = node.right,然后继续重复步骤2;
  4. 当stack为空并且cur为空时结束。

看下面这个动图,应该更好理解。

后续遍历(非递归)

/**
 * 后序遍历(非递归)
 * @param root
 */
public static void postOrderNonRe(TreeNode root){
    if (root==null)return;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()){
        TreeNode temp = stack1.pop();
        stack2.push(temp);
        if (temp.left!=null)stack1.push(temp.left);
        if (temp.right!=null)stack1.push(temp.right);
    }
    while (!stack2.isEmpty()){
        System.out.print(stack2.pop().val);
    }
}

步骤如下:

  1. 申请两个栈stack1,stack2,然后将根结点压入stack1中;
  2. 从stack1中弹出的节点记为cur,然后先把cur的左孩子压入stack1中,再把cur的右孩子压入stack1中;
  3. 在整个过程中,每一个从stack1中弹出的节点都放在第二个栈stack2中;
  4. 不断重复步骤2和步骤3,直到stack1为空,过程停止;
  5. 从stack2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序。

看下面这个动图,应该更好理解。

如果还是想只用一个栈,其实也是很好实现的。

/**
 * 后序遍历-第二种方法(非递归)
 * @param root
 */
public static void postOrderNonRe2(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    TreeNode lastVisit = root;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        // 查看栈顶元素
        cur = stack.peek();
        // 如果其右子树为空,或者右子树已经访问
        // 则可以直接输出当前节点的值
        if (cur.right==null||cur.right==lastVisit){
            System.out.print(cur.val);
            stack.pop();
            lastVisit = cur;
            cur = null;
        }else {
            // 继续遍历右子树
            cur = cur.right;
        }
    }
}

后序遍历在决定是否可以输出当前节点的值的时候,需要考虑其左右子树是否都已经遍历完成。步骤如下:

  1. 申请一个新栈,记为stack,申请一个变量cur,初始时令cur为根节点;
  2. 申请一个变量lastVisit,用于记录最近一次打印的节点;
  3. 先把cur节点压入栈中,对以cur节点为根的整棵子树来说,依次把整棵树的左子树压入栈中,即令cur=cur.left;
  4. 不断重复步骤3,直到发现cur为空,此时从stack中查看栈顶元素记为cur ;
  5. 若cur.right为空或者cur.right等于lastVisit,表示该节点的左右子树都已经遍历完成,则可以输出当前节点。并把lastVisit节点设置成当前cur节点,将当前cur节点设置为空,下一轮就可以访问栈顶元素;
  6. 否则,需要接着考虑右子树,cur = cur.right,重复步骤3。

除了常见的三种遍历之外,还有一种,也用的比较多:层次遍历。也就是说,按照树的层次,从上到下,从左到右依次遍历。

/**
 * 层次遍历
 * @param root
 */
public static void level(TreeNode root){
    if (root==null)return;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        TreeNode t = queue.remove();
        System.out.print(t.val);
        if(t.left!=null) {
            queue.add(t.left);
        }
        if(t.right!=null) {
            queue.add(t.right);
        }
    }
}

步骤如下:

  1. 首先申请一个新的队列,记为queue;
  2. 将根节点root压入queue中;
  3. 每次从queue中出队,记为node,然后打印node值,如果node左孩子不为空,则将左孩子入队;如果node的右孩子不为空,则将右孩子入队;
  4. 重复步骤3,直到queue为空。

上面这种层次遍历的方法,没法区分哪些节点是位于同一层的,力扣上有一题,需要返回的类型是 List<List<Integer>> ,也就是说,需要按照每一层,进行“打印”。对于这种情况,我们在上面的代码中,稍加改造就行了。

/**
 * 层次遍历
 * @param root
 */
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();
    if (root==null){
        return list;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        //获取当前队列的长度,这个长度相当于,当前这一层的节点个数
        int size = queue.size();
        List<Integer> temp = new ArrayList<>();
        //将队列中的元素都拿出来(也就是获取这一层的节点)
        //如果节点的左/右子树不为空,也放入队列中
        for(int i=0;i<size;++i) {
            TreeNode t = queue.remove();
            temp.add(t.val);
            if(t.left!=null) {
                queue.add(t.left);
            }
            if(t.right!=null) {
                queue.add(t.right);
            }
        }
        list.add(temp);
    }
    return list;
}

参考

极客时间-数据结构与算法之美

玩透二叉树(Binary-Tree)及前序(先序)、中序、后序【递归和非递归】遍历

【图解数据结构】 二叉树遍历

人已赞赏
Java基础编程语言

【JVM系列】JVM常见面试题

2020-6-8 9:30:18

Java基础编程语言

优化代码中的if-else

2020-7-12 18:55:40

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索