unit4.utilsLib
Class BinTreeUtils

java.lang.Object
  unit4.utilsLib.BinTreeUtils

public final class BinTreeUtils
extends java.lang.Object

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

Version:

26.11.2007

Author:

צוות מדעי המחשב, המרכז להוראת המדעים, האוניברסיטה העברית, ירושלים

Method Summary

static BinTreeNode<java.lang.String>	buildExpressionTree(java.lang.String exp) הפעולה יוצרת ומחזירה עץ ביטוי חשבוני
static BinTreeNode<java.lang.Integer>	buildRandomTree(int maxNodes, int low, int high) הפעולה יוצרת ומחזירה עץ בינרי אקראי עם ערכים מספריים אקראיים
static <T> BinTreeNode<T>	clone(BinTreeNode<T> tree) הפעולה מחזירה עץ בינרי חדש שהוא העתק מדוייק (שכפול) של העץ שהתקבל
static boolean	exists(BinTreeNode<java.lang.Integer> tree, int x) הפעולה שבודקת האם ערך מסויים נמצא בעץ
static int	height(BinTreeNode<?> tree) פעולה המחזירה את גובה העץ (עץ עלה גובהו 0)
static java.lang.String	inOrderTraversal(BinTreeNode<?> tree) פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תוכי
static boolean	isAllPositive(BinTreeNode<java.lang.Integer> tree) הפעולה שבודקת האם כל הצמתים בעץ חיוביים
static boolean	isFull(BinTreeNode<?> tree) הפעולה בודקת האם העץ מלא
static boolean	isLeaf(BinTreeNode<?> tree) הפעולה שבודקת האם העץ שמתקבל הוא עץ עלה
static java.lang.String	levelOrderTraversal(BinTreeNode<?> tree) פעולה המחזירה מחרוזת המתארת את סריקת העץ לפי רמות
static int	max(BinTreeNode<java.lang.Integer> tree) הפעולה מחזירה את הערך הגדול ביותר בעץ בינרי של מספרים שלמים
static int	numOfLeaves(BinTreeNode<?> tree) הפעולה מחזירה את מספר העלים בעץ
static int	numOfNodes(BinTreeNode<?> tree) הפעולה מחזירה את מספר הצמתים בעץ
static BinTreeNode<?>	parent(BinTreeNode<?> tree, BinTreeNode<?> child) הפעולה מחזירה את ההורה של צומת מסוים בעץ; במידה והצומת הוא שורש העץ יוחזר null
static java.lang.String	postOrderTraversal(BinTreeNode<?> tree) פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר סופי
static java.lang.String	preOrderTraversal(BinTreeNode<?> tree) פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תחילי
static void	showTree(java.lang.Object tree, java.lang.String... title) הפעולה מציגה את הבינרי המתקבל בצורה גרפית
static int	sumOfNodes(BinTreeNode<java.lang.Integer> tree) הפעולה מחזירה את סכום הצמתים בעץ בינרי של מספרים שלמים
static int	sumOfNodesInLevel(BinTreeNode<java.lang.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(java.lang.Object tree,
                            java.lang.String... title)

הפעולה מציגה את הבינרי המתקבל בצורה גרפית

Parameters:

tree - עץ בינרי גנרי

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

buildExpressionTree

public static BinTreeNode<java.lang.String> buildExpressionTree(java.lang.String exp)

הפעולה יוצרת ומחזירה עץ ביטוי חשבוני

Parameters:

exp - מחרוזת המייצגת ביטוי חשבוני תקין

Returns:

עץ ביטוי חשבוני

buildRandomTree

public static BinTreeNode<java.lang.Integer> buildRandomTree(int maxNodes,
                                                             int low,
                                                             int high)

הפעולה יוצרת ומחזירה עץ בינרי אקראי עם ערכים מספריים אקראיים

Parameters:

maxNodes - מספר צמתים מקסימלי

low - ערך מינימלי שיכול להיות בעץ

high - ערך מקסימלי שיכול להיות בעץ

Returns:

עץ בינרי עם ערכים אקראיים

preOrderTraversal

public static java.lang.String preOrderTraversal(BinTreeNode<?> tree)

פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תחילי

Parameters:

tree - עץ בינרי גנרי

Returns:

מחרוזת המתארת את סריקת העץ בסדר תחילי

inOrderTraversal

public static java.lang.String inOrderTraversal(BinTreeNode<?> tree)

פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר תוכי

Parameters:

tree - עץ בינרי גנרי

Returns:

מחרוזת המתארת את סריקת העץ בסדר תוכי

postOrderTraversal

public static java.lang.String postOrderTraversal(BinTreeNode<?> tree)

פעולה המחזירה מחרוזת המתארת את סריקת העץ בסדר סופי

Parameters:

tree - עץ בינרי גנרי

Returns:

מחרוזת המתארת את סריקת העץ בסדר סופי

levelOrderTraversal

public static java.lang.String levelOrderTraversal(BinTreeNode<?> tree)

פעולה המחזירה מחרוזת המתארת את סריקת העץ לפי רמות

Parameters:

tree - עץ בינרי גנרי

Returns:

מחרוזת המתארת את סריקת העץ לפי רמות

height

public static int height(BinTreeNode<?> tree)

פעולה המחזירה את גובה העץ (עץ עלה גובהו 0)

Parameters:

tree - עץ בינרי גנרי

Returns:

גובה העץ

numOfNodes

public static int numOfNodes(BinTreeNode<?> tree)

הפעולה מחזירה את מספר הצמתים בעץ

Parameters:

tree - עץ בינרי גנרי

Returns:

מספר הצמתים בעץ

clone

public static <T> BinTreeNode<T> clone(BinTreeNode<T> tree)

הפעולה מחזירה עץ בינרי חדש שהוא העתק מדוייק (שכפול) של העץ שהתקבל

Parameters:

tree - עץ בינרי גנרי

Returns:

עץ בינרי

isFull

public static boolean isFull(BinTreeNode<?> tree)

הפעולה בודקת האם העץ מלא

Parameters:

tree - עץ בינרי גנרי

Returns:

הפעולה מחזירה 'אמת' אם העץ מלא, ו'שקר' אחרת

max

public static int max(BinTreeNode<java.lang.Integer> tree)

הפעולה מחזירה את הערך הגדול ביותר בעץ בינרי של מספרים שלמים

Parameters:

tree - עץ בינרי של מספרים שלמים

Returns:

הערך הגדול ביותר בעץ

sumOfNodes

public static int sumOfNodes(BinTreeNode<java.lang.Integer> tree)

הפעולה מחזירה את סכום הצמתים בעץ בינרי של מספרים שלמים

Parameters:

tree - עץ בינרי של מספרים שלמים

Returns:

סכום כל ערכי הצמתים בעץ

sumOfNodesInLevel

public static int sumOfNodesInLevel(BinTreeNode<java.lang.Integer> tree,
                                    int level)

הפעולה מחזירה את סכום הצמתים ברמה מסויימת בעץ בינרי של מספרים שלמים

Parameters:

tree - עץ בינרי של מספרים שלמים

level - רמה בעץ(מספר גדול או שווה לאפס)

Returns:

סכום הצמתים ברמה מסויימת בעץ

isAllPositive

public static boolean isAllPositive(BinTreeNode<java.lang.Integer> tree)

הפעולה שבודקת האם כל הצמתים בעץ חיוביים

Parameters:

tree - עץ בינרי של מספרים שלמים

Returns:

מחזירה 'אמת' אם כל הצמתים בעץ חיוביים, ו'שקר' אחרת

exists

public static boolean exists(BinTreeNode<java.lang.Integer> tree,
                             int x)

הפעולה שבודקת האם ערך מסויים נמצא בעץ

Parameters:

tree - עץ בינרי של מספרים שלמים

x - ערך לחיפוש

Returns:

הפעולה מחזירה 'אמת' אם הערך המתקבל נמצא בעץ, ו'שקר' אחרת

isLeaf

public static boolean isLeaf(BinTreeNode<?> tree)

הפעולה שבודקת האם העץ שמתקבל הוא עץ עלה

Parameters:

tree - עץ בינרי גנרי

Returns:

הפעולה מחזירה 'אמת' אם העץ הוא עץ עלה, ו'שקר' אחרת

numOfLeaves

public static int numOfLeaves(BinTreeNode<?> tree)

הפעולה מחזירה את מספר העלים בעץ

Parameters:

tree - עץ בינרי גנרי

Returns:

מספר העלים בעץ

parent

public static BinTreeNode<?> parent(BinTreeNode<?> tree,
                                    BinTreeNode<?> child)

הפעולה מחזירה את ההורה של צומת מסוים בעץ; במידה והצומת הוא שורש העץ יוחזר null

Parameters:

tree - עץ בינרי גנרי

child - הפנייה לצומת בעץ

Returns:

הפנייה לשורש העץ שהוא הורה