Binary Tree in C

Binary tree เป็นอีกรูปแบบนึ่งของการจัดเก็บข้อมูล

Binary tree แต่ละ node จะเก็บข้อมูลของตัวเองและ pointer 2 ตัว เอาไว้ชี้ไปยัง node ซ้ายและขวา
จุดเริ่มต้นของ binary tree เรียกว่า root
node ลูกซ้ายเรียก left subtree node ลูกขวาเรียก right subtree
node ที่ไม่มีลูกต่อเรียก leaf

การนำ binary tree ไปใช้งาน

จะยกตัวอย่างการจัดเก็บข้อมูลตัวเลขโดยเรียงให้ตัวเลยน้อยกว่าหรือเท่ากันให้เป็น left subtree ส่วนถ้ามีค่ามากกว่าให้ เป็น right subtree

สร้าง struct ที่จะเอาไว้เก็บข้อมูลของเรา

typedef struct node{
 int value;
 struct node *left,*right;
} NODE;

สร้าง function เพื่อนำข้อมูลมาสร้าง tree

กรอบเหลืองถ้าไม่มีให้ newnode เป็น root ไปเลย
กรอบสีน้ำเงิน ถ้าค่าที่ใส่มากกว่าให้ใส่ข้อมูลทางขวาเลยถ้าว่างแต่ถ้าไม่ว่าจะเรียก function ตัวเองอีกรอบทำไปจนเจอ NULL แล้วค่อยเติม
กรอบสีเขียนก็เช่นกันเพียงแค่ถ้าค่าน้อยกว่าหรือเท่ากันให้ไปทางซ้าย

การที่ function เรียน function ตัวเองซ้ำเรียกการทำแบบนี้ว่า Recursion

ในตอนแรกเรา run insertnode(&root,25);

ในการทำงานเนื่องจากทางขวามี node ต่อทำให้ต้องเรียกตัวเองซ้ำโดน
insertnode(&((*root)->right),25);
จะเห็นว่ามันมากว่า 20 และด้านขวายังไงมี node ต่อก็ต้องเรียนตัวเองซ่ำอีกจนกว่าจะเจอ NULL

เมื่อว่าถึงตำแน่งที่ไม่มี node ต่อแล้วก็ให้เอา node ที่เราสร้างขึ้นมาเอาไปต่อ
ค่าของเราน้อยกว่า 30 ดังนั้นก็ให่ต่อไปด้านซ้าย

ขอดีของการเก็บข้อมูลที่เราเรียกกันด้วยวิธีแบบนี้

ปกติการค้นหาค่าหากเก็บข้อมูลปกติเราต้อง loop ไล่ไปจากหัวจนกว่าจะเจอ แต่ binary tree ทำให้เราหาข้อมูลเจอได้ไว้กว่าเพราะการเทียบค่าจะทำให้จำนวนข้อมูลลดลงได้สูงสุดครึ่งนึงของ tree ในทุกๆครั้ง

จากภาพเราทำการค้นหา 5 ใน tree ของเราการเทียบครั้งแรกทำให้เราตัด tree ฝั่งขวาออกไปได้เลยเนื่องจากค่ามากกว่าอยู่แล้ว ทำให้เราลดเวลาให้การค้นหาได้หากเจอข้อมูลจำนวนมากๆ

int search(TREE *root,int value){
    if(*root!=NULL){
        if(value!=(*root)->value){
            if(value>(*root)->value){
                bs(&((*root)->right),value);
            }else{
                bs(&((*root)->left),value);
            }
        }else{
            return 1;
        }
    }else{
        return 0;
    }
}