นิยามของโครงสร้างต้นไม้
ต้นไม้ที่มีแบบแผน (Ordered Tree)
การแทนโครงสร้างต้นไม้ในคอมพิวเตอร์
ต้นไม้แบบไบนารี(Binary Tree)
การแทนต้นไมไบนารีในหน่วยความจำ
การเดินเข้าไปในโครงสร้างต้นไม้

โครงสร้างข้อมูลแบบต้นไม้(Tree)

                 โครงสร้างข้อมูลแบบต้นไม้ โครงสร้างต้นไม้ (tree) เป็นโครงสร้างชนิดไม่เชิงเส้นที่สำคัญที่สุดของโครงสร้างข้อมูล โครงสร้างต้นไม้มีความสัมพันธ์อย่างใกล้ชิดกับธรรมชาติของข่าสารและวิธีการแปลงข่าวสารมาก โครงสร้างต้นไม้มีลักษณะที่สมชื่อของตนเอง เพราะมีลักษณะคล้ายกิ่งก้านของต้นไม้ ต้นไม้ตามธรรมชาติจะงอกจากล่างไปบน ส่วนโครงสร้างข้อมูลที่มีลักษณะต้นไม้นั้นเราจะวาดหรือให้เจริญจากบนลงมาล่างดังรูปจุดที่มีการแตกกิ่งก้านสาขาออกไปจะเรียกว่าโหนด (node) โดยข่าวสารจะเก็บอยู่ที่โหนด กิ่งที่ต่อระหว่างโหนดจะแสดงความสัมพันธ์ระหว่างโหนดเรียกว่าลิงค์ (link) อนึ่งตามรูป(ข) จุดปลายของกิ่งจะเรียกว่าโหนดด้วย

(ก) ต้นไม้ปกติในธรรมชาติ (ข) ต้นไม้ในวิชาโครงสร้างข้อมูล

รูปลักษณะของโครงสร้างต้นไม้

 

1.นิยามของโครงสร้างต้นไม้
เราสามารถนิยามโครงสร้างต้นไม้อย่างรีเคอร์ซีฟว่าเป็¹กลุ่มของโหนด T ดังนี้ ท มีโหนดพิเศษโหนดหนึ่งเรียกว่า รากหรือรูต (root node) , R ท โหนดอื่น ๆ ที่ไม่ใช่รูต สามารถถูกแบ่งย่อยออกเป็น n กลุ่ม โดยที่แต่ละกลุ่มไม่มีโหนดร่วมกันเลย สมมติให้ชื่อแต่ละกลุ่มเป็น T1,T2,…,Tn (n >= 0) ซึ่งแต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน แต่จะเรียกว่าเป็น ต้นไม้ย่อย (subtree) ของโหนด R ดังรูปแสดงลักษณะของต้นไม้ตามนิยามแบบรีเคอร์ซีฟ

ซึ่งจะเห็นได้ว่า R เป็นรูตโหนดของต้นไม้ย่อย A,B,C,D
A เป็นรูตโหนดของต้นไม้ย่อย E,F,G
F เป็นรูตโหนดของต้นไม้ย่อย J
B เป็นรูตโหนดของต้นไม้ย่อย H , I เป็นต้น

1.1การเรียกชื่อส่วนต่าง ๆ ของต้นไม
ลักษณะของโครงสร้างต้นไม้มีลักษณะเหมือนการลำดับบรรพบุรุษ ดังนั้นชื่อที่ใช้จึงได้มาจากการลำดับบรรพบุรุษ เช่น FATHER , SON , GRANDSON ฯลฯ ที่ใช้บ่อยจะเป็นความสัมพันธ์ของพ่อ - ลูก (หรือ FATHER - SON )

1.2 ระดับของโหนด (Level)
ระดับของโหนดหนึ่ง ๆ แสดงถึงหน่วยระยะทางตามแนวดิ่งของโหนดนั้นว่าอยู่ห่าง จากรูตโหนดเท่าไร ถ้ากำหนดว่ารูตโหนดของต้นไม้นั้นอยู่ที่ระดับ 1 และกิ่งทุกกิ่งมีความยาวเท่ากันหมดคือยาว 1 หน่วย เลขระดับของโหนดใด ๆ คือจำนวนกิ่งที่น้อยที่สุดจากรูตโหนดบวกหนึ่ง เช่น F มีเลขระดับเป็น 4 เป็นต้น

