当前位置：首页 > news >正文

二叉树知识点

news 来源：原创 2025/5/19 10:48:07

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.二叉树的性质

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

4.二叉树的遍历

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

5.二叉树的基本操作

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

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

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

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

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

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

层序遍历 void levelOrder(Node root);

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