【数据结构】二叉爆炸

阅读本书更多章节>>>>

【数据结构】二叉爆炸

按照惯例整点抽象的，贴上这篇博客的名字由来：

言归正传，本篇博客介绍二叉树的构造方式、前中后序遍历、层序遍历以及代码随想录中二叉树章节的相关题目：

代码随想录 (programmercarl.com)

一、啥是二叉树

1.二叉树是什么？

百度百科上的解释是这样的：

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

太长不看，简单来说，二叉树就是这个：

单亲爸爸带俩娃（划掉），一个根节点带着俩孩子。左边的孩子是“左子树”，右边的孩子是“右子树”。

下面是一些二叉树相关的定义，下面关于二叉树的算法题中可能会用到：

①节点：包含一个数据元素及若干指向子树分支的信息。

②节点的度：一个节点拥有子树的数目称为节点的度。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。

⑤树的度：树中所有节点的度的最大值。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。

⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。

⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。

⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

2.二叉树有啥用？

数据存储和检索：二叉搜索树（BST）是一种常见的数据结构，用于存储和检索数据。在BST中，每个节点的左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点，这使得查找、插入和删除操作的平均时间复杂度为O(log n)，其中n是树中节点的数量。数据库索引：许多数据库系统使用二叉树或其变种（如B树、B+树）来加速数据检索。这些树结构允许在大量数据中快速找到所需的记录。文件系统：许多操作系统使用树状结构来组织文件和目录。文件系统中的每个目录都可以视为一个节点，其中包含文件和其他子目录。图形用户界面（GUI）：许多GUI工具包使用树形结构来组织用户界面元素。例如，菜单和文件资源管理器通常使用树形结构来表示层级结构。

3.特殊的二叉树！

满二叉树

所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树。

这张图上的树就是一棵满二叉树。

完全二叉树

在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树。即最后一层所有节点靠左的二叉树。

如图所示：

二、咋遍历二叉树？

1. 深度优先搜索（前，中，后序遍历）

从根节点开始，沿着树的深度尽可能远的搜索树的分支。当达到树的最深处时，再回溯到上一级节点继续搜索，直到遍历完整棵树。

前序遍历（Preorder Traversal）：以根节点、左子树、右子树的顺序遍历二叉树。中序遍历（Inorder Traversal）：以左子树、根节点、右子树的顺序遍历二叉树。后序遍历（Postorder Traversal）：以左子树、右子树、根节点的顺序遍历二叉树。

接下来我们就看看前中后序遍历的代码实现，此处均以leetcode上题目为模板。

前序遍历

递归遍历：

class Solution {    public List<Integer> preorderTraversal(TreeNode root) {        List<Integer> result = new ArrayList<Integer>();        preorder(root, result);        return result;    }    public void preorder(TreeNode root, List<Integer> result) {        if (root == null) {            return;        }        result.add(root.val);        preorder(root.left, result);        preorder(root.right, result);    }}

迭代法遍历：