1.3 ดีกรีของโหนด (Level Degree)
ดีกรีของโหนดคือจำนวนต้นไม้ย่อยของโหนดนั้น ตามรูปที่ 3 โหนด X มีดีกรี 1 โหนด A มีดีกรี 2 ส่วนโหนด H มีดีกรี 3 โหนด B มีดีกรี 1 และโหนด E มีดีกรี 0 เป็นต้น

1.4 โหนดที่เป็นใบ (Leaf Node หรือ Terminal Node)
โหนดที่เป็นใบหมายถึงที่มีดีกรีเป็น 0 เช่นโหนด C,D,E,J,F,G ส่วนโหนดที่มีดีกรีไม่เท่ากับ 0 เรียกว่า โหนดภายใน หรือ interior node หรือ branch node

1.5 Predecessor และ Successor ( หรือ Ancester และ Descendant) predecessor
หมายถึงผู้มาก่อน successor หมายถึงผู้มาทีหลัง R,B,H จะเป็น predecessor ของโหนด E,I,F,J,E,F ไม่มี successor ส่วนโหนด J เป็น successor ของโหนด I และสรุปได้ว่าโหนด I จะเป็น predecessor ของโหนด J (หรือ J เป็น successor ของโหนด I ) ถ้าโหนด I และโหนด J มีกิ่ง (หนึ่งกิ่งหรือมากกว่า ) เชื่องถึงกัน
และโหนด I มีเลขหมายระดับน้อยกว่า โหนด J

1.6 Immediate Successor หรือ SON ของโหนด i immediate successor
คือโหนดทั้งหลายของต้นไม้ย่อย i ที่มีค่าระดับต่ำกว่าโหนด i อยู่หนึ่ง เช่น SON ของโหนด H คือโหนด E,I,F

1.7 Immediate Predecessor หรือ FATHER ของโหนด I immediate predecessor
คือโหนดที่มีค่าระดับสูงกว่าโหนด iอยู่หนึ่ง เช่น FATHER ของโหนด J คือ โหนด I , FATHER ของโหนด I คือโหนด H เป็นต้น

1.8 ป่า (Forest)
ป่าหมายถึงกลุ่มของต้นไม้ที่เกิดจากการเอารูตโหนดของต้นไม้ต้นหนึ่งทิ้งไปตามรูปที่ 3 ถ้าลบรูตโหนด R ออกจะได้ต้นไม้ 3 ต้นประกอบขึ้นเป็น ป่าป่าที่ประกอบด้วยต้นไม้ A,B,X


2. ต้นไม้ที่มีแบบแผน (Ordered Tree)
เราเรียกต้นไม้ A ว่าเป็นต้นไม้ที่มีแบบแผน ถ้าโหนดต่าง ๆ ของต้นไม้นั้นมีความสัมพันธ์ที่แน่นอนประการหนึ่ง เช่น ก่อน , ไปทางขวา , ไปทางซ้าย เป็นต้น ปกติต้นไม้จะถือว่าเป็นแบบที่ไม่มีแบบแผน นั่นคือไม่ได้กำหนดความสัมพันธ์ (เชิงตำแหน่ง) ระหว่างโหนด ฉะนั้นต้นไม้ตามรูป จึงถือว่าเหมือนกัน เพราะมีจำนวนโหนดและจำนวนต้นไม้ย่อยเท่ากัน นอกจากนี้เรายังสามารถ "หมุน" ต้นไม้ทั้งสองต้นนี้ให้อยู่ในแบบเดียวกันได้อีกด้วย แต่ถ้าเรากำหนดว่าต้นไม้ A และ B มีแบบแผน เราจะถือว่าต้นไม้ A และต้นไม้ B เป็นคนละต้นเพราะต้นไม้ A มีใบทางซ้าย 2 ใบ ส่วนต้นไม้ B มีใบทางขวา 2
ในหัวข้อที่ 4 เราจะศึกษาถึงต้นไม้ไบนารีซึ่งเป็นต้นไม้ชนิดมีแบบแผนที่มีความสำคัญต่อระบบคอมพิวเตอร์ ตลอดจนการเขียนโปรแกรมที่มีประสิทธิภาพ

