Деревья

Доброго времени суток. Балуюсь с деревьями. Написал функцию (FindNode), которая возвращает узел, содержащий элемент, ключ которого задан, но она в некоторых случаях не работает :-(Определение дерева
using System;using System.IO;using System.Text;using System.Collections.Generic;using System.Collections.Specialized;namespace Tree{    struct BranchKey /* Ключ узла дерева */    {        public string currentName;        public string parentName;        public BranchKey(string currentName, string parentName)        {            this.currentName = currentName;            this.parentName = parentName;        }    }    sealed class BranchNode /* Узел дерева */    {        private Dictionary<BranchKey, BranchNode> node; // узел: уникальный ключ, список узлов-потомков                 public BranchNode() // создание пустого узла (0 элементов)        {            this.node = new Dictionary<BranchKey, BranchNode>();        }        public BranchNode(BranchKey key) // создание элемента в узле, содержащего ключ и пустой подузел        {            this.node = new Dictionary<BranchKey, BranchNode>();            this.node.Add(key, new BranchNode());        }        public Dictionary<BranchKey, BranchNode> Node        { get { return this.node; } }        // ЭТА ФУНКЦИЯ РАБОТАЕТ НЕКОРРЕКТНО        public static BranchNode FindNode(BranchNode startNode, BranchKey findKey) // найти подузел, содержащий элемент с заданным ключом, начиная с заданного узла         {            if (startNode.node.ContainsKey(findKey))                return startNode;            if(startNode.node.Keys.Count > 0)                foreach (BranchKey key in startNode.node.Keys)                {                    BranchNode pointer = startNode.node[key];                    return FindNode(pointer, findKey);                }            return null;        }        public bool AddSubkeys(BranchKey key, params string[] subkeys) // добавление элементов в подузел элемента с заданным ключом в текущем узле        {            if (this.node.ContainsKey(key))            {                foreach (string subkey in subkeys)                    this.node[key].node.Add(new BranchKey(subkey, key.currentName), new BranchNode());                return true;            }            else                return false;        }        public void PrintNode(BranchKey key, int ind) // печать элемента, заданного ключом, в текущем узле и подузла этого элемента        {            if (this.node.ContainsKey(key))            {                PrintValue(key.currentName, ind);                BranchNode pointer = this.node[key]; // подузел элемента с ключом "key"                if (pointer.node.Keys.Count > 0) // если в подузле есть элементы                {                    foreach (BranchKey subKey in pointer.node.Keys)                    {                        ind += 3;                        pointer.PrintNode(subKey, ind);                        ind -= 3;                    }                }            }            else                Console.WriteLine("Error: Node doesn't contain this key");        }         private void PrintValue(string value, int n) // печать пробелов и значения        {            for (int i = 0; i < n; i++)                Console.Write("-");            Console.Write("> {0}\n", value);        }    }}
А вот тут использую своё дерево:
class Program    {        static void Main(string[] args)        {            BranchKey firstKey = new BranchKey("GraphmatTick.cpp", null);            BranchKey secondKey1 = new BranchKey("util_classes.h", "GraphmatTick.cpp");            BranchKey secondKey2 = new BranchKey("GraphmatFile.h", "GraphmatTick.cpp");            BranchKey thirdKey1 = new BranchKey("utilit.h", "util_classes.h");            BranchKey thirdKey2 = new BranchKey("UnitHolder.h", "GraphmatFile.h");            BranchKey fourthKey1 = new BranchKey("graline.h", "UnitHolder.h");                        BranchKey fiveKey1 = new BranchKey("utilit.h", "graline.h");            BranchNode tree = new BranchNode(firstKey); // корневой узел с элементом с ключом 'firstKey'            tree.AddSubkeys(firstKey, secondKey1.currentName, secondKey2.currentName);            BranchNode treeItem1 = tree.Node[firstKey]; // подузел из элемента с ключом 'firstKey'            treeItem1.AddSubkeys(secondKey1, thirdKey1.currentName);            treeItem1.AddSubkeys(secondKey2, thirdKey2.currentName);                        BranchNode treeSubItem2 = treeItem1.Node[secondKey2]; // подузел из элемента с ключом 'secondKey2'            treeSubItem2.AddSubkeys(thirdKey2, fourthKey1.currentName);            BranchNode treeSubSubItem1 = treeSubItem2.Node[thirdKey2]; // подузел из элемента с ключом 'thirdKey2'            treeSubSubItem1.AddSubkeys(fourthKey1, fiveKey1.currentName);            // Для ключей secondKey1, secondKey1, thirdKey1 метод работает нормально           //  Для ключей thirdKey2, fourthKey1, fiveKey1 метод не возвращает нужное значение           // Иерархия элементов с ключами:           //    secondKey1->thirdKey1          //     secondKey1->thirdKey2->fourthKey1->fiveKey1            BranchNode pointer = BranchNode.FindNode(tree, fiveKey1);            pointer.PrintNode(fiveKey1, 1);            Console.Write("\nPress any key to continue . . . ");            Console.ReadLine();        }    }
4 ответа

У тебя иерархия файлов должна повторять иерархиютвоего дерева? Потому что она у тебя разная. utilit.h имеет два предка:  BranchKey thirdKey1 = new BranchKey("utilit.h", "util_classes.h");BranchKey fiveKey1 = new BranchKey("utilit.h", "graline.h"); Если да, то такой хитропопой реализации я еще не видел.По поводу ошибки. Ты действительно неправильно ищеш. 
// ЭТА ФУНКЦИЯ РАБОТАЕТ НЕКОРРЕКТНО        public static BranchNode FindNode(BranchNode startNode, BranchKey findKey) // найти подузел, содержащий элемент с заданным ключом, начиная с заданного узла         {            if (startNode.node.ContainsKey(findKey))                return startNode;            if(startNode.node.Keys.Count > 0)                foreach (BranchKey key in startNode.node.Keys)                {                    BranchNode pointer = startNode.node[key];                    return FindNode(pointer, findKey);                }            return null; /[color=orangered]/Сдесь нельзя писать return null, потому что оно у тебя отбрываеться на первой ветке дерева (короткой).[/color]        }


Уникальный ключ для каждого элемента в узле состоит из двух значений: собственного и имени ключа элемента, расположенного на один узел выше.


Вот модифицированный метод. // ЭТА ФУНКЦИЯ РАБОТАЕТ КОРРЕКТНО        public static List FindNode(BranchNode startNode, BranchKey findKey) // найти подузел, содержащий элемент с заданным ключом, начиная с заданного узла         {            List _branchNodes = new List();            if (startNode.node.ContainsKey(findKey))            {                _branchNodes.Add(startNode);                return _branchNodes;            }            if (startNode.node.Keys.Count > 0)                foreach (BranchKey key in startNode.node.Keys)                {                    BranchNode pointer = startNode.node[key];                    _branchNodes.AddRange(FindNode(pointer, findKey));                }            return _branchNodes;        }Модифицировать главную функцию так/ Для ключей secondKey1, secondKey1, thirdKey1 метод работает нормально        //  Для ключей thirdKey2, fourthKey1, fiveKey1 метод не возвращает нужное значение        // Иерархия элементов с ключами:        //    secondKey1->thirdKey1        //     secondKey1->thirdKey2->fourthKey1->fiveKey1        List pointer = BranchNode.FindNode(tree, fiveKey1);        pointer[0].PrintNode(fiveKey1, 1);Мой совет. Подебаж и посмотри как рекурсия пробегает дерево. Ты не совсем понимаеш принцип ёё работы. Тебе будет очень полезно.PS: Само собой если даже елемент найдеться раньше чем дерево окончиться, дерево все равно будет перебираться до самого конца. Думаю втулить умную проверку сможеш сам.


Вот как раз только что, пройдясь дебаггером, заметил, что функция обрывается на первой ветке (содержащей элемент с ключом secondKey1), а в другую, более "длинную", не заходит. Сейчас буду разбираться Добавлено через 6 минут и 43 секундыБольшое спасибо за подсказку!!