💕"从前种种譬如昨日死；从后种种譬如今日生"💕
作者：Mylvzi
文章主要内容：数据结构之二叉树及面试题讲解
一.概念
1.树的定义
树是一种非线性的数据结构，是由n个结点组成的一种非线性集合；之所以叫做树，是因为他看起来像一颗倒挂的树，也就是根朝上，叶子朝下，一颗二叉树具有以下特征
- 有一个特殊节点--根节点 一颗二叉树有且仅有一个根节点
- 树是递归定义的
2.树与非树
如何判断一棵树是否是树呢?可以通过以下几个方式
- 除根节点外，其余结点有且仅有一个父节点
- 一棵树如果有n个结点，则一定有n-1条边
- 子树是不相交的
3.树的相关概念
- 度：某个结点的子结点个数就叫做该节点的度 比如B结点的度就是2，因为其有两个子节点
- 树的度：指的是结点度的最大值 如图A结点的度是3，所以树的度就是3
- 叶子节点(终端节点):没有子节点的结点 比如E,F,G
- 祖先节点：所有节点的父节点 就是根节点 本图中A结点时祖先节点
- 父节点：结点的前驱结点就是父节点，也叫做双亲结点 B是E,F的父节点
- 孩子节点：与父结点相对
- 树的高度：树的层次的最大值就是树的高度 如图层次是三，所以树的高度就是3
- 树的以下概念只需了解，在看书时只要知道是什么意思即可：
- 非终端结点或分支结点：度不为0的结点；
- 兄弟结点：具有相同父结点的结点互称为兄弟结点；
- 堂兄弟结点：双亲在同一层的结点互为堂兄弟；
- 森林：由m（m>=0）棵互不相交的树组成的集合称为森林
4.树的表示形式（了解）
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
class Node { int value; // 树中存储的数据 Node firstChild; // 第一个孩子引用 Node nextBrother; // 下一个兄弟引用 }
二. 二叉树（重点）
1.概念
二叉树是树形结构的一种，二叉树就是度<= 2的的树
二叉树是由以下几种情况组成
2.两种特殊的二叉树
- 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵 二叉树的层数为K，且结点总数是 2^k - 1，则它就是满二叉树。
- 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
- 完全二叉树就是从上到下，从左到右依次存放结点的树
3.二叉树的性质(重点 )
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有(2^i - 1) (i>0)个结点
- 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(2^k - 1) (k>=0)推导：等比数列的求和公式推导而成
- 具有n个结点的完全二叉树的深度k 为 Log(n+1)向 上取整
- 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1 也就是叶子节点的个数一定比度为2的结点的个数多一
这个性质经常作为考试题目，会结合结点数目的奇偶性以及完全二叉树来出题
如果结点数是2N，则n1的个数一定是1
如果结点数是2N+1,则n1的个数一定是0
4.二叉树的存储
二叉树的存储结构分为：顺序存储和链式存储
顺序存储的底层其实是"堆"这种数据结构的实现，也就是二叉搜索树
我们以链式的存储结构进行讲解
二叉树的链式存储结构是通过一个一个结点实现的，最常用的表示方法是左右孩子表示法，即每个节点存储左右孩子结点
定义结点内部类
static class TreeNode { public int val; public TreeNode lChild;// 左孩子 public TreeNode rChild;// 右孩子 public TreeNode(char val) { this.val = val; } }
手动插入结点
public TreeNode create() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.lChild = B; A.rChild = C; B.lChild = D; B.rChild = E; C.lChild = F; C.rChild = G; E.rChild = H; return A; }
2.二叉树的遍历
遍历是二叉树的一个很重要的操作，二叉树作为一种存储数据的结构，在我们获取数据的时候需要遍历整棵二叉树，直到拿到我们所需要的数据，不同的遍历方式也会带来不同的效率，二叉树常见的遍历方式有：
- 前序遍历preOrder 根左右
- 中序遍历inOrder 左根右
- 后序遍历postOrder 左右根
- 层序遍历levelOrder 从上至下从左至右依次遍历每一个结点
遍历操作最核心的思路就是"子问题思路"和递归的思想，下面进行遍历的代码实现
把整棵二叉树想象为只有一个根节点和两个孩子节点的树，很多二叉树的问题就容易解决
要谨记，二叉树有两种，空树和非空树，任何情况下都不要忘记空树的情况
1，前序遍历
// 前序 public void preOrder(TreeNode root) { // 空树直接返回 if(root == null) return; System.out.print(root.val+" "); // 打印完根节点再去访问左孩子和右孩子 preOrder(root.lChild); preOrder(root.rChild); }
力扣题目
https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/
代码实现
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); // 空树直接返回 if(root == null) return list; list.add(root.val); // 遍历左子树 List<Integer> leftTree = preorderTraversal(root.left); list.addAll(leftTree); // 遍历右子树 List<Integer> rightTree = preorderTraversal(root.right); list.addAll(rightTree); return list; }
2.中序遍历
// 中序 public void inOrder(TreeNode root) { // 空树 直接返回 if(root == null) return; inOrder(root.lChild); System.out.print(root.val+" "); inOrder(root.rChild); }
https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/
代码实现
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); // 空树 直接返回 if(root == null) return list; // 遍历左子树 List<Integer> leftTree = inorderTraversal(root.left); list.addAll(leftTree); list.add(root.val); // 遍历右子树 List<Integer> rightTree = inorderTraversal(root.right); list.addAll(rightTree); return list; }
数据结构之二叉树及面试题讲解（二）+https://developer.aliyun.com/article/1413554
