26.2 ท่องต้นไม้

เก็บต้นไม้ได้แล้ว งานถัดไปคือไปให้ถึงทุกโหนด เรียกว่า การท่องต้นไม้ (tree traversal) อาเรย์มีลำดับเดียวคือซ้ายไปขวา แต่ต้นไม้ไปได้หลายลำดับ และลำดับที่เลือกเปลี่ยนสิ่งที่คำนวณได้ หน้านี้ดูสามลำดับของ binary tree การท่องทีละชั้นด้วย queue การคำนวณขนาด ความสูง และความลึกของทุกโหนดในรอบเดียว และปิดท้ายด้วย เส้นผ่านศูนย์กลาง (diameter) ของต้นไม้ ซึ่งเป็นโจทย์ต้นไม้ที่ออกบ่อยที่สุดข้อหนึ่ง

ต้นไม้ของนิพจน์

หน้า 17.3 คำนวณนิพจน์แบบ postfix ด้วย stack นิพจน์คณิตศาสตร์ทุกตัวเขียนเป็น binary tree ได้ เครื่องหมายเป็นโหนดที่มีลูกสองตัวคือตัวตั้งทางซ้ายกับทางขวา ตัวเลขเป็นใบ ภาพนี้คือ (8 + 2 * 5) / (6 - 4) ตัวเลขเล็กข้างวงกลมคือหมายเลขโหนด

ข้อมูลเข้าใช้แบบอาเรย์ลูกซ้ายลูกขวาจากหน้า 26.1 เพิ่มแค่ว่าแต่ละโหนดมีข้อความหนึ่งคำ บรรทัดแรกคือ N แล้วบรรทัดที่ v คือข้อความ ลูกซ้าย และลูกขวาของโหนด v รากคือโหนด 1

preorder inorder postorder

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

"ท่องต้นไม้ย่อยซ้าย" คือปัญหาเดิมที่เล็กลง จึงเขียนเป็น recursion แบบบทที่ 9 ได้ตรงตัว ต้นไม้ย่อยที่ว่างคือหมายเลข 0 ซึ่งเป็นกรณีฐาน

#include <bits/stdc++.h>
using namespace std;

vector<string> token;
vector<int> left_child, right_child;
vector<string> visited;

void preorder(int v)
{
    if (v == 0) { // (1)!
        return;
    }
    visited.push_back(token[v]); // (2)!
    preorder(left_child[v]);
    preorder(right_child[v]);
}

void inorder(int v)
{
    if (v == 0) {
        return;
    }
    inorder(left_child[v]);
    visited.push_back(token[v]);
    inorder(right_child[v]);
}

void postorder(int v)
{
    if (v == 0) {
        return;
    }
    postorder(left_child[v]);
    postorder(right_child[v]);
    visited.push_back(token[v]);
}

void print_and_clear() // (3)!
{
    for (int i = 0; i < (int)visited.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << visited[i];
    }
    cout << '\n';
    visited.clear();
}

int main()
{
    int n;
    cin >> n;
    token.resize(n + 1);
    left_child.resize(n + 1);
    right_child.resize(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> token[v] >> left_child[v] >> right_child[v];
    }
    preorder(1);
    print_and_clear();
    inorder(1);
    print_and_clear();
    postorder(1);
    print_and_clear();
    return 0;
}

1. โหนด 0 แปลว่าไม่มีโหนด ใบมีลูกเป็น 0 ทั้งสองข้าง การเรียกลงไปที่ลูกของใบจึงจบตรงนี้
2. สามฟังก์ชันต่างกันแค่ตำแหน่งของบรรทัดนี้ บนสุด ตรงกลาง หรือล่างสุด
3. เก็บโหนดที่ไปถึงลงใน vector ก่อน แล้วค่อยพิมพ์คั่นด้วยช่องว่าง จะได้ไม่มีช่องว่างเกินท้ายบรรทัด

