কনটেন্টে যান

Tree traversal — একই গাছ, চারভাবে পড়া

অধ্যায়ের সূচি · সহজ ব্যাখ্যা ও বাস্তব ব্যবহার · অনুশীলন ও সমাধান

এই ছয়টি node-ই প্রতিবার থাকবে। বদলাবে শুধু কখন একটি node-এর value উত্তরে লিখব। এটি একটি binary search tree (BST): বাম subtree-র মান ছোট, ডান subtree-র মান বড়।

flowchart TD
  n8((8)) -->|বাম| n3((3))
  n8 -->|ডান| n10((10))
  n3 -->|বাম| n1((1))
  n3 -->|ডান| n6((6))
  n10 -->|ডান| n14((14))

চারটি traversal এক নজরে

নিচের প্রতিটি বাক্স একটি visit। বাক্সের ক্রমই সম্পূর্ণ output; কোনো node বাদ যায়নি।

একই tree-এর চারটি output

  1. Inorder — বাম, নিজে, ডান

    1
    3
    6
    8
    10
    14

    BST হওয়ায় মানগুলো ছোট থেকে বড় হয়েছে।

  2. Preorder — নিজে, বাম, ডান

    8
    3
    1
    6
    10
    14

    Parent-এর পরে তার সন্তানগুলো আসে।

  3. Postorder — বাম, ডান, নিজে

    1
    6
    3
    14
    10
    8

    দুই subtree শেষ হওয়ার পরে parent আসে।

  4. Level order — এক স্তর শেষ করে পরের স্তর

    8
    3
    10
    1
    6
    14

    স্তরগুলো হলো 8; তারপর 3 ও 10; শেষে 1, 6 ও 14।

Traversal Value লেখার সময় কোথায় কাজে লাগে
Inorder বাম subtree শেষ হলে BST-এর মান sorted order-এ পড়া
Preorder node-এ পৌঁছেই Tree copy, structure-সহ serialization
Postorder দুই subtree শেষ হলে Height, subtree sum, child-এর ফল জোড়া দেওয়া
Level order queue থেকে বের করলে প্রতি level-এর তথ্য, নিকটতম node খোঁজা

সাধারণ binary tree-তে inorder করলেই sorted output আসে না; এর জন্য BST-এর নিয়ম দরকার। আর শুধু preorder value দিয়ে সাধারণ binary tree পুনর্গঠন করা যায় না—অনুপস্থিত child বোঝাতে null marker বা অন্য structure-তথ্য লাগে। Serialization-এর পূর্ণ নোট।

Inorder-এ ফিরে আসার মুহূর্তটি ধরো

প্রথমে 8 থেকে বাঁয়ে 3, তারপর বাঁয়ে 1-এ নামি। কোনো subtree শেষ হলে যে node থেকে এসেছিলাম সেখানে ফিরে যাই।

Visit তার আগে কী শেষ হলো এখন লেখা value এরপর
1 1-এর বাম child নেই 1 1-এর ডান child-ও নেই; 3-এ ফিরি
2 3-এর বাম subtree 3 ডান child 6-এ যাই
3 6-এর বাম child নেই 6 6 শেষ; 3 হয়ে 8-এ ফিরি
4 8-এর পুরো বাম subtree 8 ডান child 10-এ যাই
5 10-এর বাম child নেই 10 ডান child 14-এ যাই
6 14-এর বাম child নেই 14 আর কোনো কাজ বাকি নেই

তিনটি depth-first traversal-এ যাওয়া-ফেরার পথ একই। Preorder পৌঁছানোর সময়, inorder দুই subtree-র মাঝখানে এবং postorder ফেরার আগে value লেখে।

Node Inorder-এ অবস্থান Preorder-এ অবস্থান Postorder-এ অবস্থান
8 4 1 6
3 2 2 3
1 1 3 1
6 3 4 2
10 5 5 5
14 6 6 4

Level order-এ queue কেন লাগে

Queue-এর সামনে থেকে একটি node নিই, তারপর তার বাম ও ডান child পেছনে যোগ করি। নিচে queue-এর বাম দিক front।

ধাপ বের হলো পেছনে যোগ হলো কাজের পরে queue
শুরু — 8 [8]
1 8 3, 10 [3, 10]
2 3 1, 6 [10, 1, 6]
3 10 14 [1, 6, 14]
4 1 কিছু নেই [6, 14]
5 6 কিছু নেই [14]
6 14 কিছু নেই []

পরের level-এর child-গুলো পেছনে থাকে। তাই বর্তমান level শেষ না করে পরের level শুরু হতে পারে না। Stack ব্যবহার করলে এই ক্রম থাকবে না; তখন একটি পথ ধরে গভীরে যাওয়া হবে।

Postorder দিয়ে height হিসাব

এখানে height মানে নিচের সবচেয়ে দূরের leaf পর্যন্ত edge-এর সংখ্যা। খালি subtree-র height −1, leaf-এর height 0। প্রতিটি parent-এর সূত্র: 1 + max(left_height, right_height)।

flowchart BT
  n1["1: height 0"] --> n3["3: 1 + max(0, 0) = 1"]
  n6["6: height 0"] --> n3
  n14["14: height 0"] --> n10["10: 1 + max(-1, 0) = 1"]
  n3 --> n8["8: 1 + max(1, 1) = 2"]
  n10 --> n8

এই ছবির arrow হিসাবের ফল উপরে যাওয়া বোঝায়। আগে 1 ও 6-এর ফল পেয়ে 3-এর height, আগে 14-এর ফল পেয়ে 10-এর height, সবশেষে 8-এর height হিসাব করি। এটাই postorder কাজে লাগার কারণ।

নিজে যাচাই করো

  1. Root 8-এর ডান child 10-এর বদলে 9 হলে কোন output বদলাবে? নিজে চারটি traversal লেখো।
  2. 6-এর নিচে নতুন child যোগ হলে কোন কোন node-এর height আবার হিসাব করতে হবে?
  3. প্রতি level-এর সর্বোচ্চ মান পেতে কোন traversal নেবে, এবং কেন?

পরের পাঠ: Traversal patterns—প্রশ্ন দেখে সঠিক traversal বেছে নেওয়া।