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

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.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 ของโหนด

 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 (ข) ทิศทางการเยี่ยมโหนด

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