C#二叉樹

二叉樹是一種常見的數據結構，它是由節點組成的一種樹形結構，其中每個節點最多有兩個子節點。二叉樹的一個節點通常包含三部分：存儲數據的變量、指向左子節點的指針和指向右子節點的指針。二叉樹可以用于多種算法和操作，如搜索、排序和遍歷。

二叉樹遍歷

遍歷方式	順序	C#遞歸實現核心代碼
前序遍歷	根 → 左 → 右	Console.Write(root.val); → 遞歸左 → 遞歸右
中序遍歷	左 → 根 → 右	遞歸左 → Console.Write(root.val); → 遞歸右
后序遍歷	左 → 右 → 根	遞歸左 → 遞歸右 → Console.Write(root.val);

二叉樹的應用場景

1. 快速查找與排序
   • 二叉搜索樹用于實現字典、數據庫索引（如B樹、B+樹的基礎）。
2. 表達式樹
   • 編譯器解析數學表達式時構建二叉樹，葉節點為操作數，非葉節點為運算符。
3. 哈夫曼編碼
   • 通過構建最優二叉樹實現數據壓縮。
4. 決策樹與機器學習
   • 二叉樹結構用于分類和回歸模型的決策過程。

二叉樹的優缺點

優點	缺點
邏輯清晰，易于實現遞歸操作	普通二叉樹可能退化為鏈表（時間復雜度升至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);}
}

關鍵點總結

1. 遞歸思想：二叉樹問題多通過遞歸解決，注意終止條件（root == null）
2. BST特性：插入/刪除時利用左小右大規則
3. 遍歷選擇：
   • 前序：根節點最先訪問
   • 中序：BST會得到有序序列
   • 層序：需要隊列輔助
4. 空間復雜度：
   • 遞歸：O(h)（h為樹高）
   • 層序：O(n)