3.การแทนโครงสร้างต้นไม้ในคอมพิวเตอร์
ต้นไม้แบบที่กล่าวมาแล้วนี้สามารถเก็บในคอมพิวเตอร์ โดยอาศัยโครงสร้างของแต่ละโหนดดังรูปที่ 6 รูปที่ 6 โครงสร้างโหนดของต้นไม้ทั่วไป เนื่องจากแต่ละโหนดของต้นไม้จะมีกี่ SON ก็ได้ ดังนั้นจึงให้ส่วนลิงค์ของโหนดมี k ส่วน ถ้าโหนดหนึ่งในต้นไม้นั้นมี 3 SONs ก็จะได้ k = 3 ซึ่งแสดงว่าดครงสร้างของโหนดนั้นนอกจากจะมีส่วนข่าวสารแล้วยังจะมีส่วนลิงค์ 3 ส่วน คือ SON1 ,SON2, SON3 แต่ถ้าอีกโหนดหนึ่งในต้นไม้นั้นมี 5 SONs โครงสร้างของโหนดนั้นจะมีส่วนลิงค์ 5 ส่วนคือ SON1 ถึง SON5 จะเห็นได้ว่าการแทนโหนดลักษณะนี้ขนาดของพื้นที่ความจำที่ใช้สร้างแต่ละโหนดจะมีขนาดไม่คงที่ขึ้นอยู่กับจำนวน SON ของโหนดนั้น การจัดการกับโครงสร้างที่มีขนาดไม่เท่ากันตลอดนี้จะมีความยุ่งยากมากในแง่การจัดสรรและเลิกจัดสรรพื้นที่ความจำให้แก่โหนดวิธีหนึ่งที่จะผ่านข้อยุ่งยากนี้ไปคือ
ให้ขนาดของโหนดคง ที่ตลอด ทั้งนี้ให้กำหนดว่า ค่า k คือค่าดีกรีสูงสุดของโหนดในต้นไม้นั้น ต้นไม้ A มีดีกรีสูงสุดเท่ากับ 4 (จำนวน SON ของโหนด B)อาจจำลองด้วยอาร์เรย์ 5 อาร์เรย์ ชื่อ INFO(9) , SON1 (1:9), SON2 (1:9) , SON3 (1:9), SON4(1:9) แต่ละอาร์เรย์จะมี 9 ช่อง ดังนั้นโหนดที่ใช้จะมีโครงสร้างดังรูปที่เนื่องจากต้นไม้นี้มี 9 โหนด เป็นลักษณะค่าในแต่ละช่องของอาร์เรย์ ค่าตัวเลขที่เติมไว้ได้มาจากการมองดูตต้นไม้ และเลขลำดับของข่าวสารภายในอาร์เรย์ ทั้งนี้เราต้องเก็บข่าวสารของโหนดไว้ในอาร์เรย์ชื่อ INFO ดังนั้น INFO(1) จะเก็บค่า A SON1 (1) จะต้องชี้ไปยัง B ซึ่งคือ 2 ส่วน SON2 (1) ต้องชี้ไปยังโหนด C ซึ่งอยู่ที่ตำแหน่ง 3 ใน INFO ดังนั้นค่าของ SON2(1) จึงเป็น 3 ส่วนค่าของ SON3 (1) และ SON4 (1) จะเป็นศูนย์ (หรือตัวพิเศษอะไรก็ได้ ที่แสดงว่าเป็นส่วนลิงค์ที่เป็นศูนย์หรือว่างเปล่า) ในที่นี้เราเขียนแทนด้วย ขีด (ก) (ข) (ค)การแทนต้นไม้ โดยโครงสร้างโหนดซึ่งจะได้โครงสร้าง (ค) การแทนโครงสร้างต้นไม้ ด้วยอาร์เรย์ 5 อาร์เรย์ โดยใช้โครงสร้างโหนดโดยให้ 1 โหนดใช้หนึ่งคอลัมน์ของทั้ง 5 อาร์เรย์ จะเห็นได้ว่าช่องส่วนที่ใช้เป็นพอยน์เตอร์จะว่างเปล่าและไม่ได้ใช้ประโยขน์อยู่มาก ทั้งนี้เนื่องจากดีกรีของโหนดต่างกันนั่นเอง ถ้าทุกโหนดในต้นไม้มีดีกรีเท่ากัน การแทนในคอมพิวเตอร์จะไม่มีช่องว่างในส่วนพอยน์เตอร์เลย ถ้าดีกรีระหว่างโหนดต่างกันมาก ส่วนพอยน์เตอร์ก็จะสูญเปล่ามาก เพราะเราให้ขนาดของโหนดที่ใช้เท่ากันตลอดดังที่กล่าวไว้แล้ว ปกติถ้าต้นไม้มีดีกรี k (kคือค่าดีกรีสูงสุดของโหนดในต้นไม้นั้น ) และมีโหนด n โหนด การแทนโดยโครงสร้างที่กล่าวมาแล้วจะต้องใช้ ส่วนข่าวสาร n ช่อง ส่วนพอยน์เตอร์ kn ช่อง เนื่องจากต้นไม้นี้มี n โหนด ดังนั้นจำนวนช่องพอยน์เตอร์ที่ใช้จริงเพียง n - 1 ช่อง (ไม่นับรูตโหนด เพราะไม่มีโหนดใดชี้ไปยังรูตโหนด) ดังนั้น จำนวนช่องพอยน์เตอร์ที่ไม่ได้ใช้ประโยชน์ = kn - ( n - 1 ) = n ( k - 1 ) + 1 ตามรูปที่ 7 หรือ 8 เมื่อ n = 9 และ k = 4 จะเห็นได้ว่าจำนวนช่องที่ไม่ได้ใช้ประโยชน์เท่ากับ 9(4 -1) + 1 = 28 ช่อง ในหัวข้อต่อไปเราจะศึกษาถึงต้นไม้ไบนารีและวิธีการแทนต้นไม้ไบนารีในคอมพิวเตอร์อย่างมีประสิทธิภาพ สำหรับต้นไม้ธรรมดาอาจแปลงเป็นต้นไม้ไบนารีได้

