二叉树是一种常见的数据结构，它是由节点组成的一种树形结构，其中每个节点最多有两个子节点。二叉树的一个节点通常包含三部分：存储数据的变量、指向左子节点的指针和指向右子节点的指针。二叉树可以用于多种算法和操作，如搜索、排序和遍历。
在这里插入图片描述
二叉树遍历
遍历方式 顺序 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 3
Console.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
// 删除节点3
root = 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);
else
root.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)); // true
Console.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)