C#二叉树原理及二叉搜索树代码实现

一、概念

        二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的每个节点包含三个部分：一个值、一个指向左子节点的引用和一个指向右子节点的引用。

二、二叉树的基本概念

1. 节点：二叉树中的每个元素称为节点。每个节点包含一个值以及指向其左子节点和右子节点的引用。
2. 根节点：二叉树的顶端节点称为根节点。它是树中唯一没有父节点的节点。
3. 子节点：每个节点可以有零个、一或两个子节点。子节点分为左子节点和右子节点。
4. 叶节点：没有子节点的节点称为叶节点或终端节点。
5. 内部节点：至少有一个子节点的节点称为内部节点。
6. 高度：从根节点到某个节点的最长路径上的边数称为该节点的高度。树的高度是所有节点高度的最大值。
7. 深度：从根节点到某个节点的路径上的边数称为该节点的深度。根节点的深度为0。
8. 层次：树中所有深度相同的节点组成一层。根节点在第0层，其子节点在第1层，以此类推。

三、二叉树的类型

1. 满二叉树：每个节点要么是叶节点，要么有两个子节点。
2. 完全二叉树：除了最后一层外，每一层都是满的，并且最后一层的所有节点都尽可能地靠左排列。
3. 二叉搜索树（BST）：对于树中的每个节点，其左子树中的所有节点值都小于该节点的值，而其右子树中的所有节点值都大于该节点的值。

四、二叉树的作用

1. 快速查找：二叉搜索树允许我们以O(log n)的时间复杂度进行查找操作。
2. 排序：通过中序遍历，可以得到一个有序的元素列表。
3. 动态集合：支持动态插入和删除操作，适用于需要频繁修改的数据集合。
4. 表达式解析：二叉树常用于表示算术表达式，其中内部节点表示运算符，叶节点表示操作数。

五、二叉树的遍历

遍历是指访问树中每个节点的过程。常见的遍历方法包括：

1. 前序遍历（Pre-order Traversal）：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。
2. 中序遍历（In-order Traversal）：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。这种遍历方式特别适用于二叉搜索树，因为它会按升序访问所有节点。
3. 后序遍历（Post-order Traversal）：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。
4. 层次遍历（Level-order Traversal）：按层次逐层访问节点，从上到下，从左到右。

六、二叉搜索树（Binary Search Tree, BST）

定义

二叉搜索树是一种特殊的二叉树，它满足以下性质：

• 对于树中的每个节点，其左子树中的所有节点值都小于该节点的值，而其右子树中的所有节点值都大于该节点的值。

特性

1. 查找操作：由于二叉搜索树的性质，可以通过比较节点值快速定位目标节点，平均时间复杂度为O(log n)。
2. 插入操作：新节点总是插入到叶节点的位置，保持二叉搜索树的性质。
3. 删除操作：删除节点时需要考虑三种情况：
   • 节点是叶节点：直接删除即可。
   • 节点有一个子节点：用子节点替换被删除的节点。
   • 节点有两个子节点：找到该节点的中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点），用它替换被删除的节点，然后删除该后继或前驱节点。

七、二叉搜索树代码实现

        1、定义二叉树结构

 /// <summary>/// 二叉树搜索树节点结构/// </summary>public class TreeNode{public int Value;public TreeNode? Left;public TreeNode? Right;public TreeNode(int value) {Value = value;Left = null;Right = null;}}

         2、定义二叉搜索树类，实现包括二叉搜索树的插入、删除、搜索、中序遍历等

