X‘’mas树实现

Question

随着节日的气氛和新年的到来，我想今年我要提出第一个问题，那就是树的实现。怪我吧，因为圣诞节没什么可做的。

public interface ITreeITem
{
    object Key { get;  }
    object ParentKey { get; set; }
}

public class Tree<T> : IEnumerable<T>
    where T: ITreeITem
{
    private readonly IDictionary<object, Tree<T>> _items = new Dictionary<object, Tree<T>>(7);
    public T Item { get; set; }
    public Tree()
    {
    }  

    public Tree(IEnumerable<T> values)
    {
        foreach (var value in values)
        {
            if (value.ParentKey == null)
            {
                AddAsSubTree(value);
            }
            else
            {
                Parent(value)?.AddAsSubTree(value);
            }
        }
    }

    public IEnumerable<Tree<T>> Children
    {
        get { return _items.Values; }
    }

    public Tree<T> Parent(T item)
    {
        if (item.ParentKey == null)
        {
            return this;
        }
        if(_items.Count == 0)
        {
            return null;
        }
        var child = _items.TryGetOrValue(item.ParentKey, null);
        if (child == null)
        {
            return _items.Values
                .Select(v => v.Parent(item))
                .FirstOrDefault(v => v != null);
        }
        else
        {
            return child;
        }
    }

    public Tree<T> Parent(T item, int level)
    {
        if (level == 1)
        {
            return this;
        }
        return ChildrenInLevel(level - 1)
            .FirstOrDefault(t => t._items.ContainsKey(item.ParentKey));
    } 

    protected Tree<T> AddAsSubTree(T item)
    {
        var tree = new Tree<T>
        {
            Item = item
        };
        _items.Add(item.Key, tree);
        return tree;
    }

    protected IEnumerable<T> AllChildren(Tree<T> root)
    {
        foreach (var item in root._items.Values)
        {
            yield return item.Item;
            foreach (var aux in AllChildren(item))
            {
                yield return aux;
            }
        }
    }

    protected IEnumerable<Tree<T>> ChildrenInLevel(int level)
    {
        var children = Children;
        while (--level > 0)
        {
            children = children.SelectMany(t => t._items.Values);
        }
        return children;
    }

    public Tree<T> Add(T item)
    {
        return Parent(item).AddAsSubTree(item);
    }

    public Tree<T> Add(T item, int level)
    {
        return Parent(item, level).AddAsSubTree(item);
    }

    public bool RemoveItemAndChildren(T item)
    {
        if (Parent(item)._items.Remove(item.Key))
        {
            item.ParentKey = null;
            return true;
        }
        return false;
    }

    public bool RemoveItemAndChildren(T item, int level)
    {
        if (Parent(item, level)._items.Remove(item.Key))
        {
            item.ParentKey = null;
            return true;
        }
        return false;
    }

    public class Family
    {
        public Family(Tree<T> tree, T item)
        {
            Parent = tree.Parent(item);
            Children = Parent._items[item.Key].Children;
        }

        public Family(Tree<T> tree, T item, int level)
        {
            Parent = tree.Parent(item, level);
            Children = Parent._items[item.Key].Children;
        }

        public Tree<T> Parent { get; set; }
        public IEnumerable<Tree<T>> Children { get; set; }

        public IEnumerable<T> Remove(T item)
        {
            Parent._items.Remove(item.Key);
            yield return item;
            foreach (var child in Children)
            {
                Parent._items.Add(child.Item.Key, child);
                child.Item.ParentKey = item.ParentKey;
                yield return child.Item;
            }
        } 
    }

    public IEnumerable<T> Remove(T item)
    {
        var family = new Family(this, item);
        return family.Remove(item).ToList();
    }

    public IEnumerable<T> Remove(T item, int level)
    {
        var family = new Family(this, item, level);
        return family.Remove(item).ToList();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return AllChildren(this).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

我也对它进行了一些测试，这样您也可以运行测试并修改它。

public class Model : ITreeITem
{
    public int ID { get; set; }
    public int? ParentID { get; set; }
    public string Text { get; set; }
    public object Key
    {
        get { return ID; }
    }

    public object ParentKey
    {
        get { return ParentID; }
        set { ParentID = (int?)value; }
    }
}

public class TestTree
{
    private Tree<Model> _tree;
    private List<Model> _list; 

    [SetUp]
    public void Init()
    {
        _list = new List<Model>(8)
        {
            new Model() {ID = 1, Text = "Item 1"},
            new Model() {ID = 2, Text = "Item 2"},
            new Model() {ID = 3, Text = "Item 1.1", ParentID = 1},
            new Model() {ID = 4, Text = "Item 1.2", ParentID = 1},
            new Model() {ID = 7, Text = "Item 1.2.1", ParentID = 4},
            new Model() {ID = 5, Text = "Item 2.1", ParentID = 2},
            new Model() {ID = 6, Text = "Item 1.2.2", ParentID = 4},
            new Model() {ID = 8, Text = "Item 1.2.1.1", ParentID = 7}
        };
        _tree = new Tree<Model>(_list);
    }

    [Test]
    public void AsSameCount()
    {
        Assert.AreEqual(_list.Count, _tree.Count());
    }

    [Test]
    public void HasParentElements()
    {
        var parents = _tree.Children;
        Assert.AreEqual(2, parents.Count());
        Assert.AreEqual(3, parents.Sum(p => p.Item.ID));
    }

    [Test]
    public void HasChildren()
    {
        var children = _tree.Children.SelectMany(t => t.Children);
        Assert.AreEqual(3, children.Count());
        Assert.AreEqual(12, children.Sum(p => p.Item.ID));

        children = children.SelectMany(t => t.Children);
        Assert.AreEqual(2, children.Count());
        Assert.AreEqual(13, children.Sum(p => p.Item.ID));
    }

    [Test]
    public void TestAdd()
    {
        _tree = new Tree<Model>();
        foreach (var item in _list)
        {
            _tree.Add(item);
        }
        AsSameCount();
        HasParentElements();
        HasChildren();
    }

    [Test]
    public void TestRemoveAll()
    {
        foreach (var item in _list)
        {
            _tree.Remove(item);
        }
        Assert.AreEqual(0, _tree.Count());
    }

    [Test]
    public void TestRemoveLast()
    {
        var last = _list.Last();
        var removed = _tree.Remove(last);
        Assert.AreEqual(1, removed.Count());
        Assert.AreSame(removed.FirstOrDefault(), last);
    }

    [Test]
    public void TestRemoveItemAndChildren()
    {
        var item = _list[3];
        Assert.IsTrue(_tree.RemoveItemAndChildren(item));
        Assert.AreEqual(_list.Count - 4, _tree.Count());
    }
}

4.接受您可能对此实现的任何批评。

Answer 1

family类并不那么有用，实际上它可能有点混淆了逻辑，因为现在我们不知道将方法放在哪个类中。如果我们总是使用family类来支持每个方法，并使每个树方法只是简单地实例化一个family对象并调用相应的方法，这听起来很愚蠢，但是按照我的方法，这将是实现退化的原因。这就是说，family类很容易被一个辅助方法替换。

private bool RemoveItemAndChildren(Tree<T> parent, T item)
{
    if (parent._items.Remove(item.Key))
    {
        item.ParentKey = null;
        return true;
    }
    return false;
}

public bool RemoveItemAndChildren(T item)
{
    return RemoveItemAndChildren(Parent(item), item);
}

public bool RemoveItemAndChildren(T item, int level)
{
    return RemoveItemAndChildren(Parent(item, level), item);
}

这样就不再需要family类了。我还应该将相同的逻辑应用到remove方法中，因为那里有一些重复的代码。

private IEnumerable<T> Remove(Tree<T> parent, T item)
{
    var children = parent._items[item.Key].Children;
    parent._items.Remove(item.Key);
    item.ParentKey = null;
    yield return item;
    foreach (var child in children)
    {
        parent._items.Add(child.Item.Key, child);
        child.Item.ParentKey = item.ParentKey;
        yield return child.Item;
    }
} 

public IEnumerable<T> Remove(T item)
{
    return Remove(Parent(item), item).ToList();
}

public IEnumerable<T> Remove(T item, int level)
{
    return Remove(Parent(item, level), item).ToList();
}

再次回到我的树上，因为我再次需要它。我可以看到两个进一步改进的空间。

为了解决@ChrisWue提供的第4点，我想拥有一个bool AutoUpdateParentKeyOnRemove属性，这样用户就可以指定所需的行为。不过，我仍然同意，最好的选择是根本不更新对象参数状态。

在实现在它们上接收int level的方法时，我考虑到了性能(尽管我从未将它们与没有参数的版本进行比较)。回顾过去，我想我可以在树的派生实现上支持它们，这样我就不会用很少使用的方法来污染公共API。我想常见的用例应该只是检索一个条目，而不知道树的哪个级别。