4.ต้นไม้แบบไบนารี (Binary Tree)
4.1 นิยาม ต้นไม้ไบนาร
เป็น rooted binary tree ที่ว่างเปล่า หรือประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่มที่ไม่มีโหนดร่วมกัน แต่ละกลุ่มจะมีชื่อเรียก (โดยตำแหน่งที่อยู่หรือที่เขียน) ว่าต้นไม้ย่อยทางซ้าย (left subtree) และต้นไม้ย่อยทางขวา (right subtree) ตามลำดับ คำว่า ว่างเปล่า ในนิยามหมายความว่า ต้นไม้ไบนารีต้นนั้นมีแต่รูตโหนดเพียงโหนดเดียวเท่านั้น โครงสร้างต้นไม้ที่ใช้ในการจัดการข่าวสารโดยคอมพิวเตอร์นั้น ส่วนใหญ่จะเป็นแบบโครงสร้างต้นไม้ไบนารี ลักษณะพิเศษจำเพาะของต้นไม้ไบนารีคือแต่ละโหนดมีดีกรีอย่างมากที่สุดเท่ากับ 2 นอกจากนี้ต้นไม้ไบนารียังเป็นต้นไม้ที่มีแบบแผนความสัมพันธ์เชิงตำแหน่งระหว่างโหนด นั่นคือที่โหนดใด ๆ ต้นไม้ย่อยของโหนดนั้นจะเรียกชื่อเฉพาะว่าเป็น ต้นไม้ย่อยทางขวา หรือ ต้นไม้ย่อยทางซ้าย ถ้าดูแค่โหนด จากโหนดหนึ่งจะเป็นความสัมพันธ์ FATHER และมีอีก 2 โหนด ต่อลงไปเป็น โหนดทางซ้าย หรือ left son หรือ LSON และโหนดทางขวา หรือ right son หรือ RSON ดังรูป

โครงสร้างต้นไม้ไบนารี LSON

รูป ตัวอย่างของต้นไม้ไบนารีดูได้จากรูป(ก),(ข),(ค) ส่วนรูป (ง),(จ) และ (ฉ) นั้นไม่ใช่ต้นไม้ไบนารี เนื่องจากมีวงจรปิด

4.2 ต้นไม้ไบนารีแบบสมบูรณ์ (Complete Binary Tree)
ต้นไม้ไบนารีแบบสมบูรณ์ หมายถึงต้นไม้ไบนารีที่แต่ละโหนดภายในมีโหนดย่อยซ้ายและขวา (นั่นคือแต่ละโหนดภายในมี left son และ right son ) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป (ก) เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มี 3 ระดับ ส่วนรูปที่ 11 เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 4 จะเห็นได้ว่าต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 3 จะมีโหนดทั้งหมดเท่ากับ 23 - 1 หรือ 7 และต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ 4 จะมีโหนดเท่ากับ 24 - 1 หรือ 15 ซึ่งความสัมพันธ์ระหว่างระดับ (1) กับจำนวนโหนด (n) ในต้นไม้ไบนารีแบบสมบูรณ์ จะเขียนได้ดังนี้ n = 21 - 1

รูป ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบทั้งหมดอยู่ที่ระดับ 4

