ผลต่างระหว่างรุ่นของ "Psl/binary search trees"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 4: | แถว 4: | ||
* [http://www.comp.nus.edu.sg/~stevenha/visualization/bst.html bst ที่ visual algo] | * [http://www.comp.nus.edu.sg/~stevenha/visualization/bst.html bst ที่ visual algo] | ||
| − | ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node | + | ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้ |
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
| แถว 17: | แถว 17: | ||
}; | }; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | |||
| − | |||
== การเพิ่มข้อมูลใน bst (ไม่ balanced) == | == การเพิ่มข้อมูลใน bst (ไม่ balanced) == | ||
| แถว 35: | แถว 33: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| + | |||
| + | == การเก็บข้อมูลเพิ่มใน bst == | ||
== Balanced bst == | == Balanced bst == | ||
รุ่นแก้ไขเมื่อ 02:18, 9 กุมภาพันธ์ 2558
ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree
ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้
struct Node {
int val;
Node* left;
Node* right;
Node(int v, Node* l=0, Node* r=0)
: val(v), left(l), right(r)
{}
};
การเพิ่มข้อมูลใน bst (ไม่ balanced)
void insert(Node*& root, int x)
{
if(root == 0) {
root = new Node(x);
return;
}
if(x > root->val)
insert(root->right, x);
else if(x < root->val)
insert(root->left, x);
}