class Solution {    public List<Integer> preorderTraversal(TreeNode root) {        List<Integer> result = new LinkedList<>();        Stack<TreeNode> st = new Stack<>();        if (root != null) st.push(root);        while (!st.empty()) {            TreeNode node = st.peek();            if (node != null) {                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）                st.push(node);                          // 添加中节点                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。                            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集                st.pop();           // 将空节点弹出                node = st.peek();    // 重新取出栈中元素                st.pop();                result.add(node.val); // 加入到结果集            }        }        return result;    }}

中序遍历

递归遍历：

class Solution {    public List<Integer> inorderTraversal(TreeNode root) {        List<Integer> res = new ArrayList<>();        inorder(root, res);        return res;    }    void inorder(TreeNode root, List<Integer> list) {        if (root == null) {            return;        }        inorder(root.left, list);        list.add(root.val);             // 注意这一句        inorder(root.right, list);    }}

迭代法遍历：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {        List<Integer> result = new LinkedList<>();    Stack<TreeNode> st = new Stack<>();    if (root != null) st.push(root);    while (!st.empty()) {        TreeNode node = st.peek();        if (node != null) {            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）            st.push(node);                          // 添加中节点            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集            st.pop();           // 将空节点弹出            node = st.peek();    // 重新取出栈中元素            st.pop();            result.add(node.val); // 加入到结果集        }    }    return result;}}

后序遍历

递归遍历：

class Solution {    public List<Integer> postorderTraversal(TreeNode root) {        List<Integer> res = new ArrayList<>();        postorder(root, res);        return res;    }    void postorder(TreeNode root, List<Integer> list) {        if (root == null) {            return;        }        postorder(root.left, list);        postorder(root.right, list);        list.add(root.val);             // 注意这一句    }}

迭代法遍历：

class Solution {   public List<Integer> postorderTraversal(TreeNode root) {        List<Integer> result = new LinkedList<>();        Stack<TreeNode> st = new Stack<>();        if (root != null) st.push(root);        while (!st.empty()) {            TreeNode node = st.peek();            if (node != null) {                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中                st.push(node);                          // 添加中节点                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）                                                    } else { // 只有遇到空节点的时候，才将下一个节点放进结果集                st.pop();           // 将空节点弹出                node = st.peek();    // 重新取出栈中元素                st.pop();                result.add(node.val); // 加入到结果集            }        }        return result;   }}

如何从中序和后序倒推出二叉树

先别急着看层序遍历，既然二叉树可以用这几种方式遍历，那么一定可以从这几种方式中倒推出二叉树的构造！

来看看这道题目：

首先复习一下中序遍历与后序遍历的遍历方式：

中序：左中右

后序：左右中

如果光看中序遍历数组，无法找到中间节点，光看后序遍历的数组，无法分割左右孩子，于是将两

种遍历方式结合起来，先从后序中找到中间节点的值，再将中序数组的左右孩子分开。

思路大概是：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中

序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

接下来出场的是递归三部曲：

首先确定递归函数返回值和参数：返回treenode，参数为两个数组及其区间。

而后确定递归终止条件：当后序数组为空时，证明已经没有新的中间节点了，则返回空。

最后确定单层递归逻辑：

在本题的单层递归中，我们需要做的事情稍显复杂：

首先，我们需要从后序数组中找到最后一个值，即当前子树的根节点。而后，在中序数组中找到该节点，并保存其索引mid。以mid分割中序数组，找到左子树和右子树。分割后序数组，找到中序数组中左子树与右子树对应的左子树和右子树区间。将计算好的值传入下层递归中。最后返回根节点。

AC代码如下：

class Solution {    public TreeNode buildTree(int[] inorder, int[] postorder) {        if(postorder.length == 0 || inorder.length == 0)            return null;        return Build(inorder, 0, inorder.length, postorder, 0, postorder.length);    }    public TreeNode Build(int[] inorder, int inStart, int inEnd, int[] postorder, int posStart, int posEnd){        if(posStart == posEnd){            return null;        }        //后序遍历的最后一个值，即为当前子树的根节点        int rootVal = postorder[posEnd - 1];        TreeNode root = new TreeNode(rootVal);        int mid;        //从中序遍历数组中找到root结点        for (mid = inStart; mid < inEnd; mid++){            if(inorder[mid] == rootVal){                break;            }        }        //分割中序数组        int lInStart = inStart;         int lInEnd = mid;        int rInStart = mid + 1;        int rInEnd = inEnd;        //分割后序数组        int lPosStart = posStart;        int lPosEnd = posStart + (mid - inStart);        int rPosStart = lPosEnd;        int rPosEnd = posEnd - 1;                //传入下层递归        root.left = Build(inorder, lInStart, lInEnd,  postorder, lPosStart, lPosEnd);        root.right = Build(inorder, rInStart, rInEnd, postorder, rPosStart, rPosEnd);        return root;    }  }

2. 广度优先搜索（层序遍历）

从根节点开始，沿着树的宽度遍历树的节点。首先访问根节点，然后依次访问与根节点相邻的节点，直到遍历完整层的节点后再继续向下一层移动。

借用队列Queue来实现层序遍历，将每一层的内容放入队列中，在下一次遍历时，对队列中从头到

尾的每个元素进行检查，如果存在左右子节点，则入队，依次进行下去即可完成层序遍历。

例：对于如下二叉树，某一次的出队入队过程如下：

示例代码如下：

class Solution {    public List<List<Integer>> ans = new LinkedList<>();    public List<List<Integer>> levelOrder(TreeNode root) {        if(root == null){            return ans;        }        Queue<TreeNode> que = new LinkedList<>();        que.add(root);        while(!que.isEmpty()){            int len = que.size();            List<Integer> ls = new LinkedList<>();                        while(len > 0){                TreeNode temp = que.poll();                ls.add(temp.val);                if(temp.left != null){                    que.add(temp.left);                }                if(temp.right != null){                    que.add(temp.right);                }                len--;            }            ans.add(ls);        }        return ans;    }}

学完层序遍历可以一口气A完以下10题：

102.二叉树的层序遍历107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度

我们选取一道典型的题目来看看：

这个题和116. 填充每个节点的下一个右侧节点指针两道题，用同一套代码直接解决了…

层序遍历真好用（喜）

用队列来进行层序遍历，再用一个list维护每一层的代码，在遍历完某一层后链接该层的next指针即可。

值得一提的是链接时用的while代码块，单独掏出来看看：

while(ls.size() > 1){    Node pf = ls.removeLast();    Node pb = ls.getLast();    pb.next = pf;}

首先把最后的节点保存，然后在get到倒数第二个节点，因为下一次遍历仍然会用到倒数第二个节

点，故而不能remove掉，再进行连接，结束条件是list中只剩下一个节点。

AC代码如下：

class Solution {    public Node connect(Node root) {        if(root == null){            return root;        }        Queue<Node> que = new LinkedList<>();        List<Node> ls = new LinkedList<>();        que.add(root);        while(!que.isEmpty()){            int len = que.size();            ls.clear();            while(len > 0){                Node tmp = que.poll();                ls.add(tmp);                if(tmp.left != null) que.add(tmp.left);                if(tmp.right != null) que.add(tmp.right);                len--;            }            while(ls.size() > 1){                Node pf = ls.removeLast();                Node pb = ls.getLast();                pb.next = pf;            }        }        return root;    }}

这个代码使用了List进行辅助，导致时间和空间都变得复杂了，唯一的好处是好理解，接下来登场的是优化代码~

public Node connect(Node root) {    if(root == null){        return root;    }    Queue<Node> que = new LinkedList<>();    que.add(root);    while (!que.isEmpty()) {        int len = que.size();        //前一个节点        Node pre = null;        while(len > 0){            //出队            Node node = que.poll();            //如果pre为空就表示node节点是这一行的第一个，            //没有前一个节点指向他，否则就让前一个节点指向他            if (pre != null) {                pre.next = node;            }            //然后再让当前节点成为前一个节点            pre = node;            //左右子节点如果不为空就入队            if (node.left != null) que.add(node.left);            if (node.right != null) que.add(node.right);            len--;        }    }    return root;}

将内层的循环拿出来看：

定义一个pre节点，用于保存每次的节点，依次向后遍历，将每次出队的节点保存为node，若首次

插入，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();//前一个节点Node pre = null;while(len > 0){    //出队    Node node = que.poll();    //如果pre为空就表示node节点是这一行的第一个，    //没有前一个节点指向他，否则就让前一个节点指向他    if (pre != null) {        pre.next = node;    }    //再让当前节点成为前一个节点    pre = node;    if (node.left != null) que.add(node.left);    if (node.right != null) que.add(node.right);    len--;}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

，则将第一个node定义为pre，然后再进行后面的操作。

int len = que.size();//前一个节点Node pre = null;while(len > 0){    //出队    Node node = que.poll();    //如果pre为空就表示node节点是这一行的第一个，    //没有前一个节点指向他，否则就让前一个节点指向他    if (pre != null) {        pre.next = node;    }    //再让当前节点成为前一个节点    pre = node;    if (node.left != null) que.add(node.left);    if (node.right != null) que.add(node.right);    len--;}

三、结语

本篇博客介绍了树的基础知识以及树的各种遍历方式的应用，在接下来的学习中，还可能会接触到较为复杂的树，如二叉搜索树，平衡二叉树等。

本篇博客代码以及部分解析参考：

代码随想录 (programmercarl.com)

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-15/158889.html，文章来源：网络cs，作者：淼淼，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！