9
/ 2 7
+ 3 4
8 0 0
* 5 6
2 0 0
5 0 0
- 8 9
6 0 0
4 0 0

/ + 8 * 2 5 - 6 4
8 + 2 * 5 / 6 - 4
8 2 5 * + 6 4 - /

สามบรรทัดคือนิพจน์เดียวกันที่เขียนสามแบบ

• postorder ได้ 8 2 5 * + 6 4 - / คือ postfix เอาไปป้อนโปรแกรม postfix ในหน้า 17.3 ได้ 9 ซึ่งถูกต้อง เพราะ postorder คำนวณลูกทั้งสองข้างเสร็จก่อนค่อยมาถึงเครื่องหมาย เหมือน postfix ที่ตัวเลขสองตัวมาก่อนเครื่องหมายเสมอ
• preorder ได้เครื่องหมายมาก่อนตัวเลข เรียกว่า prefix
• inorder ได้นิพจน์แบบที่เราเขียนกันปกติ แต่ไม่มีวงเล็บ 8 + 2 * 5 / 6 - 4 ถ้าอ่านตามกฎคูณหารก่อนจะได้ค่าอื่น ต้นไม้ไม่ต้องใช้วงเล็บ เพราะรูปร่างของมันบอกลำดับการคำนวณอยู่แล้ว

ทั้งสามแบบไปถึงแต่ละโหนดครั้งเดียว และเรียกฟังก์ชันกับโหนด 0 อีกไม่เกินสองครั้งต่อโหนด จึงใช้เวลา O(N) ลำดับเหล่านี้จะกลับมาอีกหลายครั้ง inorder ของต้นไม้ค้นหาในหน้า 26.4 ได้ค่าเรียงจากน้อยไปมาก และการคืนหน่วยความจำของทั้งต้นต้องใช้ postorder เพราะต้องคืนลูกก่อนพ่อ

ท่องทีละชั้นด้วย queue

preorder ดำดิ่งลงไปตามกิ่งซ้ายสุดก่อนแล้วค่อยย้อนกลับมา บางงานอยากได้โหนดเรียงตามชั้น รากก่อน แล้วทุกโหนดที่ลึก 1 แล้วทุกโหนดที่ลึก 2 เรียกว่า level order ใช้ queue จากบทที่ 17 เอารากเข้าคิว แล้ววนหยิบโหนดหน้าคิวออกมา ใส่ลูกทั้งหมดของมันต่อท้ายคิว ลูกเข้าคิวหลังทุกโหนดที่อยู่ชั้นเดียวกับพ่อเสมอ โหนดจึงออกจากคิวเรียงชั้นเอง

ใช้กับชมรมหุ่นยนต์ในหน้า 26.1 ที่อ่านเป็นพ่อของแต่ละโหนด

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = v;
        } else {
            children[p].push_back(v);
        }
    }
    vector<int> depth(n + 1, 0);
    queue<int> waiting;
    waiting.push(root);
    int current_level = -1; // (1)!
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        if (depth[v] != current_level) {
            if (current_level != -1) {
                cout << '\n';
            }
            current_level = depth[v];
            cout << "level " << current_level << ':';
        }
        cout << ' ' << v;
        for (int c : children[v]) {
            depth[c] = depth[v] + 1; // (2)!
            waiting.push(c);
        }
    }
    cout << '\n';
    return 0;
}

1. จำว่ากำลังพิมพ์ชั้นไหนอยู่ เจอโหนดที่ลึกกว่านั้นเมื่อไรแปลว่าขึ้นชั้นใหม่ ให้ขึ้นบรรทัดใหม่
2. ความลึกของลูกคือความลึกของพ่อบวกหนึ่ง และพ่อออกจากคิวก่อนลูกเสมอ ตอนที่ลูกถูกใช้ ความลึกจึงถูกตั้งไว้แล้ว

9
0 1 1 2 2 3 1 5 7

