C#二叉树
二叉树是一种常见的数据结构，它是由节点组成的一种树形结构，其中每个节点最多有两个子节点。二叉树的一个节点通常包含三部分：存储数据的变量、指向左子节点的指针和指向右子节点的指针。二叉树可以用于多种算法和操作，如搜索、排序和遍历。
二叉树遍历
| 遍历方式 | 顺序 | C#递归实现核心代码 |
|---|---|---|
| 前序遍历 | 根 → 左 → 右 | Console.Write(root.val); → 递归左 → 递归右 |
| 中序遍历 | 左 → 根 → 右 | 递归左 → Console.Write(root.val); → 递归右 |
| 后序遍历 | 左 → 右 → 根 | 递归左 → 递归右 → Console.Write(root.val); |
二叉树的应用场景
- 快速查找与排序
- 二叉搜索树用于实现字典、数据库索引（如B树、B+树的基础）。
- 表达式树
- 编译器解析数学表达式时构建二叉树，叶节点为操作数，非叶节点为运算符。
- 哈夫曼编码
- 通过构建最优二叉树实现数据压缩。
- 决策树与机器学习
- 二叉树结构用于分类和回归模型的决策过程。
二叉树的优缺点
| 优点 | 缺点 |
|---|---|
| 逻辑清晰，易于实现递归操作 | 普通二叉树可能退化为链表（时间复杂度升至O(n)) |
| 二叉搜索树支持高效查找/插入 | 平衡二叉树实现复杂（如AVL树的旋转操作） |
| 天然适合分治算法（如快速排序） | 存储指针占用额外内存空间 |
实例1
using System;
using System.Collections.Generic;public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) { val = x; }
}class BinaryTreeDemo
{static void Main(){// 构建二叉树TreeNode root = new TreeNode(1){left = new TreeNode(2){left = new TreeNode(4),right = new TreeNode(5)},right = new TreeNode(3)};Console.WriteLine("前序遍历:");PreOrder(root); // 输出: 1 2 4 5 3Console.WriteLine("\n层序遍历:");LevelOrder(root); // 输出: 1 2 3 4 5}// 前序遍历static void PreOrder(TreeNode root){if (root == null) return;Console.Write(root.val + " ");PreOrder(root.left);PreOrder(root.right);}// 层序遍历static void LevelOrder(TreeNode root){if (root == null) return;Queue<TreeNode> queue = new Queue<TreeNode>();queue.Enqueue(root);while (queue.Count > 0){TreeNode node = queue.Dequeue();Console.Write(node.val + " ");if (node.left != null) queue.Enqueue(node.left);if (node.right != null) queue.Enqueue(node.right);}}
}
实例2
public class TreeNode<T>
{public T Value { get; set; }public TreeNode<T> Left { get; set; }public TreeNode<T> Right { get; set; }public TreeNode(T value){Value = value;Left = null;Right = null;}
}public class BinaryTree<T>
{public TreeNode<T> Root { get; private set; }public BinaryTree(){Root = null;}// 插入新值到二叉树中public void Add(T value){if (Root == null){Root = new TreeNode<T>(value);}else{AddTo(Root, value);}}private void AddTo(TreeNode<T> node, T value){if (Comparer<T>.Default.Compare(value, node.Value) < 0){if (node.Left == null){node.Left = new TreeNode<T>(value);}else{AddTo(node.Left, value);}}else{if (node.Right == null){node.Right = new TreeNode<T>(value);}else{AddTo(node.Right, value);}}}// 前序遍历（根-左-右）public void PreOrderTraversal(TreeNode<T> node){if (node != null){Console.WriteLine(node.Value); // 访问节点PreOrderTraversal(node.Left); // 遍历左子树PreOrderTraversal(node.Right); // 遍历右子树}}// 中序遍历（左-根-右）public void InOrderTraversal(TreeNode<T> node){if (node != null){InOrderTraversal(node.Left); // 遍历左子树Console.WriteLine(node.Value); // 访问节点InOrderTraversal(node.Right); // 遍历右子树}}// 后序遍历（左-右-根）public void PostOrderTraversal(TreeNode<T> node){if (node != null){PostOrderTraversal(node.Left); // 遍历左子树PostOrderTraversal(node.Right); // 遍历右子树Console.WriteLine(node.Value); // 访问节点}}
}
实例3
class BSTDemo
{static void Main(){TreeNode root = null;// 插入节点root = InsertBST(root, 5);InsertBST(root, 3);InsertBST(root, 7);InsertBST(root, 2);Console.WriteLine("中序遍历BST:");InOrder(root); // 输出: 2 3 5 7// 删除节点3root = DeleteNode(root, 3);Console.WriteLine("\n删除后:");InOrder(root); // 输出: 2 5 7}// BST插入static TreeNode InsertBST(TreeNode root, int val){if (root == null) return new TreeNode(val);if (val < root.val)root.left = InsertBST(root.left, val);elseroot.right = InsertBST(root.right, val);return root;}// BST删除（使用之前定义的DeleteNode方法）// 中序遍历static void InOrder(TreeNode root){if (root == null) return;InOrder(root.left);Console.Write(root.val + " ");InOrder(root.right);}
}
实例4
class SymmetricTreeDemo
{static void Main(){// 对称二叉树TreeNode root1 = new TreeNode(1){left = new TreeNode(2) { left = new TreeNode(3), right = new TreeNode(4) },right = new TreeNode(2) { left = new TreeNode(4), right = new TreeNode(3) }};// 非对称二叉树TreeNode root2 = new TreeNode(1){left = new TreeNode(2) { right = new TreeNode(3) },right = new TreeNode(2) { right = new TreeNode(3) }};Console.WriteLine("root1是否对称: " + IsSymmetric(root1)); // trueConsole.WriteLine("root2是否对称: " + IsSymmetric(root2)); // false}static bool IsSymmetric(TreeNode root){if (root == null) return true;return CheckSymmetric(root.left, root.right);}static bool CheckSymmetric(TreeNode left, TreeNode right){if (left == null && right == null) return true;if (left == null || right == null) return false;return left.val == right.val && CheckSymmetric(left.left, right.right)&& CheckSymmetric(left.right, right.left);}
}
实例5
class DepthDemo
{static void Main(){TreeNode root = new TreeNode(1){left = new TreeNode(2) { left = new TreeNode(4) },right = new TreeNode(3)};Console.WriteLine("最大深度: " + MaxDepth(root)); // 输出: 3}static int MaxDepth(TreeNode root){if (root == null) return 0;return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;}
}
实例6
class PathSumDemo
{static void Main(){TreeNode root = new TreeNode(5){left = new TreeNode(4) { left = new TreeNode(11) { left = new TreeNode(7), right = new TreeNode(2) } },right = new TreeNode(8) { left = new TreeNode(13), right = new TreeNode(4) { right = new TreeNode(1) } }};Console.WriteLine("是否存在和为22的路径: " + HasPathSum(root, 22)); // true}static bool HasPathSum(TreeNode root, int targetSum){if (root == null) return false;if (root.left == null && root.right == null)return root.val == targetSum;return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);}
}
关键点总结
- 递归思想：二叉树问题多通过递归解决，注意终止条件（
root == null） - BST特性：插入/删除时利用左小右大规则
- 遍历选择：
- 前序：根节点最先访问
- 中序：BST会得到有序序列
- 层序：需要队列辅助
- 空间复杂度：
- 递归：O(h)（h为树高）
- 层序：O(n)