遍历复杂的树结构

本文关键字：结构 复杂 遍历 | 更新日期: 2023-09-27 18:25:46

我有一个这样的树结构：

A (20,40)
    B (21,22)
    C (23,33)
        D (24,29)
            E (25,26)
            F (27,28)
        G (30,31)
        H (32,33)
    I (34,37)
        J(35,36)
    K (38,39)

级别可能很深，所以我需要使用递归。如何找到给定节点的子节点及其级别值（例如，"B"将为级别2）？

我很纠结于这个问题，但到目前为止我的伪代码大致是这样的：

传入一个节点-->，如果其左值和右值之差>1，则使用左值+1 查找下一个子节点

遍历复杂的树结构

有很多方法可以做到这一点！看看树遍历的想法。

从您的示例来看，似乎每个节点上都有一些应该使用的范围。

只是为了好玩，我尝试（非常快速）构建一些代码——同样，这是在不知道搜索中使用什么参数的情况下完成的。请注意，这只是一个例子，构建得非常快：

节点结构

class Node
{
    public int Min { get; set; }
    public int Max { get; set; }
    public List<Node> Children { get; set; }
    public Node(int min, int max)
    {
        this.Min = min;
        this.Max = max;
        this.Children = new List<Node>();
    }
    public void Add(Node child)
    {
        this.Children.Add(child);
    }
}

主要类别

该类包含一个用于构建树的函数（不漂亮），以及一个递归函数，该函数返回leve并输出节点对象。

class Program
{
    static void Main(string[] args)
    {
        var tree = GetTree();
        Node node;
        var val = Find(tree, 21, 1, out node);
        Console.WriteLine("depth: {0}", val);
        Console.WriteLine("'t{0}, {1}", node.Min, node.Max);
        Console.ReadKey();
    }
    private static int Find(Node curNode, int value, int level, out Node foundNode)
    {
        foundNode = curNode;
        foreach (var child in curNode.Children)
        {
            if (child.Min <= value && child.Max >= value)
                return Find(child, value, level + 1, out foundNode);
        }
        return level;
    }
    private static Node GetTree()
    {
        var a = new Node(20, 40);
        var b = new Node(21, 22);
        var c = new Node(23, 33);
        var d = new Node(24, 29);
        var e = new Node(25, 26);
        var f = new Node(27, 28);
        var g = new Node(30, 31);
        var h = new Node(32, 33);
        var i = new Node(34, 37);
        var j = new Node(35, 36);
        var k = new Node(38, 39);
        d.Add(e);
        d.Add(f);
        c.Add(d);
        c.Add(g);
        c.Add(h);
        i.Add(j);
        a.Add(b);
        a.Add(c);
        a.Add(i);
        a.Add(k);
        return a;
    }
}
private static Node GetTree()
{
    var a = new Node(20, 40);
    var b = new Node(21, 22);
    var c = new Node(23, 33);
    var d = new Node(24, 29);
    var e = new Node(25, 26);
    var f = new Node(27, 28);
    var g = new Node(30, 31);
    var h = new Node(32, 33);
    var i = new Node(34, 37);
    var j = new Node(35, 36);
    var k = new Node(38, 39);
    d.Add(e);
    d.Add(f);
    c.Add(d);
    c.Add(g);
    c.Add(h);
    i.Add(j);
    a.Add(b);
    a.Add(c);
    a.Add(i);
    a.Add(k);
    return a;
}

您总是可以使用正则表达式，对吧？：）

您可以为此进行全局匹配：

([    ]+)([A-Z]+) '('d+,'d+')

并计算这四个空格重复了多少次，这基本上就是字母的级别。

如果要存储实际的树，还必须记录父节点。

相关文章：