level 0: 1
level 1: 2 3 7
level 2: 4 5 6 9
level 3: 8

ตรงกับภาพในหน้า 26.1 ทุกชั้น ทุกโหนดเข้าคิวและออกจากคิวครั้งเดียว และดูรายชื่อลูกของตัวเองครั้งเดียว รวมเป็น O(N) การเดินแบบนี้มีชื่อว่า BFS (breadth-first search) บนต้นไม้ บทที่ 27 จะใช้ BFS กับกราฟทั่วไปที่เดินวนกลับมาโหนดเดิมได้ ซึ่งต้องมีวิธีกันการเข้าคิวซ้ำเพิ่ม ส่วนต้นไม้ที่เดินจากพ่อลงหาลูกอย่างเดียวไม่มีทางไปเจอโหนดเดิมซ้ำ

เร็วกว่าการเดินขึ้นแค่ไหน

หน้า 26.1 หาความลึกด้วยการเดินจากทุกโหนดขึ้นไปหาราก level order ได้ความลึกของทุกโหนดมาในตัว ลองวัดทั้งสองวิธีกับต้นไม้ N = 100000 โหนดสองแบบ แบบแรกสุ่มพ่อของแต่ละโหนด ได้ต้นไม้สูงแค่ 25 แบบที่สองเป็นเส้นตรงสูง 99999 วัดบนเครื่องเดียวกับหน้า 19.1 จับเวลาเฉพาะส่วนที่หาความลึก ไม่นับการอ่านข้อมูล ฝั่ง level order นับการสร้างรายชื่อลูกด้วย รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

กับต้นไม้สุ่ม วิธีเดินขึ้นเร็วกว่าด้วยซ้ำ เพราะแต่ละโหนดเดินแค่ราวสิบก้าว และไม่ต้องสร้างรายชื่อลูก แต่กับเส้นตรง วิธีเดินขึ้นต้องเดินราว 5 × 10⁹ ก้าว ช้ากว่าพันเท่า ถ้าลองแค่กับข้อมูลสุ่ม จะไม่มีทางรู้เลยว่าวิธีนี้ช้า ชุดทดสอบของโจทย์ต้นไม้แทบทุกข้อมีต้นไม้เส้นตรงยาวอยู่ด้วย เพราะเป็นกรณีที่ต้นไม้ลึกที่สุด ก่อนส่ง ให้ลองโปรแกรมกับเส้นตรงยาวทุกครั้ง

นับขนาดและความสูงด้วย recursion

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

• ขนาดของต้นไม้ย่อย v คือ 1 บวกขนาดของต้นไม้ย่อยของลูกทุกตัว
• ความสูงของ v คือ 0 ถ้าเป็นใบ ไม่งั้นคือความสูงมากสุดของลูกบวก 1
• ผลรวมของค่าในต้นไม้ย่อย v คือค่าของ v บวกผลรวมของต้นไม้ย่อยของลูกทุกตัว

ต้องรู้คำตอบของลูกก่อนพ่อ จึงเป็นลำดับแบบ postorder เรียกตัวเองกับลูกให้ครบก่อน แล้วค่อยรวม

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> children;
vector<int> subtree_size, height;

void measure(int v)
{
    subtree_size[v] = 1;
    height[v] = 0;
    for (int c : children[v]) {
        measure(c); // (1)!
        subtree_size[v] += subtree_size[c];
        height[v] = max(height[v], height[c] + 1); // (2)!
    }
}

int main()
{
    int n;
    cin >> n;
    children.resize(n + 1);
    subtree_size.resize(n + 1);
    height.resize(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = v;
        } else {
            children[p].push_back(v);
        }
    }
    measure(root);
    for (int v = 1; v <= n; v++) {
        cout << "node " << v << " size " << subtree_size[v] << " height " << height[v] << '\n';
    }
    return 0;
}

