Skip to content

Instantly share code, notes, and snippets.

@EgoPingvina
Created July 31, 2020 09:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save EgoPingvina/692644f25b6c79da37d2b7f3c8da269c to your computer and use it in GitHub Desktop.
Save EgoPingvina/692644f25b6c79da37d2b7f3c8da269c to your computer and use it in GitHub Desktop.
c# truncate the tree, keeping the specified number of nodes
public Node TruncateByTraverseBF(Node root,int count)
{
if (count <= 0)
return null;
if (count == 1)
{
root.Children.Clear();
return root;
}
var queue = new Queue<Node>();
queue.Enqueue(root);
var currentLength = 1;
int i = 0;
while (queue.TryDequeue(out Node subTree))
{
for (i = 0; i < subTree.Children.Count && currentLength < count; i++, currentLength++)
queue.Enqueue(
subTree.Children[i]);
if (currentLength >= count)
{
subTree.Children.RemoveRange(i, subTree.Children.Count - i);
break;
}
}
while (queue.TryDequeue(out Node subTree))
subTree.Children.Clear();
return root;
}
/*
* Example
*/
/31-41 /31
/21-32 /21
TruncateByTraverseBF(1-22-33 , 5) = 1-22
\23 \23
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment