C#使用自定义的泛型节点类接口 IBinaryTreeNode＜T＞实现二叉树类接口IBinaryTree＜T＞及其方法

2024-03-10 17:20:02
开发
19

1.首先，定义节点类接口 IBinaryTreeNode

2.第二，定义二叉树接口 IBinaryTree

3.第三，定义二叉树节点BinaryTreeNode(T value)

4.第四，二叉树方法实现

5.最后，用Main方法实现二叉树类接口IBinaryTree 及其方法

6.运行结果

C#使用自定义的泛型节点类接口 IBinaryTreeNode<T>实现二叉树类接口IBinaryTree<T> 及其方法并不简单，是作者连续发布的二叉树类实现方法中最难的方法。但这种方法仍然有它的特色和存在的意义。

在C#中，你可以定义一个二叉树接口IBinaryTree<T>来描述二叉树应有的行为，然后实现一个二叉树类（BinaryTree）来满足这个接口。下面是一个简单的例子，展示了如何定义二叉树接口并实现二叉树类：

1.首先，定义节点类接口 IBinaryTreeNode<T>

/// <summary>
///  二叉树节点接口
/// </summary>
public interface IBinaryTreeNode<T>
{
    T Value { get; set; }
    IBinaryTreeNode<T> Left { get; set; }
    IBinaryTreeNode<T> Right { get; set; }
}

2.第二，定义二叉树接口 IBinaryTree<T>

/// <summary>
/// 二叉树接口
/// 需要实现什么方法，就要设计什么接口
/// </summary>
public interface IBinaryTree<T> where T : IComparable<T>
{
    void Insert(T value);
    bool Search(T value);
    bool Delete(T value);
    void PreorderTraversal(Action<T> action);
    void InorderTraversal(Action<T> action);
    void PostorderTraversal(Action<T> action);
}

3.第三，定义二叉树节点BinaryTreeNode<T>(T value)

 /// <summary>
 /// 二叉树节点实现
 /// </summary>
 public class BinaryTreeNode<T>(T value) : IBinaryTreeNode<T> where T : IComparable<T>
 {
     public T Value { get; set; } = value;
     public BinaryTreeNode<T>? Left { get; set; } = null;
     public BinaryTreeNode<T>? Right { get; set; } = null;
     IBinaryTreeNode<T> IBinaryTreeNode<T>.Left { get => throw new NotImplementedException(); set => throw new NotImplementedException(); }
     IBinaryTreeNode<T> IBinaryTreeNode<T>.Right { get => throw new NotImplementedException(); set => throw new NotImplementedException(); }
 }

4.第四，二叉树方法实现

想实现什么方法，现在第2步定义方法的接口，然后第4步实现该方法的。

/// <summary>
/// 二叉树方法实现
/// </summary>
public class BinaryTree<T> : IBinaryTree<T> where T : IComparable<T>
{
    private BinaryTreeNode<T>? _root;

    /// <summary>
    /// 构造函数
    /// </summary>
    public BinaryTree()
    {
        _root = null;
    }

    /// <summary>
    /// 插入节点
    /// </summary>
    public void Insert(T value)
    {
        _root = BinaryTree<T>.InsertRecursive(_root!, value);
    }

    private static BinaryTreeNode<T> InsertRecursive(BinaryTreeNode<T> node, T value)
    {
        if (node == null)
        {
            return new BinaryTreeNode<T>(value);
        }

        if (value.CompareTo(node.Value) < 0)
        {
            node.Left = BinaryTree<T>.InsertRecursive(node.Left!, value);
        }
        else if (value.CompareTo(node.Value) > 0)
        {
            node.Right = BinaryTree<T>.InsertRecursive(node.Right!, value);
        }
        // 值已存在，可以选择不插入或替换
        // 这里选择不插入

        return node;
    }

    /// <summary>
    /// 查找节点
    /// </summary>
    public bool Search(T value)
    {
        return BinaryTree<T>.SearchRecursive(_root!, value);
    }

    private static bool SearchRecursive(BinaryTreeNode<T> node, T value)
    {
        if (node == null)
        {
            return false;
        }

        if (value.CompareTo(node.Value) == 0)
        {
            return true;
        }

        if (value.CompareTo(node.Value) < 0)
        {
            return BinaryTree<T>.SearchRecursive(node.Left!, value);
        }
        else
        {
            return BinaryTree<T>.SearchRecursive(node.Right!, value);
        }
    }

    /// <summary>
    /// 前序遍历
    /// </summary>
    /// <param name="action"></param>
    public void PreorderTraversal(Action<T> action)
    {
        BinaryTree<T>.PreorderTraversalRecursive(_root!, action);
    }

    private static void PreorderTraversalRecursive(BinaryTreeNode<T> node, Action<T> action)
    {
        if (node != null)
        {
            action(node.Value);
            BinaryTree<T>.PreorderTraversalRecursive(node.Left!, action);
            BinaryTree<T>.PreorderTraversalRecursive(node.Right!, action);
        }
    }

