[Coding: Java] ตัวอย่างคลาส Tree แบบง่าย

ต่อจากวันก่อนที่เราพูดถึง Data Structure แบบ Tree แบบคร่าวๆ กันมาแล้ว วันนี้เราจะมาลงเขียน Code ด้วย Java แบบง่ายๆ กัน

ต้องมี class อะไรบ้าง

สำหรับการสร้าง Tree คลาสหลักๆ ที่เราควรจะสนใจก่อนเลยก็คือ

class Tree{
 //ทำอะไรได้บ้างล่ะเนี่ย?
} 

แน่นอนล่ะ จะสร้าง Tree ก่อนอื่นก็ต้องมีคลาส Tree เสียก่อน

ทีนี้ Tree ของเราต้อง มีอะไร และ ทำอะไร ได้บ้าง?

มีอะไร (properties)

จากบทที่แล้ว เราได้รู้ว่าแต่ละก้อนของ Tree เราจะเรียกมันว่า Node ซึ่งเป็นช่องเอาไว้เก็บข้อมูลของเรา

ดังนั้น Tree ก็เลยต้องมี Node ... แล้ว Node เป็นยังไงล่ะ?

ในเมื่อเรายังไม่รู้ว่า Node เป็นไงก็สร้างคลาส Node ขึ้นมาอีกตัวละกัน

class Node{
 //ทำอะไรได้บ้างล่ะเนี่ย?
} 

คำ ถามเดิม! Nodeต้องมีอะไรบ้าง ... เมื่อกี้เพิ่งพูดไปว่ามันเอาไว้เก็บ data ของเราดังนั้นสิ่งแรกที่มันต้องมีก็คือ data (สร้างประเภทของ data นั้น เพื่อความง่าย ขอยกตัวอย่างว่าเราเก็บแต่ integer ละกัน)

แต่ว่านอกจาก data แล้วใน Node แต่ละตัวจำเป็นต้องรู้ว่า child node ของมันมีอะไรบ้าง เราจึงต้องเพิ่ม Node ตัวต่อไปด้วย

class Node{

   public int data;
   public Node leftChild = null, rightChild = null;
   public boolean visited = false;

   public Node() {
      data = -1;
   }

   public Node(int data) {
     this.data = data;
   }
}

เพิ่ม constructure ให้ ด้วยและตัวแถมอีกตัวนึงคือ visited เอาไว้ใช้สำหรับการค้นหาข้อมูล visited จะเอาไว้บอกได้ว่า Node ตัวนี้เคยค้นหาผ่านไปแล้วหรือยัง

กลับมาที่ Tree ถ้าจะให้เราเก็บ Node ทุกตัวก็คงจะไม่ไหว ในเมื่อ Node ทุกตัวมันเชื่อมกันอยู่ เราเก็บแค่หัวบนสุดก็พอแล้ว

class Tree{
    private Node root = null;
}

คำถามเดิม!

ทำอะไร (method)

method ที่ Tree ทำได้ก็มีประมาณ

• insert เพิ่มข้อมูลตัวใหม่เข้าไป
• find ค้นหาข้อมูลใน Tree
• delete ลบข้อมูลออกไป

เราก็เพิ่มเข้าไป

class Tree{
    private Node root = null;
 
    private void insert(type data){...}
    private type find(type data){...}
    private void delete(type data){...}

}

insert แบบ Binary Tree

การ insert ข้อมูลในกรณีที่ Tree ของเรากำหนดเป็นแบบ Binary Tree จะใช้คุณสมบัติของ Binary Tree ในการเลือกหาที่ลงให้ข้อมูลของเรา

โค้ดข้างล่างนี่เป็นตัวอย่างแบบหนึ่ง

public void insert(int data) {
    if (root == null) {
        root = new Node(data);
        return;
    }

   Node cur = root;

   while (cur != null) {

       //lookup left child
       if (cur.data > data) {
           if (cur.leftChild == null) {
               cur.leftChild = new Node(data);
               break;
          }
          else {
              cur = cur.leftChild;
          }
      }
      //lookup right child
      else {
          if (cur.rightChild == null) {
              cur.rightChild = new Node(data);
              break;
          }
          else {
              cur = cur.rightChild;
          }
      }
   }
}