二叉树-删除指定节点
以上一篇为基础来看看树中的删除。
问题
（1）如果删除的节点是叶子节点，则删除该节点。
（2）如果删除的节点是非叶子节点，则删除该子树。
（3）测试，删除5号叶子节点和3号子树。
分析
首先先处理，如果树是空树，如果只有一个节点，则等价于将二叉树置空。
1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除节点，而不能去判断当前这个结点是不是需要删除节点。
2.如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.Left = null; 并且就返回（结束递归删除）
3.如果当前节点的右子节点不为空，且左子节点就是要删除的节点，就将this.Right = null; 并且就返回（结束递归删除）
4.如果第2步和第3步都没有删除掉节点，那么就需要向左子树递归删除。
5.如果第4步没有成功删除节点，则应当向右子树递归删除
代码：
代码语言：javascript复制 public class TreeNode
{
public int Id { get; set; }
public string Name { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode(int id,string name)
{
this.Id = id;
this.Name = name;
}
public override string ToString()
{
return $"TreeNode [id = { Id } , name ={ Name }]";
}
/// <summary>
/// 前序遍历
/// </summary>
public void PreOrder()
{
Console.WriteLine(this);
//递归向左子树前序遍历
if (this.Left != null)
{
this.Left.PreOrder();
}
//递归向右子树前序遍历
if (this.Right != null)
{
this.Right.PreOrder();
}
}
/// <summary>
/// 中序遍历
/// </summary>
public void InfixOrder()
{
//递归向左子树中序遍历
if (this.Left != null)
{
this.Left.InfixOrder();
}
//输出父节点
Console.WriteLine(this);
//递归向右子树中序遍历
if (this.Right != null)
{
this.Right.InfixOrder();
}
}
/// <summary>
/// 后续遍历
/// </summary>
public void PostOrder()
{
if (this.Left != null)
{
this.Left.PreOrder();
}
if (this.Right != null)
{
this.Right.PreOrder();
}
Console.WriteLine(this);
}
/// <summary>
/// 前序遍历查找
/// </summary>
/// <param name="id">根据id查找节点</param>
/// <returns></returns>
public TreeNode PreOrderSearch(int id)
{
Console.WriteLine("前序遍历查找" DateTime.Now);
//比较当前节点是不是
if (this.Id == id)
{
return this;
}
//1.则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
//2.如果左递归前序查找，找到节点，则返回
TreeNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.PreOrderSearch(id);
}
//说明我们左子树找到
if (resNode != null)
{
return resNode;
}
//左递归前序查找，找到站点，则返回，否则继续判断
//当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找。
if (this.Right != null)
{
resNode = this.Right.PreOrderSearch(id);
}
return resNode;
}
//中序遍历查找
public TreeNode InfixOrderSearch(int id)
{
TreeNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.InfixOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
Console.WriteLine("中序遍历查找" DateTime.Now);
if (this.Id == id)
{
return this;
}
if (this.Right != null)
{
resNode = this.Right.InfixOrderSearch(id);
}
return resNode;
}
//后序遍历查找
public TreeNode PostOrderSearch(int id)
{
TreeNode resNode = null;
if (this.Left != null)
{
resNode = this.Left.PostOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
if (this.Right != null)
{
resNode = this.Right.PostOrderSearch(id);
}
if (resNode != null)
{
return resNode;
}
Console.WriteLine("后序遍历查找" DateTime.Now);
if (this.Id == id)
{
return this;
}
return resNode;
}
/// <summary>
/// 根据id删除指定节点
/// </summary>
/// <param name="id"></param>
public void DeleteNode(int id)
{
if (this.Left != null && this.Left.Id == id)
{
this.Left = null;
return;
}
if (this.Right != null && this.Right.Id == id)
{
this.Right = null;
return;
}
if (this.Left != null)
{
this.Left.DeleteNode(id);
}
if (this.Right != null)
{
this.Right.DeleteNode(id);
}
}
}
public class BinaryTree
{
private TreeNode root;
public void SetRoot(TreeNode root)
{
this.root = root;
}
//前序遍历
public void PreOrder()
{
if (this.root != null)
{
this.root.PreOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
//中序遍历
public void InfixOrder()
{
if (this.root != null)
{
this.root.InfixOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
//后续遍历
public void PostOrder()
{
if (this.root != null)
{
this.root.PostOrder();
}
else
{
Console.WriteLine("二叉树为空，无法遍历！");
}
}
/// <summary>
/// 前序遍历查找
/// </summary>
/// <param name="id">根据id查找节点</param>
/// <returns></returns>
public TreeNode PreOrderSearch(int id)
{
if (root != null)
{
return root.PreOrderSearch(id);
}
else
{
return null;
}
}
//中序遍历查找
public TreeNode InfixOrderSearch(int id)
{
if (root != null)
{
return root.InfixOrderSearch(id);
}
else
{
return null;
}
}
//后序遍历查找
public TreeNode PostOrderSearch(int id)
{
if (root != null)
{
return root.PostOrderSearch(id);
}
else
{
return null;
}
}
public void DeleteNode(int id)
{
if (root != null)
{
if (root.Id == id)
{
root = null;
}
else
{
root.DeleteNode(id);
}
}
else
{
Console.WriteLine("空树无法删除！");
}
}
}调用：
代码语言：javascript复制 static void Main(string[] args)
{
//创建树
var tree = new BinaryTree();
//创建需要的节点
TreeNode root = new TreeNode(1,"名册");
TreeNode node2 = new TreeNode(2, "张三");
TreeNode node3 = new TreeNode(3,"李四");
TreeNode node4 = new TreeNode(4,"王五");
TreeNode node5 = new TreeNode(5, "赵六");
//手动创建二叉树
root.Left = node2;
root.Right = node3;
node3.Left = node5;
node3.Right = node4;
tree.SetRoot(root);
Console.WriteLine("删除前，前序遍历");
tree.PreOrder();
tree.DeleteNode(5);
Console.WriteLine("删除后，前序遍历");
tree.PreOrder();
tree.DeleteNode(3);
Console.WriteLine("删除后，前序遍历");
tree.PreOrder();
Console.Read();
}
