כתוב פעולה המקבלת עץ בינארי ומחזירה רשימה של הערכים במסלול הארוך ביותר שקיים בעץ.
פתרון עובד ב java:
import Data_Structures.BinNode;
import Data_Structures.Node;
public class test {
public static int size (BinNode <Integer> bin) {
if (bin == null)
return 0;
return 1 + Math.max(size (bin.getLeft()), size(bin.getRight()));
}
public static Node<Integer> max (BinNode <Integer> head) {
if (head == null)
return null;
Node<Integer> curr = new Node<>(head.getValue());
if (!head.hasLeft() && !head.hasRight())
return curr;
if (size (head.getRight()) > size(head.getLeft())) {
curr.setNext(max(head.getRight()));
}
else
curr.setNext(max(head.getLeft()));
return curr;
}
}
פתרונות לא בשלים:
פתרון בשפת C#
ראשית נבנה פונקציית עזר אשר בודקת מהו אורך הרשימה
public static int size(Node<int> lst)
{
Node<int> p = lst;
int counter=0;
while(p!=null)
{
counter++
p=p.GetNext();
}
return counter;
}
שנית נבנה פונקציית עזר נוספת אשר מוסיפה ערך מהסוף ומחזירה את ראש הרשימה תוך כדי שכפול הרשימה.
public static Node<int> insert(Node<int> lst , int x)
{
Node<int> newNode = new Node<int>(x, null);
Node<int> p = lst;
if(p==null)
return newNode; //the new head of the list
Node<int> newList = new Node<int>(p.GetValue());
Node<int> p2= newList;
while(p.HasNext()) // נגיע לאיבר האחרון
{
Node<int>
p=p.GetNext();
}
p.SetNext(newNode);
return lst;
}
עכשיו נכתוב את הפונקיה העיקרית
public static Node<int> MaxList(BinNode<int> t)
{
}
public static Node<int> MaxList(BinNode<int> t,Node<int> lst)
{
if(t==null)
return lst;
}
פתרון שדורש שיפוץ:
import Data_Structures.BinNode;
import Data_Structures.Node;
public class test {
public static int size (BinNode <Integer> bin) {
if (bin == null)
return 0;
return 1 + Math.max(size (bin.getLeft()), size(bin.getRight()));
}
public static Node<Integer> max (BinNode <Integer> head, Node <Integer> curr) {
if (!head.hasLeft() && !head.hasRight())
return curr;
if (size (head.getRight()) > size(head.getLeft()))
curr.setNext(max(head.getRight(), curr));
else
curr.setNext(max(head.getLeft(), curr));
return curr;
}
}