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 buildRandomTree(int maxNodes, int low, int high)
          
הפעולה יוצרת ומחזירה עץ בינרי אקראי עם ערכים מספריים אקראיים
static BinTree clone(BinTree tree)
          
הפעולה מחזירה עץ בינרי חדש שהוא העתק מדוייק (שכפול) של העץ שהתקבל
static boolean exists(BinTree tree, int x)
          
הפעולה שבודקת האם ערך מסויים נמצא בעץ
static int height(BinTree tree)
          
פעולה המחזירה את גובה העץ (עץ עלה גובהו 0)
static String inOrderTraversal(BinTree tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תוכי
static boolean isAllPositive(BinTree tree)
          
הפעולה שבודקת האם כל הצמתים בעץ חיוביים
static boolean isFull(BinTree tree)
          
הפעולה בודקת האם העץ מלא
static boolean isLeaf(BinTree tree)
          
הפעולה שבודקת האם העץ שמתקבל הוא עץ עלה
static String levelOrderTraversal(BinTree tree)
          
פעולה המחזירה מחרוזת המתארת את סריקת העץ לפי רמות
static int max(BinTree 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 tree)
          
הפעולה מחזירה את סכום הצמתים בעץ בינרי של מספרים שלמים
static int sumOfNodesInLevel(BinTree 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 - פרמטר אופציונאלי: כותרת החלון בו יוצג העץ הבינרי

buildRandomTree

public static BinTree 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 tree)
הפעולה מחזירה את הערך הגדול ביותר בעץ בינרי של מספרים שלמים

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

sumOfNodes

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

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

sumOfNodesInLevel

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

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

isAllPositive

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

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

exists

public static boolean exists(BinTree 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:
הפנייה לשורש העץ שהוא הורה