4.3 การแปลงต้นไม้ทั่วไปเป็นแบบไบนารี
ในต้นไม้ทั่วไปโหนดแต่ละโหนดจะมีกี่ SON ก็ได้ ส่วนต้นไม้ไบนารีแต่ละโหนดจะมี SON ได้มากที่สุดเท่ากับ 2 SONs การแปลงต้นไม้ทั่วไปให้เป็นแบบไบนารีจะใช้หลักความจริงที่ว่า ในต้นไม้ทั่วไปแต่ละโหนดจะมี SON ที่อยู่ทางซ้ายสุด 1 SON และ SON โหนดนั้นจะมีพี่น้องถัดไป 1 โหนดเท่านั้น การแปลงนั้นแบ่งได้เป็น 2 ขั้นตอน คือ
ขั้นที่ 1 แปลงต้นไม้ทั่วไปโดยใช้หลักความสัมพันธ์ระหว่างโหนดเป็น leftmost son - next sibiling
ขั้นที่ 2 หมุนต้นไม้ที่แปลงแล้วไป 45 องศา จะได้ต้นไม้ไบนารีแบบปกติ การแปลงต้นไม้ทั่วไปเป็นแบบไบนารี

4.4 การแปลงป่าให้เป็นโครงสร้างแบบต้นไม้ไบนารี ในกรณีถ้ามีต้นไม้ทั่วไปหลาย ๆ ต้น เราสามารถแทนกลุ่มของต้นไม้นี้ โดยต้นไม้ไบนารี่ต้นเดียวได้ดังนี้

ขั้นที่ 1 ให้แปลงต้นไม้ทั่วไปแต่ละต้น ให้เป็นต้นไม้แบบไบนารี
ขั้นที่ 2 ให้เชื่อมรูตโหนดของต้นไม้ไบนารีแต่ละต้น โดยใช้ความสัมพันธ์ "พี่น้อง"
ขั้นที่ 3 หมุนต้นไม้ที่ได้ (ก)45 องศา ก็จะได้ต้นไม้ไบนารีที่แทนกลุ่มต้นไม้ทั่วไปที่กำหนดให้ การแปลงป่าให้เป็นต้นไม้ไบนารี

5.การแทนต้นไม้ไบนารีในหน่วยความจำ ต้นไม้ไบนารีสามารถแทนได้ 2 แบบ คือ
1. การแทนโดยอาศัยพอยน์เตอร์
2. การแทนโดยอาศัยแอดเดรสของโหนด หรือการแทนแบบซีเควนเชียล (sequential)

5.1 การแทนโดยให้แต่ละโหนด
มีโครงสร้างโหนดสำหรับต้นไม้ไบนารี LLINK หรือ LSON เป็นพอยน์เตอร์ชี้ไปยังต้นไม้ย่อยทางซ้าย ส่วน RLINK หรือ RSON เป็นพอยน์เตอร์ชี้ไปยังต้นไม้ย่อยทางขวา ส่วนต้นไม้ไบนารีทั้งต้นจะแทนด้วย T โดยที่ T เป็นพอยน์เตอร์ชี้ไปยังรูตโหนด ถ้า T = L แสดงว่าต้นไม้ไบนารีนั้นว่างเปล่า T น L แสดงว่าต้นไม้ไบนารีนั้นไม่ว่างเปล่า และ T จะเป็นแอดเดรสของรูตโหนด วิธีการแทนลักษณะนี้จะช่วยให้การทำ insertion และ deletion ของโหนดที่ส่วนกลางของต้นไม้ง่ายขึ้นมาก แต่เมื่อต้องการหา FATHER NODE ของ โหนด iอาจมีข้อยุ่งยากบ้างแต่ก็สามารถช่วยได้โดยอาศัยกลไกของสแตก