1. หลังบรรทัดนี้ subtree_size[c] และ height[c] ถูกต้องแล้ว เพราะ measure(c) ทำต้นไม้ย่อยของ c เสร็จทั้งต้นก่อนกลับมา
2. ใบไม่เข้าลูปนี้เลย ความสูงจึงค้างอยู่ที่ 0 ตามที่ตั้งไว้

9
0 1 1 2 2 3 1 5 7

node 1 size 9 height 3
node 2 size 4 height 2
node 3 size 2 height 1
node 4 size 1 height 0
node 5 size 2 height 1
node 6 size 1 height 0
node 7 size 2 height 1
node 8 size 1 height 0
node 9 size 1 height 0

โหนด 2 มีขนาด 4 คือตัวเองกับ 4 5 8 และสูง 2 จากทางลง 2 ไป 5 ไป 8 ตรงกับตารางคำศัพท์ในหน้า 26.1 ทุกโหนดถูกเรียกครั้งเดียว ใช้เวลา O(N) ถ้าทำแบบตรงไปตรงมาคือนับลูกหลานของแต่ละโหนดแยกกัน ต้นไม้เส้นตรงจะเป็น O(N²) เหมือนการเดินขึ้น

เส้นผ่านศูนย์กลางของต้นไม้

เส้นผ่านศูนย์กลางคือจำนวนเส้นของทางที่ยาวที่สุดระหว่างสองโหนดใดๆ ในต้นไม้ เช่น หมู่บ้านต่อกันด้วยถนนเป็นต้นไม้ อยากรู้ว่าสองหมู่บ้านที่ไกลกันที่สุดห่างกันกี่ช่วงถนน ในชมรมหุ่นยนต์ ทางจาก 8 ขึ้นไป 5 2 1 แล้วลงไป 7 9 ยาว 5 เส้น ไม่มีทางไหนยาวกว่านี้

ทางทุกทางในต้นไม้มีจุดสูงสุดหนึ่งโหนด คือโหนดที่ใกล้รากที่สุดบนทางนั้น จากจุดสูงสุดทางจะลงไปทางลูกไม่เกินสองตัว ถ้าเดาว่า v เป็นจุดสูงสุด ทางที่ยาวที่สุดคือลงไปทางลูกที่ลึกที่สุดสองตัว ความยาวคือ (ความสูงของลูกตัวแรก + 1) + (ความสูงของลูกตัวที่สอง + 1) ลองให้ทุกโหนดเป็นจุดสูงสุดแล้วเอาค่ามากสุด ระหว่างคำนวณความสูงในลำดับ postorder ก็ได้ข้อมูลครบพอดี

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> children;
vector<int> height;
int diameter = 0;

void measure(int v)
{
    int longest = 0, second = 0;
    for (int c : children[v]) {
        measure(c);
        int down = height[c] + 1; // (1)!
        if (down > longest) {
            second = longest;
            longest = down;
        } else if (down > second) {
            second = down;
        }
    }
    height[v] = longest;
    diameter = max(diameter, longest + second); // (2)!
}

int main()
{
    int n;
    cin >> n;
    children.resize(n + 1);
    height.resize(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = v;
        } else {
            children[p].push_back(v);
        }
    }
    measure(root);
    cout << "diameter " << diameter << '\n';
    return 0;
}

1. ทางที่ลงจาก v ผ่านลูก c ยาวเท่ากับเส้นจาก v ไป c หนึ่งเส้น บวกความสูงของ c เก็บค่ามากสุดสองอันดับแรกไว้ใน longest กับ second ถ้า v มีลูกตัวเดียว second เป็น 0 คือทางลงไปข้างเดียว
2. ทางที่มี v เป็นจุดสูงสุดยาว longest + second เทียบกับคำตอบที่ดีที่สุดที่เจอมา

9
0 1 1 2 2 3 1 5 7

diameter 5

