Binary Tree และการแวะผ่าน

นึกภาพก่อน

แผนผังองค์กร โฟลเดอร์ในคอมพิวเตอร์ และสาแหรกครอบครัว มีรูปร่างเดียวกัน: เริ่มจากจุดเดียว แล้วแตกแขนงลงไป แต่ละจุดมี "ผู้บังคับบัญชา" ได้คนเดียว โครงสร้างแบบนี้คือ ต้นไม้ (tree)

นิยาม

• ต้นไม้ประกอบด้วย ปม (node) กับ เส้นเชื่อม (edge) เส้นเชื่อมมีทิศทาง
• A เป็น ปมพ่อ ของ B เมื่อมีเส้นเชื่อมจาก A ไปยัง B
• แต่ละปมมีปมพ่อได้เพียงปมเดียว ยกเว้นปมพิเศษคือ ราก (root) ที่ไม่มีพ่อ
• ต้นไม้ที่มี v ปม ย่อมมี v − 1 เส้นเชื่อม (ทุกปมยกเว้นรากมีเส้นจากพ่อหนึ่งเส้น)
• ปมที่ไม่มีลูกเรียกว่า ใบ (leaf)

การสร้างต้นไม้ทั่วไป

ต้นไม้ทวิภาค (Binary Tree)

ทุกปมมีลูกได้ไม่เกินสองลูก เรียกว่า ลูกซ้าย และ ลูกขวา

public class BinaryTree {
  static class Node {
    Object element;
    Node left;
    Node right;
    Node(Object e, Node l, Node r) {
      element = e; left = l; right = r;
    }
    boolean isLeaf() {
      return left == null && right == null;
    }
  }
  Node root;
}

อ็อบเจกต์ต้นไม้เก็บเฉพาะ root ปมอื่นเข้าถึงได้โดยเดินตามตัวโยงลงไป

เทียบกับ Binary Heap

ทั้งสองเหมือนกันตรงที่พ่อมีลูกได้สองข้างเท่านั้น ส่วนที่ต่าง:

การแวะผ่าน (Traversal)

การแวะผ่านคือการไปเยือนทุกปมปมละครั้ง มีสามแบบ ต่างกันที่ จังหวะแวะปมตัวเอง เทียบกับต้นไม้ย่อยซ้ายและขวา:

คำว่า "ซ้าย" และ "ขวา" หมายถึง ทำกระบวนการเดียวกันกับต้นไม้ย่อยทั้งต้น ไม่ใช่แค่ปมลูก จึงเขียนเป็นเมท็อดเรียกซ้ำได้ตรง ๆ

จำง่าย: Pre = ปมมา ก่อน, In = ปมอยู่ ตรงกลาง, Post = ปมมา หลัง ส่วนซ้ายมาก่อนขวาเสมอทั้งสามแบบ

ตัวอย่างไล่ทีละขั้น

ต้นไม้จากสไลด์:

            35
          /    \
        29      40
       /  \       \
     20    32      50
    /  \          /
  10    25      45

Preorder (ปม → ซ้าย → ขวา):

1. แวะ 35 แล้วไปต้นไม้ย่อยซ้าย (ราก 29)
2. แวะ 29 แล้วไปซ้าย (ราก 20)
3. แวะ 20, ซ้ายคือ 10 (แวะ), ขวาคือ 25 (แวะ)
4. กลับมาที่ 29 ไปขวา แวะ 32
5. กลับมาที่ 35 ไปต้นไม้ย่อยขวา แวะ 40 (ไม่มีซ้าย) ไปขวา แวะ 50 ไปซ้ายของ 50 แวะ 45

ผลลัพธ์ทั้งสามแบบ:

ข้อสังเกตที่ใช้ตรวจคำตอบได้:

• Preorder: รากมาเป็นตัวแรก
• Postorder: รากมาเป็นตัวสุดท้าย
• Inorder: รากอยู่ระหว่างปมของต้นไม้ย่อยซ้ายกับขวา

อีกตัวอย่างจากสไลด์ (ราก B; ลูกของ B คือ C และ D; C มีลูกซ้าย E; D มีลูก F และ H; F มีลูกขวา G): Preorder B, C, E, D, F, G, H · Inorder E, C, B, F, G, D, H · Postorder E, C, G, F, H, D, B

void preorder(Node r) {
  if (r == null) return;
  visit(r);
  preorder(r.left);
  preorder(r.right);
}

เมท็อดแบบเรียกซ้ำใน BinaryTree

int numNodes(Node node) {
  if (node == null) return 0;
  return 1 + numNodes(node.left) + numNodes(node.right);
}
int numLeaves(Node r) {
  if (r == null) return 0;
  if (r.isLeaf()) return 1;
  return numLeaves(r.left) + numLeaves(r.right);
}
int height(Node node) {
  if (node == null) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}
Node copy(Node r) {
  if (r == null) return null;
  Node leftTree = copy(r.left);
  Node rightTree = copy(r.right);
  return new Node(r.element, leftTree, rightTree);
}

ทุกเมท็อดมีรูปแบบเดียวกัน: ต้นไม้ว่าง (null) ตอบได้ทันที ไม่อย่างนั้นถามคำตอบจากต้นไม้ย่อยซ้ายและขวาแล้วนำมารวมกัน

• ความสูงของต้นไม้ว่างคือ −1 ต้นไม้ที่มีปมเดียวจึงสูง 1 + max(−1, −1) = 0
• ต้นไม้ตัวอย่างข้างบน: 9 ปม, 4 ใบ (10, 25, 32, 45), สูง 3

จุดที่มักพลาด

1. แวะแค่ลูก ไม่ใช่ต้นไม้ย่อยทั้งต้น

Inorder ที่ราก 35 ต้องทำต้นไม้ย่อยซ้าย ทั้งต้น (10 20 25 29 32) ให้เสร็จก่อนจึงแวะ 35

2. สลับ Inorder กับ Preorder

ดูตำแหน่งราก: Pre อยู่หน้าสุด, In อยู่กลาง, Post อยู่ท้ายสุด

3. ปมที่มีลูกข้างเดียว

40 ไม่มีลูกซ้าย Inorder จึงแวะ 40 ทันทีแล้วไปขวา ส่วน 50 มีแต่ลูกซ้าย Inorder จึงได้ 45 ก่อน 50

4. นับเส้นเชื่อมผิด

v ปมมี v − 1 เส้นเสมอ

5. คิดว่า binary tree ต้องเต็มหรือต้องเรียงค่า

นั่นคือคุณสมบัติของ heap binary tree ทั่วไปไม่มีข้อกำหนดนี้

6. ความสูงของต้นไม้ว่าง

ตามโค้ดในสไลด์คือ −1 ไม่ใช่ 0

7. isLeaf ใช้ ||

ใบต้องไม่มีลูก ทั้งสองข้าง จึงใช้ &&

ที่มา: BinaryTREE_8.pdf หน้า 1–9, 14–27 และ 54–55