صفحه 1:
(Ober) ی
1٠١.١ بخش
شنایی با درختها
(Introduction to Trees)
صفحه 2:
۲۲۲آ۲۳۲لن ۳
درحت
* یک گراف ساده همبند بدون دور ساده را درخت می
گویند.
* قضیه: یک گراف درخت است اگر و فقط اگر بین هر دو
راس آن دقیقا یک مسیر ساده وجود داشتته باشد.
صفحه 3:
eee
کدامیک از گراف های زیر درخت است؟
Ath
صفحه 4:
8
درخت ریشه دار (Rooted Tree)
* یک درخت ريشه دار درختی است که در آن یک راس به عنوان
ريشه معرفی شده و همه یال ها از سمت ريشه جهت دار می
gd
With root a
صفحه 5:
a
چهار نمونه از درخت ریشه دار
FIGURE 7 Four Rooted Trees.
صفحه 6:
8
درخت 1721-277
* به یک درخت ريشه دار درخت 173-077 می گویند اگر هر راس
داخلی آن (راس های که فرزند دارند) در این درخت بیشتر از
m بچه نداشته باشد.
"ا یک درخت 72-2777 کامل (1766 29-2777 [ل) درخت
ريشه داری است که تمام رئوس داخلی آن دقیقا « تا بچه
داشته باشند.
"ا به یک درخت 172-277 که مقدار 7 آن برابر با ۲ باشد یک
درخت دودویی (1۳66 3112877) می گویند.
صفحه 7:
Qoved Tree
صفحه 8:
SS
A Tree Has a Root
TREC ROOT;
اريشه درخت
صفحه 9:
a
Leaf nodes have no children
گره های برگ
صفحه 10:
a
A Tree Has Levels
صفحه 11:
a
Level One
L@OeL a
صفحه 12:
SS
Level Two
۶006 &
صفحه 13:
Se 0000
Sibling nodes have same parent
1011006
ادر يا خواهر
صفحه 14:
Se 0000
Sibling nodes have same parent
صفحه 15:
a
A Subtree
00
۱۵۲ 60617666 0 ROOT
زير درخت سمت جب ريشة
صفحه 16:
SS
Another Subtree
00
۳161۲ 6006 06 001١
صفحه 17:
SS با
?How many internal vertices
صفحه 18:
ل
—
whe gas درخت
2 قضیه: درختی با ۶ راس -١ 7 يال دارد.
* قضیه: یک دخت 111-34177 کامل با ٌ راس داخلی دارای
11212271 راس می باشد
u (full 722-277 1۳66( قضیه: یک دخت 722-2777 کامل *
(i) n vertices has i = (n — 1)/m internal vertices and] = [(m — 1)n + 1]/m leaves,
(ii) i internal vertices has n = mi + 1 vertices and / = (m — 1)i + | leaves,
(iii) |leaveshasn = (ml — 1)/(m — 1)verticesandi = (J — 1)/(m — 1) internal vertices
صفحه 19:
لا
خصوصيات درخت
* قضیه: در یک درخت 172-0177 به ارتفاع 8 حداکثر 1 برگ
دارد.
قضیه: اگر یک درخت 172-2777 دارای / برگ و ارتفاع 1
داشته باشد آنگاه 106 ]<122. اگر این درخت 22 تايى؛ پر
و متوازن باشد. آآرر100 حور
صفحه 20:
فصل دهم: درخت ها (1۲665)
بخش ۱۰.۳
بش درخت
(Tree Traversal)
صفحه 21:
سیستم آدرس دهی جهانی
(Universal Address System)
saa f 3.123 |
34223126
FIGURE 1 The Universal Address System of an Ordered Rooted Tree.
صفحه 22:
a
(Preorder Traversal) wi yi jd plo
[al ريشه سپس زیر درخت به ترتیب از سمت چپ به راست
دیده می شود.
صفحه 23:
se
صفحه 24:
h
gt
d
p fe
0
j
صفحه 25:
Se
(inorder Traversal) ew 35 glo who
* ابتدا زیر درخت اول از سمت چپ دیده می شود سپس ریشه
دیده می شود و بعد بقیه زیر درخت ها از سمت چپ به راست.
Step 2: Visit r
Inorder traversal
Step |: Step 3: Step a+ I:
Visit Ty in Visit 7) in Visit Ty in
inorder inorder inorder
صفحه 26:
صفحه 27:
صفحه 28:
- ©
<e
=e
ge
وه
~e
ve
se
ne
se
ae
se
هاعد
ve
هاه
8# ۵ ۰ و
.٠ ه و و ۰
4
2
ل ه ۰ كا
ve
“ee
صفحه 29:
a
(Postorder Traversal) پیمایش پس تر تیب
ابتدا زیردرخت ها به ترتيب از سمت *
شوند و در انتها ريشه ديده مى شود.
به راست ديده مى
Step n+ |: Visit
Postorder uaversil
Step | Step 2 Step n:
Visit 7) Visit Ty Visit 7,
in postorder__in postorder in postorder
صفحه 30:
صفحه 31:
ve
صفحه 32:
7
4
۰
۲ 1 1 i
۰ و و و و و و و
e
e
ae
°°
ze
“eo
f bc lm gh i
۰ هو و و و و وه و و
e
e
“oe
صفحه 33:
SS با
۸۱۱ ب YN
۳, /\
7 /\ 1 ۳
hs 3
FIGURE 10 A Binary Tree Representing ((x + y) T 2) + (x — 4)/3).
