Please enable JavaScript.
Coggle requires JavaScript to display documents.
Unit 6 ต้นไม้ (Trees) (ต้นไม้แบบแผ่ที่เล็กที่สุด (นิยามที่ 6.8
…
Unit 6 ต้นไม้ (Trees)
-
-
บทนำ
นิยามที่ 6.2 ต้นไม้มีราก (Rooted tree) คือ ต้นไม้ที่มีการกําหนดจุดๆ หนึ่งเป็นรากและทุกๆเส้นเชื่อมพุ่งไปในทิศทางที่ออกจากราก
นิยามที่ 6.3ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบ m ภาค (m-ary tree) ถ้าทุกๆ จุดภายในมีลูกไม่เกิน m และจะเรียกว่าเป็น ต้นไม้แบบเต็ม m ภาค (full m-ary tree) ถ้าทุกๆ จุดภายในมีลูกเท่ากับ m เท่านั้น
นิยามที่ 6.1 ต้นไม้คือ กราฟแบบไม่มีทิศทางที่เชื่อมต่อกัน (connected undirected graph) ซึ่งไม่มีวงจรแบบ
ง่ายจากนิยามจะได้ว่ากราฟแบบไม่มีทิศทางใดๆ จะเป็นต้นไม้ก็ต่อเมื่อมีทางเดินเพียง 1 ทางระหว่างคู่ของจุดใดๆ ในกราฟ
คุณสมบัติของต้นไม้
-
ทฤษฎีที่ 3 ต้นไม้แบบเต็ม m ภาคซึ่งมีจํานวนจุดทั้งหมดเท่ากับ n จํานวนจุดภายในเท่ากับ i และมีจํานวนจุดที่เป็นใบเท่ากับ l จะได้ความสัมพันธ์ดังนี้
-
-
-
-
ทฤษฎีที่ 4 ต้นไม้แบบ m ภาคซึ่งมีความสูง h จะเป็นต้นไม้แบบสมดุล
(balanced tree) ถ้าทุกใบอยู่ที่ระดับ h หรือ h–1
-
-
-
