二叉树知识点

1、树形结构

1.1概念

二叉树属于树形结构，所以先了解树形结构之后，再学习二叉树。

树形结构是一种非线性的数据结，是由n个有限节点组成的一个具有层次关系的集合，其形状就像一棵到这的树，跟朝上，叶子朝下。

特点：

1.层次分明：树形结构具有明显的层次关系，有一个根节点作为起始点，从根节点开始，向下一层一层分支扩展。

2.根节点唯一性：树形结构有且仅有一个根节点。根节点是整个树形结构的起始点和核心，所有其他节点都直接或间接与根节点相连。

3.除根结点外，其余节点被分为M个互不相交的集合，T1、T2、...、Tm，其中每一个集合Ti又是一颗与树类似的子树。每一颗子树的根节点有且只有一个前驱，可以有0个或多个后继。

4.树是递归定义的。

注意：树形结构中，字树之间。不能有交集，否则就不是树形结构。

1.2概念

1. 节点的度：节点拥有的子树的数目。
2.  树的度：树中所有节点度的最大值。
3.  叶子节点（终端节点） ：度为 0 的节点，即没有子节点的节点 。
4. 孩子节点 ：一个节点子树的根节点称为该节点的孩子节点。
5. 分支节点 ：度大于 0 的节点 。
6. 兄弟节点 ：具有相同父节点的节点彼此互为兄弟节点。
7.  堂兄弟节点 ：父节点在同一层，但父节点不同的节点互为堂兄弟节点。
8.节点的祖先 ：从根节点到该节点所经分支上的所有节点。
9.  子孙 ：以某节点为根的子树中的所有节点都称为该节点的子孙。
10. 森林 ：是 \(m\)（\(m\geq0\)）棵互不相交的树的集合 。 

1.3树的应用

文件管理系统：在文件系统树形结构中，根目录就是根节点，根目录下的子目录是第一层子节点，子目录下再包含的子目录或文件则构成更下一层的节点，这种层次结构使得数据的组织非常清晰。

2.二叉树

2.1概念

二叉树是一种树形结构，它的每个节点最多有两个子节点。也就是说，二叉树中不存在度大于 2 的节点 ，节点的子树有左右之分，次序不能颠倒，即使某节点只有一棵子树 ，也要区分它是左子树还是右子树。

2.2两种特殊的二叉树

1.满二叉树

定义：一棵深度为 k，且含有 2k−1 个节点的二叉树称为满二叉树。 也就是说，满二叉树的每一层上的节点数都达到最大值，即第 i 层上有 2i−1 个节点（1≤i≤k），从根节点开始，每一个分支都延伸到最底层叶子节点，不存在度为 1 的节点，所有叶子节点都在同一层。

特点：叶子节点都在最底层。
节点总数 n=2k−1，其中 k 为二叉树的深度（层数）。
若节点总数为 n，则深度 k=log2​(n+1)。

满二叉树是一种特殊的完全二叉树

2.完全二叉树

定义：深度为 k 的，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应时，称之为完全二叉树。完全二叉树从根节点到倒数第二层是满的，最后一层节点从左到右依次排列，可能不满，但节点都是从左到右依次存在。

特点：

叶子节点只能出现在最下两层。
最下层的叶子节点集中在左部连续位置。
如果节点度为 1，则该节点只有左孩子，不存在只有右孩子的情况。

 3.二叉树的性质

1. 第 i 层最大节点数 若规定根结点的层数为 1，对于非空二叉树，第 i 层（i>0） 上最多有 2i−1 个结点 。
2. 深度为 K 的最大节点数 若规定只有根结点的二叉树深度为 1，深度为 K（K≥0）的二叉树，其最大结点数是 2K−1 。
3. 叶节点与度为 2 的节点关系 对于任意一棵二叉树，若叶结点个数为 n0​，度为 2 的非叶结点个数为 n2​，则 n0​=n2​+1 。
4. 完全二叉树深度 具有 n 个结点的完全二叉树，其深度 k=⌈log2​(n+1)⌉，其中 ⌈x⌉ 表示对 x 向上取整。
5. 完全二叉树节点编号对应关系 对于具有 n 个结点的完全二叉树，按照从上至下、从左至右的顺序对所有节点从 0 开始编号，对于序号为 i 的结点：
   • 若 i>0，其双亲序号为 ⌊2i−1​⌋；若 i=0，i 为根结点编号，无双亲结点。
   • 若 2i+1<n，左孩子序号为 2i+1，否则无左孩子。
   • 若 2i+2<n，右孩子序号为 2i+2，否则无右孩子。

