Class BinTreeUtils

java.lang.Object
  extended by unit4.utilsLib.BinTreeUtils

public final class BinTreeUtils
extends java.lang.Object

מחלקת שירות המכילה אוסף פעולות סטטיות שימושיות בעבודה עם עץ בינרי

Version:
10/2/2007
Author:
צוות מדעי המחשב, המרכז להוראת המדעים, האוניברסיטה העברית, ירושלים

Method Summary
static BinTree<String> buildExpressionTree(String exp)
          
הפעולה יוצרת ומחזירה עץ ביטוי חשבוני
static BinTree<Integer> buildRandomTree(int maxNodes, int low, int high)
          
הפעולה יוצרת ומחזירה עץ בינרי אקראי עם ערכים מספריים אקראיים
static BinTree<?> clone(BinTree<?> tree)
          
הפעולה מחזירה עץ בינרי חדש שהוא העתק מדוייק (שכפול) של העץ שהתקבל
static boolean exists(BinTree<Integer> tree, int x)
          
הפעולה שבודקת האם ערך מסויים נמצא בעץ
static int height(BinTree<?> tree)
          
פעולה המחזירה את גובה העץ (עץ עלה גובהו 0)
static String inOrderTraversal(BinTree<?> tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תוכי
static boolean isAllPositive(BinTree<Integer> tree)
          
הפעולה שבודקת האם כל הצמתים בעץ חיוביים
static boolean isFull(BinTree<?> tree)
          
הפעולה בודקת האם העץ מלא
static boolean isLeaf(BinTree<?> tree)
          
הפעולה שבודקת האם העץ שמתקבל הוא עץ עלה
static String levelOrderTraversal(BinTree<?> tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ לפי רמות
static int max(BinTree<Integer> tree)
          
הפעולה מחזירה את הערך הגדול ביותר בעץ בינרי של מספרים שלמים
static int numOfLeaves(BinTree<?> tree)
          
הפעולה מחזירה את מספר העלים בעץ
static int numOfNodes(BinTree<?> tree)
          
הפעולה מחזירה את מספר הצמתים בעץ
static BinTree<?> parent(BinTree<?> tree, BinTree<?> childe)
          
הפעולה מחזירה את ההורה של צומת מסוים בעץ; במידה והצומת הוא שורש העץ יוחר null
static String postOrderTraversal(BinTree<?> tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר סופי
static String preOrderTraversal(BinTree<?> tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תחילי
static void showTree(BinTree<?> tree, String... title)
          
הפעולה מציגה את הבינרי המתקבל בצורה גרפית
static int sumOfNodes(BinTree<Integer> tree)
          
הפעולה מחזירה את סכום הצמתים בעץ בינרי של מספרים שלמים
static int sumOfNodesInLevel(BinTree<Integer> tree, int level)
          
הפעולה מחזירה את סכום הצמתים ברמה מסויימת בעץ בינרי של מספרים שלמים
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

showTree

public static void showTree(BinTree<?> tree, String... title)
הפעולה מציגה את הבינרי המתקבל בצורה גרפית

Parameters:
tree - עץ בינרי גנרי
title - פרמטר אופציונאלי: כותרת החלון בו יוצג העץ הבינרי

buildExpressionTree

public static BinTree<String> buildExpressionTree(String exp)
הפעולה יוצרת ומחזירה עץ ביטוי חשבוני

Parameters:
exp - מחרוזת המייצגת ביטוי חשבוני תקין
Returns:
עץ ביטוי חשבוני

buildRandomTree

public static BinTree<Integer> buildRandomTree(int maxNodes, int low, int high)
הפעולה יוצרת ומחזירה עץ בינרי אקראי עם ערכים מספריים אקראיים

Parameters:
maxNodes - מספר צמתים מקסימלי
low - ערך מינימלי שיכול להיות בעץ
high - ערך מקסימלי שיכול להיות בעץ
Returns:
עץ בינרי עם ערכים אקראיים

preOrderTraversal

public static String preOrderTraversal(BinTree<?> tree)
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תחילי

Parameters:
tree - עץ בינרי גנרי
Returns:
מחרוזת המתארת את סריקת העץ בסדר תחילי

inOrderTraversal

public static String inOrderTraversal(BinTree<?> tree)
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תוכי

Parameters:
tree - עץ בינרי גנרי
Returns:
מחרוזת המתארת את סריקת העץ בסדר תוכי

postOrderTraversal

public static String postOrderTraversal(BinTree<?> tree)
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר סופי

Parameters:
tree - עץ בינרי גנרי
Returns:
מחרוזת המתארת את סריקת העץ בסדר סופי

levelOrderTraversal

public static String levelOrderTraversal(BinTree<?> tree)
פעולה המחזירה מחרוזת המתארת את סריקת העץ לפי רמות

Parameters:
tree - עץ בינרי גנרי
Returns:
מחרוזת המתארת את סריקת העץ לפי רמות

height

public static int height(BinTree<?> tree)
פעולה המחזירה את גובה העץ (עץ עלה גובהו 0)

Parameters:
tree - עץ בינרי גנרי
Returns:
גובה העץ

numOfNodes

public static int numOfNodes(BinTree<?> tree)
הפעולה מחזירה את מספר הצמתים בעץ

Parameters:
tree - עץ בינרי גנרי
Returns:
מספר הצמתים בעץ

clone

public static BinTree<?> clone(BinTree<?> tree)
הפעולה מחזירה עץ בינרי חדש שהוא העתק מדוייק (שכפול) של העץ שהתקבל

Parameters:
tree - עץ בינרי גנרי
Returns:
עץ בינרי

isFull

public static boolean isFull(BinTree<?> tree)
הפעולה בודקת האם העץ מלא

Parameters:
tree - עץ בינרי גנרי
Returns:
הפעולה מחזירה 'אמת' אם העץ מלא, ו'שקר' אחרת

max

public static int max(BinTree<Integer> tree)
הפעולה מחזירה את הערך הגדול ביותר בעץ בינרי של מספרים שלמים

Parameters:
tree - עץ בינרי של מספרים שלמים
Returns:
הערך הגדול ביותר בעץ

sumOfNodes

public static int sumOfNodes(BinTree<Integer> tree)
הפעולה מחזירה את סכום הצמתים בעץ בינרי של מספרים שלמים

Parameters:
tree - עץ בינרי של מספרים שלמים
Returns:
סכום כל ערכי הצמתים בעץ

sumOfNodesInLevel

public static int sumOfNodesInLevel(BinTree<Integer> tree, int level)
הפעולה מחזירה את סכום הצמתים ברמה מסויימת בעץ בינרי של מספרים שלמים

Parameters:
tree - עץ בינרי של מספרים שלמים
level - רמה בעץ(מספר גדול או שווה לאפס)
Returns:
סכום הצמתים ברמה מסויימת בעץ

isAllPositive

public static boolean isAllPositive(BinTree<Integer> tree)
הפעולה שבודקת האם כל הצמתים בעץ חיוביים

Parameters:
tree - עץ בינרי של מספרים שלמים
Returns:
המחזירה 'אמת' אם כל הצמתים בעץ חיוביים, ו'שקר' אחרת

exists

public static boolean exists(BinTree<Integer> tree, int x)
הפעולה שבודקת האם ערך מסויים נמצא בעץ

Parameters:
tree - עץ בינרי של מספרים שלמים
x - ערך לחיפוש
Returns:
הפעולה מחזירה 'אמת' אם הערך המתקבל נמצא בעץ, ו'שקר' אחרת

isLeaf

public static boolean isLeaf(BinTree<?> tree)
הפעולה שבודקת האם העץ שמתקבל הוא עץ עלה

Parameters:
tree - עץ בינרי גנרי
Returns:
הפעולה מחזירה 'אמת' אם העץ הוא עץ עלה, ו'שקר' אחרת

numOfLeaves

public static int numOfLeaves(BinTree<?> tree)
הפעולה מחזירה את מספר העלים בעץ

Parameters:
tree - עץ בינרי גנרי
Returns:
מספר העלים בעץ

parent

public static BinTree<?> parent(BinTree<?> tree, BinTree<?> childe)
הפעולה מחזירה את ההורה של צומת מסוים בעץ; במידה והצומת הוא שורש העץ יוחר null

Parameters:
tree - עץ בינרי גנרי
childe - הפנייה לצומת בעץ
Returns:
הפנייה לשורש העץ שהוא הורה