Я пытался решить один вопрос с интервью, но для этого мне нужно пройти уровень двоичного дерева по уровню. Я разработал BinaryNode со значением ниже переменной
private object data;
private BinaryNode left;
private BinaryNode right;
Может ли кто-нибудь помочь написать метод BreadthFirstSearch внутри моего класса BinarySearchTree?
Обновление: Спасибо всем за ваш вклад. Так что это был вопрос интервью. "Учитывая двоичное дерево поиска, создайте алгоритм, который создает связанный список всех узлов на каждой глубине (т.е. Если у вас есть дерево с глубиной D, у вас есть D связанных списков)".
Вот мой метод, дайте мне знать ваш экспертный комментарий.
public List<LinkedList<BNode>> FindLevelLinkList(BNode root)
{
Queue<BNode> q = new Queue<BNode>();
// List of all nodes starting from root.
List<BNode> list = new List<BNode>();
q.Enqueue(root);
while (q.Count > 0)
{
BNode current = q.Dequeue();
if (current == null)
continue;
q.Enqueue(current.Left);
q.Enqueue(current.Right);
list.Add(current);
}
// Add tree nodes of same depth into individual LinkedList. Then add all LinkedList into a List
LinkedList<BNode> LL = new LinkedList<BNode>();
List<LinkedList<BNode>> result = new List<LinkedList<BNode>>();
LL.AddLast(root);
int currentDepth = 0;
foreach (BNode node in list)
{
if (node != root)
{
if (node.Depth == currentDepth)
{
LL.AddLast(node);
}
else
{
result.Add(LL);
LL = new LinkedList<BNode>();
LL.AddLast(node);
currentDepth++;
}
}
}
// Add the last linkedlist
result.Add(LL);
return result;
}