5.2 การแทนโดยอาศัยแอดเดรสของโหนด หรือการแทนแบบซีเควนเชียล วิธีนี้เป็นการแทนต้นไม้ไบนารีด้วยอาร์เรย์ 1 มิติอาร์เรย์เดียว การแทนแบบนี้เหมาะกับโครงสร้างต้นไม้ไบนารีแบบ full binary tree ที่สุด ซึ่งจะได้กล่าวต่อไป การแทนจะเริ่มต้นด้วยการให้หมายเลขแก่แต่ละโหนด ตั้งแต่ระดับ 1 ระดับ 2 …ไปเรื่อย ๆจนถึงระดับ k การให้ตัวเลขในแต่ละระดับให้จากซ้ายไปขวา โดยให้รูตโหนดมีหมายเลข 1 เสมอการให้ตัวเลขจะต้องถือว่าต้นไม้ไบนารีเป็นต้นไม้ไบนารีแบบสมบูรณ์ การให้แอดเดรสแก่ต้นไม้ไบนารีที่ถูกต่อเติมให้สมบูรณ์ เราจะต้องใช้อาร์เรย์ขนาด 15 ช่อง เพื่อเก็บต้นไม้ต้นนี้ ตำแหน่งของข่าวสารในต้นไม้จะตรงกับตำแหน่งในอาร์เรย์ การแทนต้นไม้ โดยใช้อาร์เรย์ โดยทั่วไปแล้วต้นไม้ไบนารีที่มีความสูง (ระบุโดยค่า level ที่มากที่สุด) h จะต้องใช้อาร์เรย์ที่มีขนาด 2h - 1 ช่อง เมื่อแทนโดยอาร์เรย์แล้ว เราจะต้องมีวิธีหาว่า "พ่อ" ของโหนด C คือใคร หรือว่า "ลูก" ของโหนด B คือใคร ดังนั้น FATHER , LSON ,RSON ของโหนดใดๆ ( i )จะหาได้ โดยความสัมพันธ์ดังต่อไปนี้ ท FATHER ( i ) จะอยู่ที่ตำแหน่ง [ i/2 ] ถ้า i น 1 แต่ถ้า i = 1 โหนด i จะเป็น รูตโหนด ซึ่งในกรณีนี้ไม่มี FATHER (i) ท LSON (i) จะอยู่ที่ตำแหน่ง 2i ถ้า 2i < = n แต่ถ้า 2i > n แล้ว โหนด i จะไม่มี left son ท RSON (i) จะอยู่ที่ตำแหน่ง 2i +1 ถ้า 2i + 1 < = n แต่ถ้า 2i + 1> n แล้ว i จะไม่มี right son

6.การเดินเข้าไปในโครงสร้างต้นไม้ (Tree Traversal)
การนำต้นไม้ไบนารีมาใช้ประโยชน์นั้น หมายความว่าเราต้องมีวิธี เดิน หรือ traverse เข้าไปในต้นไม้อย่างมีแบบแผน เพื่อไป เยี่ยม โหนดต่าง ๆ โหนดละ 1 ครั้ง คำว่า เยี่ยมหมายถึงว่าเราจะไปยังโหนดเพื่อประมวลผลบางอย่างที่ต้องการกระทำกับโหนดนั้น เช่น หาข่าวสาร ดังนั้นผลลัพธ์จากการเดินเข้าไปในต้นไม้คือจะได้ข่าวสารที่เก็บ(หรือชี้) โดยโหนดเหล่านั้นออกมาในรูปเชิงเส้น ซึ่งนำไปใช้ประโยชน์ได้ ความคิดเริ่มต้นของการเดินก็คือ เราต้องเยี่ยมแต่ละโหนดพร้อมทั้งต้นไม้ย่อยทางซ้ายและทางขวาของโหนดนั้น ตามแนวความคิดนี้เราจะแยกต้นไม้ไบนารีออกเป็น 3 ส่วนคือ R,TL,TR โดยที่ R จะแทนรูตโหนด TL จะแทนต้นไม้ย่อยทางซ้ายและ TR จะแทนต้นไม้ย่อยทางขวา จะเห็นได้ว่าจะมีวิธีเดินอยู่ 6 ทางคือ R TL TR , TL RTR , TL TR R , TR RTL , R TR TL สัญลักษณ์ที่เขียนนี้เป็นลักษณะการนิยามแบบรีเคอร์ซีฟและลำดับจากซ้ายไปขวา ถึงแม้ว่าจะมีวิธีเดิน 6 วิธี แต่เราจะสนใจเพียง 3 วิธีแรกเท่านั้น ซึ่ง 3 วิธีแรกมีชื่อเรียกพิเศษและลักษณะรายละเอียดการเดินดัง¹ี้

1) เดินแบบพรีออร์เดอร์ (pre - order traversal) - R TL TR ท เยี่ยม R ท เดินเข้าไปใน TL (ของ R) อย่างพรีออร์เดอร์ ท เดินเข้าไปใน TR (ของ R) อย่างพรีออร์เดอร์

