0

我有一个使用多个键的树搜索算法，每个节点都有一个子树，用键列表中的下一个键搜索该子树，直到键用完并且正在搜索的数据位于该端节点中。

我的代码正在运行，但我不知道该怎么称呼它。在我阅读 Wicki 页面之前，我认为它是一棵三叉树，但似乎并非如此。所以我只是不知道该怎么称呼它。

这是我的课。像二叉树一样工作，对键的数量没有限制，其中键集作为列表发送到搜索/插入函数。每次一个键找到一个节点时，下一个键就会从列表中删除，并且该节点的“下一个键树”重复该过程，直到它用完键并发回数据。我的想法是我可以用它来标记“名字”、“第二名”、“职业”、“城市”等类别的精确搜索。它们以相同的顺序输入，并且可以遍历任何子树。仍然不确定这比字符串的常规二叉树好多少。我有另一个精确的版本，它有可能更方便的整数键。


public class classTernaryTree_StringKey
{
    classTernaryTree_StringKey_Node cRoot = null;

    public void Insert(ref object data, List<string> lstKeys)
    {
        classTernaryTree_StringKey cMyRef = this;
        _Insert(ref cMyRef, ref data, lstKeys);

    }

    static void _Insert(ref classTernaryTree_StringKey cTree, ref object data, List<string> lstKeys)
    {

        if (cTree.cRoot == null)
        {
            cTree.cRoot = new classTernaryTree_StringKey_Node();
            cTree.cRoot.key = lstKeys[0];
            lstKeys.RemoveAt(0);
            if (lstKeys.Count > 0)
            {
                cTree.cRoot.NextTree.Insert(ref data, lstKeys);
                return;
            }
            else
            {
                cTree.cRoot.data = data;
                return;
            }
        }

        classTernaryTree_StringKey_Node cNode = cTree.cRoot;
        do
        {
            int intComparison = string.Compare(lstKeys[0], cNode.key);
            if (intComparison > 0)
            {
                if (cNode.Right != null)
                    cNode = cNode.Right;
                else
                {
                    cNode.Right = new classTernaryTree_StringKey_Node();
                    cNode.Right.key = lstKeys[0];
                    lstKeys.RemoveAt(0);

                    if (lstKeys.Count > 0)
                    {
                        cNode.Right.NextTree.Insert(ref data, lstKeys);
                        return;
                    }
                    else
                    {
                        cNode.Right.data = data;
                        return;
                    }
                }
            }
            else if (intComparison < 0)
            {
                if (cNode.Left != null)
                    cNode = cNode.Left;
                else
                {
                    cNode.Left = new classTernaryTree_StringKey_Node();
                    cNode.Left.key = lstKeys[0];
                    lstKeys.RemoveAt(0);

                    if (lstKeys.Count > 0)
                    {
                        cNode.Left.NextTree.Insert(ref data, lstKeys);
                        return;
                    }
                    else
                    {
                        cNode.Left.data = data;
                        return;
                    }
                }
            }
            else
            {
                lstKeys.RemoveAt(0);
                if (lstKeys.Count > 0)
                {
                    cNode.NextTree.Insert(ref data, lstKeys);
                    return;
                }
                else
                {
                    cNode.data = data;
                    return;
                }
            }

        } while (true);
    }


    public object Search(List<string> lstKeys)
    {
        classTernaryTree_StringKey cMyRef = this;
        return _Search(ref cMyRef, lstKeys);
    }

    static object _Search(ref classTernaryTree_StringKey cTree, List<string> lstKeys)
    {

        if (cTree.cRoot == null) return null;
        classTernaryTree_StringKey_Node cNode = cTree.cRoot;
        do
        {
            int intComparison = string.Compare(lstKeys[0], cNode.key);
            if (intComparison > 0)
            {
                if (cNode.Right != null)
                    cNode = cNode.Right;
                else
                    return null;
            }
            else if (intComparison < 0)
            {
                if (cNode.Left != null)
                    cNode = cNode.Left;
                else
                    return null;
            }
            else
            {
                lstKeys.RemoveAt(0);
                if (lstKeys.Count > 0)
                    return cNode.NextTree.Search(lstKeys);
                else
                    return cNode.data;
            }
        } while (true);
    }

}

public class classTernaryTree_StringKey_Node
{
    public string key = "";
    public classTernaryTree_StringKey_Node Left = null;
    public classTernaryTree_StringKey_Node Right = null;
    public classTernaryTree_StringKey NextTree = new classTernaryTree_StringKey();
    public object data = null;
}
4

1 回答 1

0

您在此处拥有的数据结构实际上看起来非常类似于三元搜索树，只是用字符串标记节点而不是单个字符。

三元搜索树是一种对trie数据结构进行编码的方法。尝试是表示元素序列的树。通常，这些元素是单独的字符，但原则上它们可以是任何东西。您的数据结构本质上是一个三元搜索树，您在其中存储字符串而不是每个节点的字符。

于 2020-04-14T20:26:23.360 回答