คู่มือโอลิมปิกคอมพิวเตอร์

Binary Tree

คำอธิบาย

• tree เป็นโครงสร้างข้อมูลแบบมีชนชั้น ซึ่งแตกต่างจาก array, linked list, stack และ queue ที่เป็นโครงสร้างเชิงเส้น

• ตัวอย่าง tree เบื้องต้นคือ binary tree โดยแต่ละ node สามารถมีลูกได้มากที่สุดไม่เกิน 2 ลูก ดังรูป

• ซึ่งเราสามารถเรียกลูกว่า left และ right child ได้

คำศัพท์

• node ด้านบนสุดจะถูกเรียกว่า root

• ลูกด้านล่างที่อยู่ติดกับ node โดยตรงจะเรียกว่า children

• node ด้านบนจะเรียกว่า parent

• เช่น a เป็น child ของ f และ f เป็น parent ของ a

• และ node ที่ไม่มีลูกเลยจะเรียกว่า leaves

      tree
      ----
       j    <-- root
     /   \
   f      k
 /   \      \
a     h      z    <-- leaves

เมื่อไรถึงใช้ tree?

• หากต้องการเก็บข้อมูลที่มีลำดับขั้น เช่น ระบบไฟล์ในคอมพิวเตอร์

file system
-----------
     /    <-- root
   /      \
 ...       home
        /          \
     ugrad        course
      /       /      |     \
   ...      cs101  cs112  cs113

• tree (ประกอบกับ ordering บางอย่าง e.g., BST) สามารถเข้าถึงข้อมูลได้เร็วกว่า linear data structure

• tree สามารถเพิ่มลบข้อมูลได้สะดวกกว่าในบางกรณี

• tree สามารถ implement ในรูปแบบคล้ายกับ linked list ได้

Binary Tree

• คือ tree ที่แต่ละ node มีลูกไม่เกินสองลูก คือ left และ right

ตัวอย่าง

• Binary Tree node มีส่วนประกอบต่อไปนี้

  • ข้อมูล

  • Pointer to left child

  • Pointer to right child

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

struct Node {
  int data;
  struct Node *left;
  struct Node *right;

  // val is the key or the value that
  // has to be added to the data part
  Node(int val) {
    data = val;

    // Left and right child for node
    // will be initialized to null
    left = NULL;
    right = NULL;
  }
};

int main() {
  /*create root*/
  struct Node *root = new Node(1);
  /* following is the tree after above statement

     1
     / \
     NULL NULL
   */

  root->left = new Node(2);
  root->right = new Node(3);
  /* 2 and 3 become left and right children of 1
     1
     / \\
     2     3
     / \\    /  \\
     NULL NULL NULL NULL
   */

  root->left->left = new Node(4);
  /* 4 becomes left child of 2
        1
     /     \\
     2        3
     / \\     / \\
     4 NULL NULL NULL
     / \\
     NULL NULL
   */

  return 0;
}

ใช้ array ในการสร้าง binary tree

• ขนาดเรารู้ขนาดของ binary tree แล้วเราสามารถใช้ array ได้

• Consider node A[i] has

  • A[i*2] as left child

  • A[i*2+1] as right child