企业官网建设流程全解析

二叉树基础概念

二叉树定义

二叉树是一种非线性数据结构，由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。节点包含数据域和指针域（指向子节点）。

二叉树类型

满二叉树
所有非叶子节点都有两个子节点，且所有叶子节点在同一层。

完全二叉树
除最后一层外，其他层节点数达到最大值，最后一层节点从左到右连续填充。

二叉搜索树（BST）
左子树上所有节点的值小于根节点，右子树上所有节点的值大于根节点。

平衡二叉树
任意节点的左右子树高度差不超过1，例如AVL树。

常见操作

插入节点
根据二叉搜索树规则递归或迭代插入新节点。

删除节点
分三种情况处理：无子节点、有一个子节点、有两个子节点。

查找节点
根据值递归或迭代搜索，利用二叉搜索树特性可优化查找效率。

计算深度
递归计算左右子树深度，取最大值加1。

判断平衡
递归检查左右子树高度差是否超过1。

应用场景

• 文件系统目录结构
• 数据库索引（如B树、B+树）
• 哈夫曼编码
• 表达式树（用于编译器解析）

二叉树的实现方式

二叉树的实现方式

在Java中，二叉树可以通过节点类和树类来实现。以下是常见的实现方法：

节点类定义

节点类包含数据、左子节点和右子节点的引用。

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; } }

二叉树的遍历方法

二叉树的遍历包括前序遍历、中序遍历和后序遍历。

前序遍历

void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); }

中序遍历

void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); }

后序遍历

void postOrder(TreeNode root) { if (root == null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.val + " "); }

二叉树的插入

插入节点时需遵循二叉树的规则，通常用于二叉搜索树（BST）。

TreeNode insert(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) root.left = insert(root.left, val); else if (val > root.val) root.right = insert(root.right, val); return root; }

二叉树的搜索

搜索节点时需根据值比较递归查找。

boolean search(TreeNode root, int val) { if (root == null) return false; if (root.val == val) return true; if (val < root.val) return search(root.left, val); else return search(root.right, val); }

二叉树的删除

删除节点需处理三种情况：无子节点、有一个子节点、有两个子节点。

TreeNode delete(TreeNode root, int val) { if (root == null) return null; if (val < root.val) root.left = delete(root.left, val); else if (val > root.val) root.right = delete(root.right, val); else { if (root.left == null) return root.right; if (root.right == null) return root.left; TreeNode minNode = findMin(root.right); root.val = minNode.val; root.right = delete(root.right, minNode.val); } return root; } TreeNode findMin(TreeNode node) { while (node.left != null) node = node.left; return node; }

层序遍历

层序遍历使用队列实现，按层级输出节点值。

void levelOrder(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); } }

二叉树的高度计算

递归计算二叉树的最大深度。

int height(TreeNode root) { if (root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1; }

判断是否为平衡二叉树

平衡二叉树的左右子树高度差不超过1。

boolean isBalanced(TreeNode root) { if (root == null) return true; int leftHeight = height(root.left); int rightHeight = height(root.right); return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right); }

以上方法涵盖了二叉树的基本操作，可根据实际需求扩展功能。

常见二叉树类型及Java实现

常见二叉树类型

二叉搜索树（BST）
节点左子树的值均小于当前节点，右子树的值均大于当前节点。支持高效查找、插入和删除操作，时间复杂度为O(log n)（平衡状态下）。

平衡二叉树（AVL树）
通过旋转操作保持左右子树高度差不超过1，确保操作时间复杂度稳定在O(log n)。适合频繁插入删除的场景。

红黑树
通过颜色标记和旋转规则维持近似平衡，插入删除效率优于AVL树，广泛应用于Java的TreeMap和TreeSet。

完全二叉树
除最后一层外，所有层节点完全填满，且最后一层节点靠左排列。常用于堆的实现。

满二叉树
所有非叶子节点均有左右子节点，且所有叶子节点在同一层。

Java实现示例

二叉搜索树实现

class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } class BinarySearchTree { TreeNode root; void insert(int val) { root = insertRec(root, val); } private TreeNode insertRec(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) root.left = insertRec(root.left, val); else if (val > root.val) root.right = insertRec(root.right, val); return root; } boolean search(int val) { return searchRec(root, val); } private boolean searchRec(TreeNode root, int val) { if (root == null) return false; if (root.val == val) return true; return val < root.val ? searchRec(root.left, val) : searchRec(root.right, val); } }

平衡二叉树（AVL树）核心逻辑

class AVLNode { int val, height; AVLNode left, right; AVLNode(int val) { this.val = val; this.height = 1; } } class AVLTree { AVLNode root; int height(AVLNode node) { return node == null ? 0 : node.height; } AVLNode rotateRight(AVLNode y) { AVLNode x = y.left; AVLNode T2 = x.right; x.right = y; y.left = T2; y.height = Math.max(height(y.left), height(y.right)) + 1; x.height = Math.max(height(x.left), height(x.right)) + 1; return x; } // 类似实现rotateLeft和其他平衡逻辑 }

完全二叉树验证方法

boolean isCompleteTree(TreeNode root) { if (root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean end = false; while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) end = true; else { if (end) return false; queue.offer(node.left); queue.offer(node.right); } } return true; }

应用场景

• BST：适合有序数据查询，但需注意退化问题。
• AVL树：适合查询密集型场景，如数据库索引。
• 红黑树：Java集合框架中使用，平衡性能与实现复杂度。
• 完全二叉树：堆结构的基础，用于优先队列实现。