2) เดินแบบอินออร์เดอร์ (in - order traversal) - TL RTR ท เดินเข้าไปใน TL (ของ R) อย่างอินออร์เดอร์ ท เยี่ยม R ท เดินเข้าไปใน TR (ของ R) อย่างอินออร์เดอร์

3) เดินแบบโพสออร์เดอร์ (post - order traversal) - TL TR R ท เดินเข้าไปใน TL (ของ R) อย่างโพสต์ออร์เดอร์ ท เดินเข้าไปใน TR (ของ R) อย่างโพสต์ออร์เดอร์ ท เยี่ยม R อีก 3 วิธี เกิดจากการสับเปลี่ยนตำแหน่ง TL และ TR ของ 3 วิธีที่กล่าวมาแล้ว ดังนั้น 3 วิธีหลังจะมีชื่อคล้าย ๆกับ 3 วิธีแรก เพียงแต่มีคำว่า reverse เพิ่มเข้าไปเท่านั้น ดังนั้น 3 วิธีหลังจะมีชื่อดังนี้

4) แบบ reverse pre - order traversal ( R TR TL )

5) แบบ reverse in - order traversal ( TR RTL )

6) แบบ reverse post - order traversal ( TR TL R)
6.1 การเดินเข้าแบบพรีออร์เดอร์ ( R TL TR ) สมมติมีต้นไม้ไบนารีตามรู» (ก) เราจะเดินเข้าไปในต้นไม้นี้อย่างพรีออร์เดอร์ได้ดังรูป (ข) (ก)จุดเริ่มต้นแสดงโดยพอยน์เตอร์ T (ข) ทิศทางการเยี่ยมโหนด

รูป ต้นไม้ไบนารี

เริ่มที่รูตโหนด A แล้วให้เยี่ยมโหนด A ก่อน (จากนิยาม R TL TR ) เราจะให้คำว่า เยี่ยม ของเรา หมายถึง พิมพ์ ชื่อโหนดออกมา ต่อไปให้เดินเข้าไปใน TL ของโหนด A ไปอยู่ที่ B (เนื่องจาก B เป็นรูตโหนดของต้นไม้ย่อยทางซ้ายของ A ) เมื่อคิดอย่างรีเคอร์ซีฟเท่ากับ เราตั้งต้นทำ R TL TR ใหม่ ดังนั้นโหนด B จะตรงกับตำแหน่ง R ใน R TL TR นั่นคือเราต้องเยี่ยมโหนด B เมื่อเยี่ยมโหนด B แล้ว เราก็จะเดินเข้าไปใน TL ของโหนด B ไปอยู่ที่ D แล้ว ตั้งต้นทำ R TL TR ใหม่ ดังนั้นจึงเยี่ยมโหนด D จากนั้นเดินเข้าไปใน TL ของโหนด D แต่เนื่องจาก TL ของโหนด D ว่างเปล่า ดังนั้นจึงทำตำแหน่ง TR ใน R TL TR ต่อไป TR ของโหนด D คือ G จึงได้ค่า G พิมพ์ออกมา สรุปได้ว่าในขณะนี้ชุดของโหนดที่พิมพ์ออกมา คือ ABDG ต่อไปให้เดินเข้าไปใน TL ของ G ซึ่งว่างเปล่า ดังนั้นก็ข้ามไปเดิน TR ของ G ซึ่งก็ว่างเปล่าอีกเช่นกัน ณ จุดนี้เท่ากับว่าเราได้เดิน TL ของโหนด A ครบแล้ว ดังนั้นจึงข้ามไปทำ TR ของโหนด A นั่นคือไปตั้งต้นที่โหนด C แล้วเริ่มต้นทำการเดินตามนิยาม R TL TR ใหม่อีก โดยเริ่มเยี่ยมโหนด C แล้วเดินเข้าไปใน TL ของโหนด C ต่อไปเริ่มเยี่ยมโหนด E จากนั้นก็เดินเข้าไปใน TL ของโหนด E ซี่งว่างเปล่า ต่อไปก็เดินเข้าไปใน TRของโหนด E ซึ่งก็ว่างเปล่าอีก ดังนั้นเท่ากับได้เดิน TL ของโหนด C ครบแล้ว ต่อไปก็เดินเข้าไปใน TR ของโหนด C จนครบ … ในที่สุดก็เท่ากับเดินเข้าไปใน TR ของโหนด A ครบแล้ว เมื่อเราเดินหรือทราเวิร์สต้นไม้ไบนารีอย่างพรีออร์เดอร์ (R TL TR ) ชุดข่าวสารที่พิมพ์ออกมาก็จะเป็นดังนี้ ABDGCEFHI