ทุกโหนดถูกเรียกครั้งเดียว และดูลูกแต่ละตัวครั้งเดียว ทั้งหมดเป็น O(N) วิธีตรงไปตรงมาคือหาระยะจากทุกโหนดไปทุกโหนด ซึ่งเป็น O(N²) แบบฝึกหัดข้อ 8 เป็นโจทย์แบบนี้ที่ถนนแต่ละเส้นยาวไม่เท่ากัน

ลองทำให้พัง

แบบที่ 1 ลืมกรณีฐานของโหนด 0

ในโปรแกรม orders ลบสามบรรทัด if (v == 0) ออกจาก inorder เพราะคิดว่าทุกโหนดมีลูกอยู่แล้ว คอมไพล์ด้วย -Wall

orders.cpp:18:6: warning: infinite recursion detected [-Winfinite-recursion]
   18 | void inorder(int v)
      |      ^~~~~~~
orders.cpp:20:12: note: recursive call
   20 |     inorder(left_child[v]);
      |     ~~~~~~~^~~~~~~~~~~~~~~

compiler เห็นว่าทุกทางของฟังก์ชันเรียกตัวเองต่อเสมอ ไม่มีทางไหนจบ ถ้าดื้อรัน โปรแกรมพังด้วย

Process returned -1073741571 (0xC00000FD)

stack overflow แบบหน้า 9.1 พอลงไปถึงใบ ใบก็เรียก inorder(0) ต่อ และ inorder(0) ก็เรียก inorder(left_child[0]) ซึ่งคือ inorder(0) อีก ไม่มีวันจบ ทุกฟังก์ชันท่องต้นไม้ต้องเริ่มด้วยการตรวจว่าโหนดว่างหรือไม่ ถ้าใช้ pointer ก็ตรวจ nullptr

แบบที่ 2 คิดว่าทางที่ยาวที่สุดต้องผ่านราก

หลายคนหาเส้นผ่านศูนย์กลางด้วยการเอาความสูงของลูกที่ลึกที่สุดสองตัวของรากมาบวกกันเท่านั้น โปรแกรม diameter ที่แก้แบบนั้นยังได้ 5 กับชมรมหุ่นยนต์ เพราะทางที่ยาวที่สุดบังเอิญผ่านราก แต่ลองกับต้นไม้นี้ รากคือ 1 มีลูกตัวเดียวคือ 2 แล้ว 2 แตกเป็นสองกิ่งยาว

8
0 1 2 2 3 4 5 6

diameter 4

คำตอบที่ถูกคือ 6 ทางจาก 7 ขึ้นไป 5 3 2 แล้วลงไป 4 6 8 จุดสูงสุดของทางนี้คือโหนด 2 ไม่ใช่ราก รากมีลูกตัวเดียว ทางที่ผ่านรากจึงยาวได้แค่ 4 โปรแกรม diameter ตัวที่ถูกได้ 6 เพราะลองทุกโหนดเป็นจุดสูงสุด

สรุป

• preorder จดตัวเองก่อนลูก inorder จดระหว่างลูกซ้ายกับลูกขวา postorder จดหลังลูก ทั้งหมดเป็น O(N)
• postorder ของต้นไม้นิพจน์คือ postfix งานที่ต้องรู้คำตอบของลูกก่อนพ่อ เช่น ขนาด ความสูง ผลรวมของต้นไม้ย่อย ใช้ลำดับ postorder
• level order ใช้ queue ได้โหนดเรียงทีละชั้น และได้ความลึกของทุกโหนดใน O(N)
• เส้นผ่านศูนย์กลางคือค่ามากสุดของ "ลูกที่ลึกที่สุดสองตัว" ของทุกโหนด ไม่ใช่แค่ของราก
• ฟังก์ชันท่องต้นไม้ต้องตรวจโหนดว่างเป็นกรณีฐานเสมอ
• วิธีที่เร็วกับต้นไม้สุ่มอาจช้าพันเท่ากับต้นไม้เส้นตรง ทดสอบกับเส้นตรงยาวทุกครั้ง