/// <summary>
/// 二叉搜索树
/// </summary>
public class BinarySearchTree
{private TreeNode? root;public BinarySearchTree() { root = null; }//二叉树插入数据public void BinaryTreeInsert(int value){if (root == null){root = new TreeNode(value);            }else{InsertRec(root, value);}        }//递归插入数据到二叉树public void InsertRec(TreeNode node,int value){if(value < node.Value)//小于当前节点，往当前节点的左子树判断插入{if(node.Left == null){node.Left = new TreeNode(value);}else{InsertRec(node.Left, value);}}else if(value > node.Value)//大于当前节点，往当前节点的右子树判断插入{if(node.Right == null){node.Right = new TreeNode(value);}else{InsertRec(node.Right, value);}}else if (value == node.Value) //等于当前节点，重复不插入{return;}}//二叉树搜索public bool BinaryTreeSearch(int value){return SearchRec(root, value);}//递归搜索二叉树public bool SearchRec(TreeNode? node,int value){if(node == null){return false;}if (value < node.Value)//小于当前节点，往当前节点的左子树判断比较{return SearchRec(node.Left, value);}else if (value > node.Value){return SearchRec(node.Right, value);//大于当前节点，往当前节点的左子树判断比较}else{return true; }}//二叉树删除节点public void BinaryTreeRemove(int value){root = RemoveRec(root, value);}//递归删除二叉树节点public TreeNode? RemoveRec(TreeNode? node,int value){if (node == null){ return null; }if(value < node.Value){node.Left = RemoveRec(node.Left, value);}else if(value > node.Value){node.Right = RemoveRec(node.Right, value);}else{if(node.Left != null && node.Right != null){//如果需要删除的节点左右子节点都不为空，使用节点的右子树的最小节点替换当前节点TreeNode? minNode = FinMinNode(node.Right);if(minNode != null){node.Value = minNode.Value;node.Right = RemoveRec(node.Right, minNode.Value);}}else{TreeNode? tempNode = node.Left != null ? node.Left : node.Right;node = tempNode;}}return node;}//查找二叉树的最小节点public TreeNode? FinMinNode(TreeNode? node){if(node == null){return null;}while (node.Left != null) //往左子树找最小{ node = node.Left;}return node;}//遍历二叉树排序输出public List<int> InorderTraversal(){List<int> arry = new List<int>();InorderTraversalRec(root,arry);return arry;}public void InorderTraversalRec(TreeNode? node, List<int> arrys){if(node != null){InorderTraversalRec(node.Left , arrys);arrys.Add(node.Value);InorderTraversalRec(node.Right , arrys);}}//后序遍历public void PostOrderTraversal(){PostOrderTraversalRec(root);}public void PostOrderTraversalRec(TreeNode? node){if (node == null){return;}PostOrderTraversalRec(node.Right);PostOrderTraversalRec(node.Left);Console.WriteLine(node.Value);}//前序遍历public void PreOrderTraversal(){PreOrderTraversalRec(root);}public void PreOrderTraversalRec(TreeNode? node){if(root == null){return;}Console.WriteLine(node.Value);PreOrderTraversalRec(node.Left);PreOrderTraversalRec(node.Right);}
}

八、二叉搜索树验证

        1、编写验证代码：

static async Task Main(string[] args)
{BinarySearchTreeTest();
}/// <summary>
/// 二叉树测试
/// </summary>
static void BinarySearchTreeTest()
{var bst = new BinarySearchTree();bst.BinaryTreeInsert(35);bst.BinaryTreeInsert(13);bst.BinaryTreeInsert(23);bst.BinaryTreeInsert(45);bst.BinaryTreeInsert(78);bst.BinaryTreeInsert(4);bst.BinaryTreeInsert(17);bst.BinaryTreeInsert(89);bst.BinaryTreeInsert(67);Console.WriteLine("中序遍历（打印有序数组）：");List<int> list = bst.InorderTraversal();foreach (int i in list){Console.WriteLine(i);}Console.WriteLine("\n");// 查找Console.WriteLine("Search for 45: " + bst.BinaryTreeSearch(45)); // 输出: TrueConsole.WriteLine("Search for 25: " + bst.BinaryTreeSearch(25)); // 输出: FalseConsole.WriteLine("\n");// 删除bst.BinaryTreeRemove(17);Console.WriteLine("删除17后,中序遍历（打印有序数组）：");List<int> list1 = bst.InorderTraversal();foreach (int j in list1){Console.WriteLine(j);}
}

         2、运行验证

总结