    /// <summary>
    /// 中序遍历
    /// </summary>
    /// <param name="action">委托行为</param>
    public void InorderTraversal(Action<T> action)
    {
        BinaryTree<T>.InorderTraversalRecursive(_root!, action);
    }

    private static void InorderTraversalRecursive(BinaryTreeNode<T> node, Action<T> action)
    {
        if (node != null)
        {
            BinaryTree<T>.InorderTraversalRecursive(node.Left!, action);
            action(node.Value);
            BinaryTree<T>.InorderTraversalRecursive(node.Right!, action);
        }
    }

    /// <summary>
    /// 后序遍历
    /// </summary>
    public void PostorderTraversal(Action<T> action)
    {
        BinaryTree<T>.PostorderTraversalRecursive(_root!, action);
    }

    private static void PostorderTraversalRecursive(BinaryTreeNode<T> node, Action<T> action)
    {
        if (node != null)
        {
            BinaryTree<T>.PostorderTraversalRecursive(node.Left!, action);
            BinaryTree<T>.PostorderTraversalRecursive(node.Right!, action);
            action(node.Value);
        }
    }

    /// <summary>
    /// 删除节点
    /// </summary>
    public bool Delete(T value)
    {
        _root = BinaryTree<T>.DeleteRecursive(_root!, value);
        return _root != null; // 如果根节点为空，说明树为空，返回false；否则返回true表示删除成功。
    }

    private static BinaryTreeNode<T>? DeleteRecursive(BinaryTreeNode<T>? node, T value)
    {
        if (node == null)
        {
            return null; // 节点不存在，直接返回null
        }

        if (value.CompareTo(node.Value) < 0)
        {
            node.Left = BinaryTree<T>.DeleteRecursive(node.Left!, value); // 在左子树中删除
        }
        else if (value.CompareTo(node.Value) > 0)
        {
            node.Right = BinaryTree<T>.DeleteRecursive(node.Right!, value); // 在右子树中删除
        }
        else
        {
            // 节点有三个可能的情况：叶子节点、一个子节点、两个子节点
            if (node.Left == null && node.Right == null) // 叶子节点
            {
                node = null;
            }
            else if (node.Left == null) // 只有一个右子节点
            {
                node = node.Right;
            }
            else if (node.Right == null) // 只有一个左子节点
            {
                node = node.Left;
            }
            else // 有两个子节点，找到右子树中的最小节点来替换
            {
                BinaryTreeNode<T> minNode = BinaryTree<T>.FindMin(node.Right);
                node.Value = minNode.Value;
                node.Right = BinaryTree<T>.DeleteRecursive(node.Right, minNode.Value);
            }
        }

        return node; // 返回更新后的节点
    }

    // 辅助方法：找到树中的最小节点
    private static BinaryTreeNode<T> FindMin(BinaryTreeNode<T> node)
    {
        if (node.Left == null)
        {
            return node; // 当前节点是最小节点
        }
        else
        {
            return BinaryTree<T>.FindMin(node.Left); // 递归地在左子树中查找最小节点
        }
    }
}

5.最后，用Main方法实现二叉树类接口IBinaryTree<T> 及其方法

把以上1~5步的源码放在一个命名空间下，框架.NET8.0以上控制台应用，运行。

 class Program
 {
     static void Main()
     {
         // 创建二叉树实例
         IBinaryTree<int> binaryTree = new BinaryTree<int>();
         // 插入节点
         binaryTree.Insert(5);
         binaryTree.Insert(3);
         binaryTree.Insert(7);
         binaryTree.Insert(2);
         binaryTree.Insert(4);
         binaryTree.Insert(6);
         binaryTree.Insert(8);

         // 搜索节点
         Console.WriteLine("Searching for 4: " + binaryTree.Search(4));
         Console.WriteLine("Searching for 9: " + binaryTree.Search(9));

         // 定义用于遍历的动作
         static void printValue(int value) => Console.Write(value + " ");

         // 前序遍历
         Console.WriteLine("Preorder Traversal:");
         binaryTree.PreorderTraversal(printValue);
         Console.WriteLine();

         // 中序遍历
         Console.WriteLine("Inorder Traversal:");
         binaryTree.InorderTraversal(printValue);
         Console.WriteLine();

         // 后序遍历
         Console.WriteLine("Postorder Traversal:");
         binaryTree.PostorderTraversal(printValue);
         Console.WriteLine();

         binaryTree.Delete(7);
         Console.WriteLine("删除后再执行后序遍历:");
         binaryTree.PostorderTraversal(printValue);
         Console.WriteLine();
     }
 }

6.运行结果

//运行结果：
/*
Searching for 4: True
Searching for 9: False
Preorder Traversal:
5 3 2 4 7 6 8
Inorder Traversal:
2 3 4 5 6 7 8
Postorder Traversal:
2 4 3 6 8 7 5
删除后再执行后序遍历:
2 4 3 6 8 5

原文地址:https://blog.csdn.net/wenchm/article/details/136596517 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1766755882986770432.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部