c# - 如何找到树中的下一个节点?
问题描述
问题是这样的:
我们有一个使用类 Node 构建的树,其中类的实例表示树中的一个节点。为简单起见,该节点具有单个 int 类型的数据字段。您的任务是编写扩展方法 NodeExtensions.Next() 来查找树中的下一个元素。您可以编写任意数量的辅助方法,但不要更改扩展方法 NodeExtensions.Next() 的签名。
我有这个节点类:
public class Node
{
private List<Node> _children;
public Node(int data, params Node[] nodes)
{
Data = data;
AddRange(nodes);
}
public Node Parent { get; set; }
public IEnumerable<Node> Children
{
get
{
return _children != null
? _children
: Enumerable.Empty<Node>();
}
}
public int Data { get; private set; }
public void Add(Node node)
{
Debug.Assert(node.Parent == null);
if (_children == null)
{
_children = new List<Node>();
}
_children.Add(node);
node.Parent = this;
}
public void AddRange(IEnumerable<Node> nodes)
{
foreach (var node in nodes)
{
Add(node);
}
}
public override string ToString()
{
return Data.ToString();
}
}
解决方案应该是这样的扩展方法
public static Node Next(this Node node)
{
}
我试过的代码:
public static Node Next(this Node node)
{
var newNode = NextLargerElement(node, node.Data);
return newNode;
}
public static Node res;
public static Node NextLargerElementUtil(Node root, int x)
{
if (root == null)
return null;
if (root.Data > x)
if ((res == null || (res).Data > root.Data))
res = root;
foreach (var children in root.Children)
{
NextLargerElementUtil(children, x);
}
return res;
}
static Node NextLargerElement(Node root, int x)
{
res = null;
NextLargerElementUtil(root, x);
return res;
}
这是一个测试用例:
[Test]
public void Test()
{
// Test tree:
//
// 1
// +-2
// +-3
// +-4
// +-5
// +-6
// +-7
//
var root = new Node(
1,
new Node(
2,
new Node(3),
new Node(4)),
new Node(
5,
new Node(6),
new Node(7)));
// Expected output:
//
// 1
// 2
// 3
// 4
// 5
// 6
// 7
//
var n = root;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next();
}
// Test
//
n = root;
Assert.AreEqual(1, n.Data);
n = n.Next();
Assert.AreEqual(2, n.Data);
n = n.Next();
Assert.AreEqual(3, n.Data);
n = n.Next();
Assert.AreEqual(4, n.Data);
n = n.Next();
Assert.AreEqual(5, n.Data);
n = n.Next();
Assert.AreEqual(6, n.Data);
n = n.Next();
Assert.AreEqual(7, n.Data);
n = n.Next();
Assert.IsNull(n);
}
解决方案
您可以使用Equals
回溯当前节点在树中的位置并返回其父节点的下一个子节点(如果有),如果没有,则需要回溯当前节点父节点位置,依此类推:
public static Node Next(this Node node)
{
if(node.Children != null && node.Children.Any())
{
return node.Children.First();
}
// "backtracking", also can be done recursively
var parent = node.Parent;
while(parent != null)
{
var returnNext = false; // return next element in Children if current is node
foreach (var element in parent.Children)
{
if(returnNext)
{
return element;
}
if(element == node)
{
returnNext = true;
node = parent; // to find parent's position if there is no next child
}
}
parent = parent.Parent;
}
return null;
}
推荐阅读
- typescript - 为什么 AWS CDK Typescript 在 VPC 中创建额外的子网
- html - 是否可以传递 base64 字符串来定义 Manifest.json 中的图标?
- javascript - 如何在 jQuery 中使用 document.querySelectorAll() 来提高性能?
- python - 在 python 中,你将如何创建两个相互迭代的列?
- reactjs - React Native向PNG添加边框
- python - 如何循环一个 yaml 以创建另一个带有变量的 yaml
- javascript - 如何使用 nodemailer 和 roundcube 发送电子邮件
- apache-kafka - 针对某个主题的消费群体的紧凑展示
- enums - 在 Symfony 中为 ENUM 使用 columnDefinition 中的数组
- java - 当我收到团队的频道时,MS Graph 中的不一致