汇总所有节点
本文关键字:节点 | 更新日期: 2023-09-27 17:48:52
这可能是一个简单的修复方法,但我正在尝试将二进制搜索树上的所有节点(Node类中的Size属性)相加。到目前为止,在我的BST类中,我有以下内容,但它返回0:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return 0;
if (node.Right == null)
return sum(thisNode.Left);
if (node.Left == null)
return sum(thisNode.Right);
return sum(thisNode.Left) + sum(thisNode.Right);
}
在我的Node类中,我有Data,它将Size和Name存储在它们给定的属性中。我只是想把整个尺寸加起来。有什么建议或想法吗?
这是因为当到达叶节点时返回零。您应该返回存储在该叶节点中的大小。
此外,如果你的非叶节点也有一个大小,你也需要处理它们,因此:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
if (node.Right == null)
return thisNode.Size + sum(thisNode.Left);
if (node.Left == null)
return thisNode.Size + sum(thisNode.Right);
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
如果您的非叶节点没有大小,请使用:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
if (node.Right == null)
return sum(thisNode.Left);
if (node.Left == null)
return sum(thisNode.Right);
return sum(thisNode.Left) + sum(thisNode.Right);
}
第一个更优雅的版本是:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
也许你指的是
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
试试这个:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
原始代码返回的唯一"值"是0,这就是为什么结果总是0。
怎么样
private long Sum(Node<T> thisNode)
{
if( thisNode == null )
return 0;
return thisNode.Size + Sum(thisNode.Left) + Sum(thisNode.Right);
}
如果size属性不在节点本身上,该怎么办?
public class Node<T>
{
public T Data;
public Node<T> Left;
public Node<T> Right;
public static void ForEach(Node<T> root, Action<T> action)
{
action(root.Data);
if (root.Left != null)
ForEach(root.Left, action);
if (root.Right != null)
ForEach(root.Right, action);
}
}
public interface IHasSize
{
long Size { get; }
}
public static long SumSize<T>(Node<T> root) where T : IHasSize
{
long sum = 0;
Node<T>.ForEach(root, delegate(T item)
{
sum += item.Size;
});
return sum;
}