- 1Kafka 延迟队列_kafka延时队列实现
- 2windows服务器iis系统部署https
- 3单链表的基本实现(详细图解+解说)_单链表的实现
- 4用五一最简单的板做一个智能循迹小车_制作一个智能小车,前期有哪些检查工作
- 5关于SpringCloud报错Unsatisfied dependency expressed through field ‘propertySourceLocators的解决之一
- 6【面试必看】链表的常见笔试题_找链表节点笔试
- 7强烈推介!!! java工程师（大数据）值得拥有的顶级GitHub项目_和javaguide类似的python网站
- 8JS变量命名规则+赋值_js怎么给变量赋值变量名$
- 9蓝桥杯嵌入式14届4T模拟题1_4t蓝桥杯
- 10List在遍历时修改元素会怎样？——学习笔记_c# list 集合修改 元素值
【Java】二叉树_java二叉树
赞
踩
一、树形结构
树形结构是一种常见的数据结构，它由节点（Node）和节点之间的关系构成。在树中，一个节点可以有零个或多个子节点，但每个节点只有一个父节点，除了根节点外。根节点是树的顶部节点，没有父节点。
树形结构有许多应用，例如：
-
文件系统：文件系统可以用树来表示，每个文件夹是一个节点，文件夹之间的层次关系形成树的结构。
-
组织架构：企业的组织架构可以用树来表示，每个部门是一个节点，部门之间的关系形成树的结构。
-
分类和层级结构：树可以用于表示分类和层级结构，例如产品分类、科学分类等。
树形结构的基本术语如下：
-
节点（Node）：树中的每个元素称为节点，每个节点包含数据和指向其子节点的链接。
-
根节点（Root）：树的顶部节点称为根节点，它没有父节点。
-
子节点（Child）：一个节点的直接下级节点称为子节点。
-
父节点（Parent）：一个节点的直接上级节点称为父节点。
-
叶节点（Leaf）：没有子节点的节点称为叶节点或终端节点。
-
兄弟节点（Sibling）：具有相同父节点的节点称为兄弟节点。
-
深度（Depth）：从根节点到某个节点的路径上经过的边的数量，也可以理解为该节点所在的层级。
-
高度（Height）：从某个节点到其最远叶节点的路径上经过的边的数量，也可以理解为该节点所在子树的最大深度。
树形结构的具体实现方式有多种，例如二叉树、多叉树、平衡树、B树等。每种实现方式都有自己的特点和适用场景。
树形结构提供了一种有效的组织和管理数据的方式，可以进行高效的搜索、插入和删除操作。在算法和数据结构中，树形结构也是一个重要的主题，具有广泛的应用。
二、认识二叉树
2.1 二叉树的概念
二叉树（Binary Tree）是一种常见的树形结构，它由节点（Node）和节点之间的关系构成。每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树中的每个节点可以为空（null）。
2.2 二叉树的性质
二叉树（Binary Tree）具有一些重要的性质，这些性质对于理解和操作二叉树非常有帮助。下面是二叉树的一些常见性质：
-
每个节点最多有两个子节点：每个节点最多有一个左子节点和一个右子节点。这意味着一个节点的度数（Degree）最大为2。
-
左子树和右子树的顺序是固定的：在二叉树中，左子树位于父节点的左侧，右子树位于父节点的右侧。改变左右子树的顺序将产生不同的二叉树。
-
节点的度数：节点的度数是指该节点的子节点数量。二叉树中，节点的度数最大为2，即一个节点最多有两个子节点。
-
叶节点（叶子节点）：叶节点是没有子节点的节点，也可以称为终端节点。
-
节点的层级（Level）：根节点的层级为1，其余节点的层级为其父节点的层级加1。
-
树的高度（Height）：树的高度是从根节点到最远叶节点的最长路径上的边数。叶节点的高度为0，空树的高度为-1。
-
完全二叉树（Complete Binary Tree）性质：在完全二叉树中，除了最后一层外，其他层的节点都是满的，且最后一层的节点都尽量靠左排列。
-
满二叉树（Full Binary Tree）性质：在满二叉树中，除了叶节点外，每个节点都有两个子节点。
-
二叉搜索树（Binary Search Tree）性质：二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树中的所有节点都小于该节点的值，而其右子树中的所有节点都大于该节点的值。
-
若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1) (i > 0)个结点。
-
若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k - 1 (k>=0)。
-
对任何一棵二叉树, 如果其叶结点个数为 n0，度为2的非叶结点个数为 n2，则有 n0 ＝ n2 ＋ 1。
-
具有n个结点的完全二叉树的深度k为log2 (n + 1) 上取整。
-
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为 i 的结点有：
- 若 i > 0，双亲序号：(i - 1) / 2；i = 0，i 为根结点编号，无双亲结点。
- 若 2i + 1< n，左孩子序号：2i + 1，否则无左孩子。
- 若 2i + 2 < n，右孩子序号：2i + 2，否则无右孩子。
2.3 二叉树的存储
二叉树可以使用不同的数据结构进行存储。以下是几种常见的二叉树存储方式：
-
链式存储（Linked Storage）：使用节点对象和指针来表示二叉树的结构。每个节点对象包含存储的数据以及指向左子节点和右子节点的指针。这种存储方式可以直观地表示树的结构，适用于任意形状的二叉树。Java中常用的LinkedList数据结构可以用来实现二叉树的链式存储。
-
数组存储（Array Storage）：使用数组来表示二叉树的结构。可以使用一维数组或二维数组来存储节点的数据。通过数组的索引关系来表示节点之间的父子关系。这种存储方式可以节省存储空间，但适用于完全二叉树或满二叉树等具有规律结构的二叉树。
-
堆存储（Heap Storage）：使用堆（Heap）数据结构来存储二叉树。堆是一种特殊的完全二叉树，通常使用数组来实现。在堆存储中，节点的位置是通过数组的索引来确定的。堆存储常用于实现优先队列等应用。
三、二叉树的实现
3.1 二叉树的创建
二叉树节点定义：
class TreeNode {
public char val;
public TreeNode left; // 左孩子引用
public TreeNode right; // 右孩子引用
public TreeNode(char val) {
this.val = val;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
这是一个常见的二叉树节点类定义。每个节点包含一个字符值（val）和左右孩子的引用（left 和 right）。
手动创建二叉树需要逐个节点地创建，并为每个节点设置左子节点和右子节点的引用。这种方法适用于树的结构较小或特定形状的情况。例如，创建以下二叉树：
A
/ \
B C
/ \ \
D E F
- 1
- 2
- 3
- 4
- 5
TreeNode root = new TreeNode('A');
root.left = new TreeNode('B');
root.right = new TreeNode('C');
root.left.left = new TreeNode('D');
root.left.right = new TreeNode('E');
root.right.right = new TreeNode('F');
- 1
- 2
- 3
- 4
- 5
- 6
3.2 二叉树的遍历方法
二叉树的遍历是指按照一定的顺序访问树中的所有节点。常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。
假设有一个二叉树如下所示：
A
/ \
B C
/ \ \
D E F
- 1
- 2
- 3
- 4
- 5
-
前序遍历（Preorder Traversal）：先访问根节点，然后按照左子树、右子树的顺序递归遍历子树。
遍历结果：A -> B -> D -> E -> C -> F
-
中序遍历（Inorder Traversal）：先按照左子树、根节点、右子树的顺序递归遍历子树。
遍历结果：D -> B -> E -> A -> C -> F
-
后序遍历（Postorder Traversal）：先按照左子树、右子树的顺序递归遍历子树，最后访问根节点。
遍历结果：D -> E -> B -> F -> C -> A
-
层序遍历（Level Order Traversal）：从上到下逐层遍历二叉树的节点。
遍历结果：A -> B -> C -> D -> E -> F
实现这些遍历方式的代码可以使用递归或迭代的方式来实现，以下是递归方式的示例代码：
class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char val) { this.val = val; } } public class BinaryTreeTraversal { public static void preorderTraversal(TreeNode root) { if (root == null) { return; } System.out.print(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); } public static void inorderTraversal(TreeNode root) { if (root == null) { return; } inorderTraversal(root.left); System.out.print(root.val + " "); inorderTraversal(root.right); } public static void postorderTraversal(TreeNode root) { if (root == null) { return; } postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.val + " "); } public static void levelOrderTraversal(TreeNode root) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.val + " "); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } public static void main(String[] args) { TreeNode root = new TreeNode('A'); root.left = new TreeNode('B'); root.right = new TreeNode('C'); root.left.left = new TreeNode('D'); root.left.right = new TreeNode('E'); root.right.right = new TreeNode('F'); System.out.print("Preorder Traversal: "); preorderTraversal(root); inorderTraversal(root); System.out.println(); System.out.print("Postorder Traversal: "); postorderTraversal(root); System.out.println(); System.out.print("Level Order Traversal: "); levelOrderTraversal(root); System.out.println(); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
这样就可以通过调用相应的遍历函数来遍历二叉树并输出结果。请注意，在实际代码中，可以根据具体的需求，将节点的值打印、保存到集合中或执行其他操作。
3.3 二叉树的常见操作
// 获取树中节点的个数 public static int nodeSize = 0; public int size(TreeNode root) { if (root == null) { return 0; } nodeSize++; size(root.left); size(root.right); return nodeSize; } public int size2(TreeNode root) { if (root == null) return 0; return size2(root.left) + size2((root.right)) + 1; } // 获取叶子节点的个数 public int getLeafNodeCount(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; return getLeafNodeCount(root.left) + getLeafNodeCount(root.right); } // 获取第K层节点的个数 // 相对于根节点，就是获取左数的第K-1层 + 右数的第K-1层 int getKLevelNodeCount(TreeNode root, int K) { if (root == null || K <= 0) return 0; if (K == 1) { return 1; } return getKLevelNodeCount(root.left, K - 1) + getKLevelNodeCount(root.right, K - 1); } // 获取二叉树的高度 int getHeight(TreeNode root) { if (root == null) { return 0; } return Math.max(getHeight(root.left), getHeight(root.right)) + 1; } // 检测值为value的元素是否存在 public TreeNode find(TreeNode root, int val) { if (root == null) return null; if (root.val == val) { return root; } TreeNode ret1 = find(root.left, val); if (ret1 != null) { return ret1; } TreeNode ret2 = find(root.right, val); if (ret2 != null) { return ret2; } return null; } // 判断一棵树是不是完全二叉树 public boolean isCompleteTree(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if (root == null) { return true; } queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node != null) { queue.offer(node.left); queue.offer(node.right); } else { break; } } // 判断剩下的值是否有不为空的 while (!queue.isEmpty()){ if(queue.poll() != null){ return false; } } return true; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
四、二叉树的应用场景
4.1 检查两颗树是否相同
OJ链接：检查两颗树是否相同
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null){ return true; } if (p == null || q == null){ return false; } if(q.val == p.val){ return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } return false; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4.2 寻找最近公共祖先
OJ链接：寻找最近公共祖先
class Solution1 { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Stack<TreeNode> stackP = new Stack<>(); Stack<TreeNode> stackQ = new Stack<>(); if(!getPath(root, p, stackP) || !getPath(root, q, stackQ)){ return null; } int size1 = stackP.size(); int size2 = stackQ.size(); int df = size1 - size2; if(df > 0){ int cnt = df; while (cnt != 0){ stackP.pop(); cnt--; } } else { int cnt = -df; while (cnt != 0){ stackQ.pop(); cnt--; } } while (!stackQ.isEmpty()){ TreeNode node1 = stackP.pop(); TreeNode node2 = stackQ.pop(); if(node1 == node2){ return node1; } } return null; } private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){ if(root == null || node == null){ return false; } stack.push(root); if(node == root){ return true; } boolean flag1 = getPath(root.left, node, stack); if(flag1){ return true; } boolean flag2 = getPath(root.right, node, stack); if(flag2){ return true; } stack.pop(); return false; } } class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null){ return null; } if(p == root || q == root){ return root; } TreeNode leftTree = lowestCommonAncestor(root.left, p, q); TreeNode rightTree = lowestCommonAncestor(root.right, p, q); if (leftTree != null && rightTree != null){ return root; } else if (leftTree != null){ return leftTree; } else if (rightTree != null) { return rightTree; } else { return null; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
4.3 另一颗树的子树
OJ链接：另一颗树的子树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // 判断两棵树是否相同 private boolean isSameTree(TreeNode p, TreeNode q){ if(p == null && q == null){ return true; } if(p == null || q == null) { return false; } if(q.val == p.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } return false; } public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(subRoot == null) return true; if(root == null){ return false; } return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
4.4 对称二叉树的判断
OJ链接：对称二叉树的判断
class Solution { public boolean isSymmetric(TreeNode root) { if(root == null ) return true; return _isSymmetric(root.left, root.right); } private boolean _isSymmetric(TreeNode leftTree, TreeNode rightTree){ if(leftTree == null && rightTree == null) return true; if(leftTree == null || rightTree == null) return false; if(leftTree.val != rightTree.val){ return false; } return _isSymmetric(leftTree.left, rightTree.right) && _isSymmetric(leftTree.right, rightTree.left); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
