c# - 获取二叉树中节点索引的最简单方法 C#

Question

我想得到一个bst中所有节点的索引。我用来插入值和搜索节点的代码是

public class BTS
{
    public class Node
    {
        public int value;
        public Node Left;
        public Node Right;
    }


    public Node Insert(Node nod,int value)
    {
        if (nod == null)
        {
            nod = new Node();
            nod.value = value;
        }
        else if(value < nod.value)
        {
            nod.Left = Insert(nod.Left, value);
        }
        else if(value > nod.value)
        {
            nod.Right = Insert(nod.Right, value);
        }
        return nod;
    }

    public string FindNode(Node node, int s)
    {
        string Output = "";
        if (node == null)
            return Output = "not found";
        else if (s.CompareTo(node.value) < 0)
            return FindNode(node.Left, s);
        else if (s.CompareTo(node.value) > 0)
            return FindNode(node.Right, s);

        return Output = "found";
    }
    static void Main()
    {
        Node N = null;
        BTS bs = new BTS();
        N = bs.Insert(N, 10);
        N = bs.Insert(N, 9);
        N = bs.Insert(N, 8);
        N = bs.Insert(N, 11);
        N = bs.Insert(N, 12);
        bs.FindNode(N,9);
    }
}

如果节点 9 存在，上面的代码给我的值为 true。但是我想像获取数组索引一样获取节点的索引。

提前谢谢你。

Answer 1

我会尽力为您提供答案。一开始你必须把这个任务分成几个子任务:

• 我将如何索引每个元素？
  • OP 在评论中的图片中提供了答案
• 我将如何保存每个元素的索引？
  • 可能在每个元素上添加变量
  • 我们可以有一些Dictionary<Node,int>
• 我要如何分配索引？
  • 在元素添加期间
    • 将其插入变量
    • 或将其插入字典
  • 一旦我需要它，我会重新计算索引
    • 更新所有项目的所有变量
    • 更新字典中的所有项目

---

理论上的答案:然而，这两种方法都需要 add Node和 recalculate all the indexes后。您基本上需要创建遍历树中每个元素的方法，从最低值到最高值，并将其索引保存在某处。

我们可以借用那里迭代树的答案:

• How do I iterate over Binary Tree?
• 或Traversing a tree of objects in c#