甘肃网站设计公司_黄山旅游攻略自驾游_百度网盘app下载安装 官方下载_新闻近期大事件

en造数据结构与算法C# 之 二叉排序树的增/查-CSDN博客

删除方法比起添加和查找就稍显复杂了 ，所以单独拿出来写一篇

分析

输入

1.根节点，用于从根上查找你要删除的节点

2.需要删除的值

   public Node<T> Delete(Node<T> root, T data) {if (root == null)return root;

删除节点比如，比如我有一个如下的二叉树

 1.找到最后，要删除的节点是叶子节点

删除20

2.找到最后，要删除的节点只有一个子节点

删除70，我们会发现

3.找到最后，发现要删除的节点的子树是满的，左右叶子都有

那就需要从该节点的右子树去找最小值，替换该位置

所以，从程序上来讲的话，需要分一个状态+两种情况

一个状态 = 找到需要删除的位置

两种情况 = 1.要删除的是叶子节点或者只有一个子节点 + 2.左右子节点都存在

上代码

/// <summary>/// 删除节点/// </summary>/// <param name="root">根节点</param>/// <param name="data">需要删除值</param>/// <returns></returns>public Node<T> Delete(Node<T> root, T data) {if (root == null)return root;// 找到要删除的节点if (data.CompareTo(root.data) < 0)root.LeftNode = Delete(root.LeftNode, data);else if (data.CompareTo(root.data) > 0)root.RightNode = Delete(root.RightNode, data);else {// 情况1：节点是叶子节点或只有一个子节点if (root.LeftNode == null)return root.RightNode;else if (root.RightNode == null)return root.LeftNode;// 情况2：节点有两个子节点// 找到右子树中的最小值节点root.data = MinValue(root.RightNode);// 删除右子树中的最小值节点root.RightNode = Delete(root.RightNode, root.data);}return root;}private T MinValue(Node<T> root) {T minValue = root.data;while (root.LeftNode != null) {minValue = root.LeftNode.data;root = root.LeftNode;}return minValue;}