6.2 การเดินเข้าแบบอินออร์เดอร์ (TL RTR ) การเดินแบบนี้มีลักษณะคล้ายกับการเดินแบบพรีออร์เดอร์ นั่นคือต้องท่องต้นไม้ย่อยทางซ้าย (TL )ให้ครบก่อน แล้วจึงค่อยท่องต้นไม้ทางขวาได้ การเดินแบบอินออร์เดอร์นี้เราจะเยี่ยมโหนดภายหลังจากที่ได้เดิน TL อย่างอินออร์เดอร์ครบหมดแล้วเท่านั้น เมื่อเดินอย่างอินออร์เดอร์แล้วจะได้ชุดลำดับของโหนดที่เยี่ยมดังนี้ DGBAECHFI 6.3 การเดินเข้าแบบโพสต์ออร์เดอร์ (TL TRR)เราเริ่มเดินเข้าไปใน TL จากโหนด A ถึงโหนด D จากนั้นก็เริ่มเดินเข้าไปใน TR ของโหนด D ซึ่งว่างเปล่า เป็นอันว่าเราได้เดิน TL, TR ของโหนด D ครบถ้วน ต่อไปก็ถึงคราว R ซึ่งก็ได้แก่การเยี่ยมโหนด D และได้โหนด D พิมพ์ออกมา เมื่อถึงตอนนี้ก็เท่ากับว่าเราได้เดิน TL ของโหนด B ครบถ้วน จึงเริ่มเดินเข้าไปใน TR ของโหนด B โดยเริ่มที่โหนด E ต่อไปก็เดินเข้าไปใน TL ของโหนด E อย่างโพสต์ออร์เดอร์อีก ได้โหนด G พิมพ์ออกมา (ตอนนี้ชุดของโหนดที่พิมพ์ออกมาแล้วคือ DG) จากนั้นก็เดินเข้าไปใน TR ของโหนด E อีก ได้โหนด H พิมพ์ออกมา ซึ่งเท่ากับเราได้เดิน TL , TR ของโหนด E ครบแล้ว จึงเยี่ยมโหนด E พิมพ์โหนด E ออกมา )ตอนนี้ชุดของโหนดที่พิมพ์ออกมาแล้วคือ DGHE) ณ จุดนี้เท่ากับว่าได้เดิน TL, TR ของโหนด B ครบถ้วนแล้ว จึงเยี่ยมโหนด B หลังจากนี้ เท่ากับเราได้เดิน TL ของโหนด A ครบถ้วน จึงหันไปเดิน TR ของโหนด A ซึ่งจะได้โหนด F และ C พิมพ์ออกมาตามลำดับ ขณะนี้เท่ากับว่าได้เดินเข้าไปใน TL และ TR ของโหนด A ครบถ้วนแล้ว จึงเยี่ยมโหนด A เป็นอันว่าสิ้นสุดการเดินอย่างโพสต์ออร์เดอร์เข้าไปในต้นไม้นี้ การเดินเข้าไปในโครงสร้างต้นไม้อย่างโพสต์ออร์เดอร์ ชุดของโหนดที่พิมพ์ออกมาคือ DGHEBFCA จากวิธีการเดินที่อธิบายมาแล้วนี้ เมื่อคิดเป็นโปรแกรมโดยอาศัยกลไกของสแตกมาช่วย จะทำได้ดังนี้ เมื่อเริ่มต้นพบโหนดอะไร (ตอนทำ TL) เราจะ PUSH โหนดใส่สแตก พร้อมทั้งทำเครื่องหมายว่าเราได้เดินเข้าไปใน ของโหนดนั้นแล้ว เมื่อเราพบโหนดนี้ในคราวหน้า (โดยการ POP) เราจะต้องทำเครื่องหมายอีกเพื่อแสดงว่าเราได้เดิน TR ของโหนดนั้นแล้ว จากนั้นจับโหนดนั้นใส่สแตกอีก ครั้งถัดไป (ครั้งที่ 3) ที่เราพบโหนดนี้ เราจะเยี่ยม แล้วทิ้งโหนดนั้นไป คือ ไม่ต้องผลักไปเก็บไว้ในสแตกอีก การเดินเข้าไปในต้นไม้อย่างโพสต์ออร์เดอร์จะมีประโยชน์มาก ถ้าเราจำเป็นต้องเยี่ยมโหนดใบก่อนโหนดภายในทั้งหลาย