4.二叉树的遍历

• 前序遍历：先访问根节点，再递归访问左子树，最后递归访问右子树。即按照 “根 - 左 - 右” 的顺序遍历。
• 中序遍历：先递归访问左子树，再访问根节点，最后递归访问右子树。即 “左 - 根 - 右” 的顺序。
• 后序遍历：先递归访问左子树，再递归访问右子树，最后访问根节点。即 “左 - 右 - 根” 的顺序。
• 层次遍历：按照二叉树的层次，从上到下、从左到右依次访问节点。通常使用队列来辅助实现，先将根节点入队，然后循环取出队列中的节点，访问该节点，并将其左、右子节点（如果存在）入队。

5.二叉树的存储

二叉树的存储结构分为顺序存储和类似于链表的链式存储。

顺序存储：顺序存储结构是将二叉树的所有节点，按照层次依次存储在一个一维数组中。对于完全二叉树来说，这种存储方式非常直观和高效。假设根节点存储在数组的第一个位置（下标为0 或者 1，取决于具体的实现约定，这里以下标从 0 开始为例），如果一个节点存储在数组下标为 i 的位置，那么它的左子节点存储在下标为 2*i + 1 的位置，右子节点存储在下标为 2*i + 2 的位置。例如，根节点在 array[0]，其左子节点在 array[1]，右子节点在 array[2]。

优点：

       访问节点速度快，通过简单的下标计算就能快速定位到某个节点及其子节点。
       对于完全二叉树，存储密度高，没有空间浪费。
缺点：

      对于非完全二叉树，会造成大量的空间浪费。例如，一个只有根节点和左子树的二叉树，右子        树对应的数组位置都要预留空间，导致存储效率低下。

      插入和删除节点操作比较复杂，可能需要移动大量的元素来维护节点之间的逻辑关系。

适用场景：适用于完全二叉树或近似完全二叉树的情况。

链式存储：链式存储结构是基于链表的思想，每个节点除了存储自身的数据值外，还包含指向左子节点和右子节点的引用（指针）。在Java中，通常通过定义一个类来表示二叉树的节点，类中包含数据域和两个引用域分别指向左子节点和右子节点。示例：

public static class BTNode{int val;BTNode left;BTNode right;public BTNode(int val) {this.val = val;}}

优点：
    对于任意形态的二叉树都能高效存储，不会因为二叉树的形态而造成大量空间浪费。
    插入和删除节点操作相对简单，只需要修改节点的引用关系，不需要移动大量数据。
缺点：
    访问节点需要从根节点开始遍历，时间复杂度相对较高，不像顺序存储结构那样可以通过下标直接访问。
    每个节点都需要额外的空间来存储引用，相比于顺序存储结构，空间开销较大。
适用场景：适用于各种形态的二叉树，尤其是节点插入和删除操作频繁的情况。

6.二叉树的基本操作

获取树中节点的个数 size(Node root);

 获取叶⼦节点的个数 getLeafNodeCount(Node root);

⼦问题思路-求叶⼦结点个数

 获取第K层节点的个数  getKLevelNodeCount(Node root,int k);

获取⼆叉树的⾼度  getHeight(Node root);

检测值为value的元素是否存在 find(Node root, int val);

层序遍历 levelOrder(Node root);

判断⼀棵树是不是完全⼆叉树 isCompleteTree(Node root);

方法实现：

// 获取树中节点的个数public void size(BTNode root){if(root == null){return ;}count++;size(root.left);size(root.right);}public int size2(BTNode root){if(root==null){return 0;}return size2(root.left)+size2(root.right)+1;}// 获取叶⼦节点的个数public static int count2=0;public void getLeafNodeCount(BTNode root) {if (root == null) {return;}if (root.left == null && root.right == null) {count2++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}public int getLeafNodeCount2(BTNode root){if(root==null) {return 0;}if(root.left==null&&root.right==null){return 1;}return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);}// ⼦问题思路-求叶⼦结点个数// 获取第K层节点的个数public int getKLevelNodeCount(BTNode root,int k){if(root==null){return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);}// 获取⼆叉树的⾼度public int getHeight(BTNode root){if(root==null){return 0;}int leftCount=getHeight(root.left)+1;int rightCount=getHeight(root.right)+1;return leftCount>rightCount ? leftCount:rightCount;//return Math.max(leftCount,rightCount);}// 检测值为value的元素是否存在public BTNode find(BTNode root, int val){if(root==null||root.val==val){return root;}BTNode left=find(root.left,val);if(left!=null){return left;}BTNode right=find(root.right,val);if(right!=null){return right;}return null;}