Guest User

Untitled

a guest
Jan 23rd, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.34 KB | None | 0 0
  1. private object data;
  2. private BinaryNode left;
  3. private BinaryNode right;
  4.  
  5. public List<LinkedList<BNode>> FindLevelLinkList(BNode root)
  6. {
  7. Queue<BNode> q = new Queue<BNode>();
  8. // List of all nodes starting from root.
  9. List<BNode> list = new List<BNode>();
  10. q.Enqueue(root);
  11. while (q.Count > 0)
  12. {
  13. BNode current = q.Dequeue();
  14. if (current == null)
  15. continue;
  16. q.Enqueue(current.Left);
  17. q.Enqueue(current.Right);
  18. list.Add(current);
  19. }
  20.  
  21. // Add tree nodes of same depth into individual LinkedList. Then add all LinkedList into a List
  22. LinkedList<BNode> LL = new LinkedList<BNode>();
  23. List<LinkedList<BNode>> result = new List<LinkedList<BNode>>();
  24. LL.AddLast(root);
  25. int currentDepth = 0;
  26. foreach (BNode node in list)
  27. {
  28. if (node != root)
  29. {
  30. if (node.Depth == currentDepth)
  31. {
  32. LL.AddLast(node);
  33. }
  34. else
  35. {
  36. result.Add(LL);
  37. LL = new LinkedList<BNode>();
  38. LL.AddLast(node);
  39. currentDepth++;
  40. }
  41. }
  42. }
  43.  
  44. // Add the last linkedlist
  45. result.Add(LL);
  46. return result;
  47. }
  48.  
  49. Queue<Node> q = new Queue<Node>();
  50. q.Enqueue(root);
  51. while(q.Count > 0)
  52. {
  53. Node current = q.Dequeue();
  54. if(current == null)
  55. continue;
  56. q.Enqueue(current.Left);
  57. q.Enqueue(current.Right);
  58.  
  59. DoSomething(current);
  60. }
  61.  
  62. public static IEnumerable<T> BreadthFirstTopDownTraversal<T>(T root, Func<T, IEnumerable<T>> children)
  63. {
  64. var q = new Queue<T>();
  65. q.Enqueue(root);
  66. while (q.Count > 0)
  67. {
  68. T current = q.Dequeue();
  69. yield return current;
  70. foreach (var child in children(current))
  71. q.Enqueue(child);
  72. }
  73. }
  74.  
  75. IEnumerable<Node> Children { get { return new []{ Left, Right }.Where(x => x != null); } }
  76.  
  77. foreach(var element in BreadthFirstTopDownTraversal(root, node => node.Children)
  78. {
  79. ...
  80. }
  81.  
  82. var queue = new Queue<BinaryNode>();
  83. queue.Enqueue(rootNode);
  84.  
  85. while(queue.Any())
  86. {
  87. var currentNode = queue.Dequeue();
  88. if(currentNode.data == searchedData)
  89. {
  90. break;
  91. }
  92.  
  93. if(currentNode.Left != null)
  94. queue.Enqueue(currentNode.Left);
  95.  
  96. if(currentNode.Right != null)
  97. queue.Enqueue(currentNode.Right);
  98. }
  99.  
  100. public class NodeLevel
  101. {
  102. public TreeNode Node { get; set;}
  103. public int Level { get; set;}
  104. }
  105.  
  106. public class NodeLevelList
  107. {
  108. private Dictionary<int,List<TreeNode>> finalLists = new Dictionary<int,List<TreeNode>>();
  109.  
  110. public void AddToDictionary(NodeLevel ndlvl)
  111. {
  112. if(finalLists.ContainsKey(ndlvl.Level))
  113. {
  114. finalLists[ndlvl.Level].Add(ndlvl.Node);
  115. }
  116. else
  117. {
  118. finalLists.Add(ndlvl.Level,new List<TreeNode>(){ndlvl.Node});
  119. }
  120. }
  121.  
  122. public Dictionary<int,List<TreeNode>> GetFinalList()
  123. {
  124. return finalLists;
  125. }
  126. }
  127.  
  128. public static void DFSLevel(TreeNode root, int level, NodeLevelList nodeLevelList)
  129. {
  130. if(root == null)
  131. return;
  132.  
  133. nodeLevelList.AddToDictionary(new NodeLevel{Node = root, Level = level});
  134.  
  135. level++;
  136.  
  137. DFSLevel(root.Left,level,nodeLevelList);
  138. DFSLevel(root.Right,level,nodeLevelList);
  139.  
  140. }
Add Comment
Please, Sign In to add comment