用BinaryTree<T>编写的C#

Question

我用.NET Core 3.0写了一棵二叉树。我能做些什么来改进我的编码风格？

using System;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

namespace BinaryTree
{
    /// 
    /// Represents a binary tree .
    /// 
    /// The type which this tree should contain.
    [Serializable]
    [DataContract]
    public class BinaryTree where T : IComparable, new()
    {
#if DEBUG
        /// 
        /// Determines whether or not to log actions in the console.
        /// 
        public static bool Log = true;
#endif

        [DataMember]
        private Node _parentNode;

        public BinaryTree()
        {
#if DEBUG
            if (Log)
                Console.WriteLine("Initializing binary-tree..");
#endif
            _parentNode = new Node();
        }

        /// 
        /// Adds the specific item inside the binary-tree using binary-tree logic.
        /// 
        /// The item that will be added.
        public void Add(T item)
        {
#if DEBUG
            if (Log)
                Console.WriteLine("Initializing binary-tree..");
#endif
            _parentNode.Add(item);
        }

        /// 
        /// Removes the specific item inside the binary-tree using binary-tree logic. The root node cannot be removed.
        /// 
        /// The item that will be removed.
        public void Remove(T item)
        {
            _parentNode.Remove(item);
        }

        /// 
        /// Searches for a specific item inside this binary-tree using binary-tree logic.
        /// 
        /// 
        /// Returns the count of said item if existing - 0 if otherwise.
        public int Contains(T item)
        {
            return _parentNode.Contains(item);
        }

        /// 
        /// Clears everything out of this binary-tree.
        /// 
        public void Clear()
        {
            _parentNode = new Node();
        }

        public override bool Equals(object obj)
        {
            return obj is BinaryTree tree && tree._parentNode.Equals(_parentNode);
        }

        public void Serialize(string file)
        {
            using (var writer = new StreamWriter(file))
            {
                var bf = new BinaryFormatter();
                bf.Serialize(writer.BaseStream, this);
            }
        }

        public static BinaryTree Deserialize(string file)
        {
            using (var reader = new StreamReader(file))
            {
                var bf = new BinaryFormatter();
                return (BinaryTree)bf.Deserialize(reader.BaseStream);
            }
        }

        /// 
        /// Represents a node of a binary-tree. This may be either a simple node, a parent, or a leaf.
        /// 
        /// The type which this node should contain.
        [Serializable]
        [DataContract]
        private class Node where T : IComparable, new()
        {
            /// 
            /// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
            /// 
            [DataMember]
            private Node _bigger;

            /// 
            /// Saved data and count of data - inside this specific node.
            /// 
            [DataMember]
            private (T data, int count) _item;

            /// 
            /// Root node, if existing.
            /// 
            [DataMember]
            private Node _parent;

            /// 
            /// Left "lower" arm of current node - this is where everything smaller than this node is getting redirect towards.
            /// 
            [DataMember]
            private Node _smaller;

            private Node(T item)
            {
                _item = (item, 1);
            }

            public Node()
            {
            }

            public override bool Equals(object obj)
            {
                return obj is Node node &&
                       (node._bigger?.Equals(_bigger) ?? _bigger == null) &&
                       (node._item.data?.Equals(_item.data) ?? _item.data == null) &&
                       (node._item.count.Equals(_item.count)) &&
                       (node._parent?.Equals(_parent) ?? _parent==null) &&
                       (node._smaller?.Equals(_smaller) ?? _smaller == null);
            }

            private void Set(T data)
            {
                if (_item.data.Equals(default(T)))
                {
                    _item = (data, 1);
                    return;
                }

                if (data.Equals(_item.data))
                    _item.count++;
                else
                    Add(data);
            }

            public void Remove(T data)
            {
                if (data.Equals(_item.data))
                {
                    if (_item.count > 1)
                    {
                        _item.count--;
                    }
                    else
                    {
                        if (_parent == null) return;

                        var replacement = new Node(data)
                        {
                            _smaller = _smaller,
                            _bigger = _bigger,
                            _parent = _parent
                        };

                        if (_parent._item.data.CompareTo(_item.data) == 1)
                            _parent._smaller = replacement;
                        else
                            _parent._bigger = replacement;
                    }
                }
                else
                {
                    if (data.CompareTo(_item.data) == 1)
                    {
                        _bigger?.Remove(data);
                        if (_bigger != null) _bigger._parent = this;
                    }
                    else
                    {
                        _smaller?.Remove(data);
                        if (_smaller != null) _smaller._parent = this;
                    }
                }
            }

            public void Add(T item)
            {
                if (_item.data.Equals(default(T)))
                {
                    Set(item);
                    return;
                }

                if (item.CompareTo(_item.data) == 1)
                {
#if DEBUG
                    if (Log)
                        Console.WriteLine($"{item} > {_item.data} → move to right lower node..");
#endif
                    (_bigger = CreateOrReturnNode(_bigger)).Set(item);
                }
                else
                {
#if DEBUG
                    if (Log)
                        Console.WriteLine($"{item} < {_item.data} → move to left lower node..");
#endif
                    (_smaller = CreateOrReturnNode(_smaller)).Set(item);
                }
            }

            public int Contains(T value)
            {
                if (_item.data.Equals(value))
                {
#if DEBUG
                    if (Log)
                        Console.WriteLine("Item was found!");
#endif
                    return _item.count;
                }

                if (value.CompareTo(_item.data).Equals(1))
                {
#if DEBUG
                    if (Log)
                        Console.WriteLine($"{value} > {_item.data} → search in right lower node..");
#endif
                    return _bigger?.Contains(value) ?? 0;
                }

#if DEBUG
                if (Log)
                    Console.WriteLine($"{value} < {_item.data} → search in left lower node..");
#endif
                return _smaller?.Contains(value) ?? 0;
            }

            /// 
            /// Either creates a new node, or returns the existing one.
            /// 
            /// The node which is getting checked whether it is set or not.
            /// Either a new node, or the already existing one.
            private static Node CreateOrReturnNode(Node node = null)
            {
                return node ?? new Node();
            }
        }
    }
}

Updated版本： https://github.com/TheRealVira/binary-tree/blob/master/BinaryTree/BinaryTree.cs

Answer 1

public class BinaryTree where T : IComparable, new()

我怀疑你没有意识到写作的可能性

    public class BinaryTree where T : IComparable, new()

如果您确实有意地选择了IComparable而不是IComparable，那么添加一个解释原因的评论会很有帮助。

为什么是where T : new()？代码在任何地方都不会调用new T()。

如果您还实现了IEnumerable，那么类将更加强大，而且理想情况下，您将实现ICollection。

private Node \_parentNode;

Node是一个内部类，因此它不需要类型参数。您可以删除它，外部类中的T将在作用域中。如果您从Java学习过C#，那么请注意，这是它们的类型系统的更大差异之一。

#如果调试if (日志)Console.WriteLine(“初始化二叉树.”)；#endif

如果使用System.Diagnostics.Debug.WriteLine，则(a)可以跳过所有的#if DEBUG；(b)在Visual中运行时，即使在进程完成之后，输出窗格中也可以使用日志。

或者，您可以将其提升到一个级别，并使用一个适当的运行时可配置日志库，如Serilog、log4net、.

public void Add(T item) { #if DEBUG if (Log) Console.WriteLine("Initializing binary-tree.."); #endif \_parentNode.Add(item); }

日志信息看起来很可疑..。

另外，我看到您已经做出了将大部分逻辑推入节点的设计决策。由于您似乎是作为一个学习练习来这样做的，因此为了比较起见，我建议您单独实现一个版本，该版本将节点作为纯数据对象，并将所有的逻辑放入BinaryTree的方法中。这使您可以使用尾优化(将递归转换为while循环)。

public override bool Equals(object obj) { return obj is BinaryTree tree && tree.\_parentNode.Equals(\_parentNode); }

Visual对此提出了警告:当您重写Equals时，您应该重写GetHashcode，否则，如果您将该类的实例放置在HashSet<>中或作为Dictionary中的键，您将花费很长时间进行调试。

这同样适用于Node。

/// /// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards. /// [DataMember] private Node \_bigger;

我设法理解了代码ok，但更传统的做法是将其命名为_right。(也可能是right，但我不想对这种命名惯例发牢骚)。

private (T data, int count) \_item;

count是不寻常的。实际上，您正在实现一个IDictionary：也许推广到IDictionary并有一个单独的包装类将任何IDictionary转换为计数器是有意义的。

            public override bool Equals(object obj)
            {
                return obj is Node node &&
                       (node._bigger?.Equals(_bigger) ?? _bigger == null) &&
                       (node._item.data?.Equals(_item.data) ?? _item.data == null) &&
                       (node._item.count.Equals(_item.count)) &&
                       (node._parent?.Equals(_parent) ?? _parent==null) &&
                       (node._smaller?.Equals(_smaller) ?? _smaller == null);
            }

ValueStruct重写了==，因此可以简化一些。除非您想疑神疑鬼，并假设T可能没有与CompareTo一致的Equals，在这种情况下，您应该在这里使用CompareTo来比较_item.data。

public void Remove(T data) { if (data.Equals(\_item.data)) { if (\_item.count > 1) { \_item.count--; } else { if (\_parent == null) return;

唯一接触_parent的地方是Remove，所以如果我向树中添加一个项，然后用相同的项调用Remove，它就不会被删除。

public int Contains(T value) { if (\_item.data.Equals(value))

当我在一棵空树上给Contains打电话时，这里有一个D62。

public void Add(T item) { if (\_item.data.Equals(default(T)))

当树是空的时，这里有一个NullReferenceException：您测试过这些代码吗？

if (\_parent.\_item.data.CompareTo(\_item.data) == 1) if (data.CompareTo(\_item.data) == 1) if (item.CompareTo(\_item.data) == 1) if (value.CompareTo(\_item.data).Equals(1))

IComparable的约定并不表示返回的值总是-1、0或1。我不知道为什么很多人都这么认为。您应该始终将返回值与0进行比较。

Answer 2

好吧，我不希望在BinaryTree类中有一个私有Node类。我认为在树中添加/删除节点的逻辑应该在tree类而不是Node类级别上完成。

可以将Node类移动到自己的文件中，将其重命名为BinaryNodeTree，并将添加/删除逻辑移动到树本身，树本身也可以使用实用工具类搜索节点以添加值。