thaiall logomy background

ทรี (Tree)

my town
datastructure | รหัสเทียม | เซต | คิว | สแตก | ลิงค์ลิสต์ | ทรี | จัดเรียง | กราฟ | งานมอบหมาย
ไบนารีทรี (Binary Tree)
ทรี (Tree) คือ โครงสร้างข้อมูลที่เป็นความสัมพันธ์ระหว่างโหนดที่ลดหลั่นกันตามลำดับชั้น คล้ายต้นไม้ หรือแผนผังองค์กรที่มีโหนดพ่อ (Parent node) และโหนดที่ต่ำลงมาเป็นสมาชิกเรียกว่าโหนดลูก (Child Node) ส่วนโหนดที่อยู่บนสุดและไม่มีโหนดพ่อเรียกว่าโหนดราก (Root node)
ไบนารีทรี (Binary Tree) 3 ประเภท 1. ไบนารีเสิร์ชทรี (Binary Search Tree) คือ ทรีที่มีโหนดในซับทรีด้านซ้ายน้อยกว่ารูทโหนด และโหนดในซับทรีด้านขวามีค่ามากกว่าหรือเท่ากับรูทโหนด และซับทรีต้องมีคุณสมบัติเป็นไบนารีเสิร์ชทรี
2. เอวีแอลเสิร์ชทรี (AVL Search Tree) คือ ทรีที่คิดค้นโดย G.M.Adelson-Velskii และ E.M.Landis โดยทรีแบบนี้จะมี ความสูงของซับทรี มาหักลบกันแล้วต้องมีค่าไม่มากกว่า 1
3. ฮีพทรี (Heap Tree) คือ ไบนารีทรีแบบสมบูรณ์หรือเกือบสมบูรณ์ ซึ่งโหนดพ่อจะมีค่ามากกว่าหรือเท่ากับซับทรีด้านซ้าย และด้านขวา


Code : Data Structures

ศัพท์เกี่ยวกับทรี (Term in Tree)
ต.ย. ทรี (Tree) 7 โหนด (Node)
ไบนารีทรีสมดุล (Balanced Tree)
[3]p.211
1. โหนดราก (Root Node) : 6
2. โหนดพ่อ (Parents Node) : 6, 2, 8 (โหนดที่มีลูก)
3. โหนดลูก (Children Node) : 2, 8, 1, 4, 7, 9 (โหนดที่มีพ่อ)
4. โหนดพี่น้อง (Sibling Node) : {2, 8}, {1, 4}, {7, 9} (เซตของโหนดลูก)
5. โหนดใบ (Leaf Node) : 1, 4, 7, 9 (โหนดที่ไม่มีลูก = External node)
6. ดีกรีทั้งหมดของทรี (Degree) : 6 (โหนดที่ไม่ใช่ Root node)
7. โหนดภายใน (Internal Node) : 2, 8 (โหนดที่ไม่ใช่ root และ leaf)
8. ระดับความสูง/ความลึกของทรี (Height) : 3
9. เขียนในวงเล็บ : 6 ( 2 ( 1 4 ) 8 ( 7 9 ) ) เป็นการเขียนแบบ prefix

preorder : 6 2 1 4 8 7 9
inorder : 1 2 4 6 7 8 9
postorder : 1 4 2 7 9 8 6
ท่องตามแนวนอน : 6 2 8 1 4 7 9

preorder : 9 2 1 4 8 7 6
inorder : 1 2 4 9 7 8 6
postorder : 1 4 2 7 6 8 9
ท่องตามแนวนอน : 9 2 8 1 4 7 6
Binary Tree
การแทนที่ Binary Tree ในหน่วยความจำ Array (P.231 - 235)
1. วิธีการท่องแบบแนวกว้าง (Breadth-First Traversals)
2. วิธีการท่องแบบแนวลึก (Depth-First Traversals)
2.1 แบบพรีออร์เดอร์ (Preorder traversal : NLR)
2.2 แบบอินออร์เดอร์ (Inorder traversal : LNR)
2.3 แบบโพสต์ออร์เดอร์ (Postorder traversal : LRN)
เอ็กซ์เพรสชั่นทรี (Expression Trees)
((a x (b + c)) + d) เขียน tree อย่างไร
post order : a b c + * d +
pre order : + * a + b c d
แล้ว 3 ตัวอย่างข้างล่างนี้
จะเขียน postorder, preorder และ binary tree อย่างไร
((a + b) * ((c - d) % e))
((a + b) % c)
(c % ((b + a) * (d + e))

C++ Sample
Binary Tree
ตัวอย่างนี้ แสดงการเขียน javascript ให้ทำงานแบบ tree อาจคัดลอกส่วนของ script ไปทดสอบที่ 1) webtoolkitonline.com 2) js.do 3) เขียนบน notepad จัดเก็บ แล้วทดสอบบน Browser หรือ 4) ส่ง code เข้า console ใน Browser : Developer tools
ตัวอย่างนี้ เรียกใช้ method tree.setNode ทั้งหมด 7 ครั้ง เพื่อสร้าง 7 Node รูปแบบ คือ tree.setNode(value, level, node); เช่น setNode(7,2,3); คือ ทำให้ค่า 7 อยู่ใน tree และอยู่ใน level ที่ 2 ใน nodeที่ 3 แต่ถ้า setNode(1,0,0); คือ ทำให้ค่า 1 อยู่ใน tree และอยู่ใน level ที่ 0 ใน nodeที่ 0 โดยโหนดแรกในแต่ละ level คือ 0 ดังนั้น node สุดท้ายของ level 2 ย่อมเป็น 3
// 1<<k is 2^k (อ่าน https://www.w3schools.com/jsref/jsref_operators.asp)
// เช่น x = 5 << 1 เท่ากับ 1010 << 1 คือ bit:left shift ดังนั้นผล คือ 0101 ค่าคือ 10
// เช่น x = 5 << 2 เท่ากับ 1010 << 2 คือ bit:left shift ดังนั้นผล คือ 00101 ค่าคือ 20
+ ตัวอย่าง tree_sample.htm ที่ยังไม่แปลภาษา
+ ตัวอย่าง tree_sample.htm แบบ unicode ใน github.com
+ ตัวอย่าง github.io + index.md สำหรับเผยแพร่ผลงาน
<script>
var tree=new BinaryTree();
tree.setNode(1,0,0); // (value, level, node)
tree.setNode(2,1,0); // ( 2 , 1 , 0 )
tree.setNode(3,1,1);
tree.setNode(4,2,0);
tree.setNode(5,2,1);
tree.setNode(6,2,2);
tree.setNode(7,2,3);
document.write("" + tree.level + tree.node); // ค่า 00 นั้น เมื่อเริ่มต้นจำนวน node ที่กำหนดไว้ คือ 0
document.write(tree.rightChild()); // ค่า 3 คือ right ของ 0,0
document.write("" + tree.level + tree.node); // ค่า 11 คือ ระดับที่ 1 และโหนดที่ 1 ซึ่ง value=3
document.write(tree.leftChild()); // ค่า 6 คือ ค่าลูกทางซ้ายของ node ที่ 3 
document.write("" + tree.level + tree.node + "
"); // ค่า 22 คือ ตำแหน่งของค่า 6 document.write(tree.root()); // 1 document.write("" + tree.level + tree.node); // ค่า 00 คือ ระดับที่ 0 และโหนดที่ 0 document.write(tree.getNodePow(0,0)); //1 document.write(tree.getNodePow(2,3)); //7 document.write(tree.btSMF(2,3) + "
"); // 6 document.write(tree.traverse()); // 1,2,4,5,3,6,7 คือการท่องแบบ preorder document.write("" + tree.level + tree.node + "
"); // ค่า 00 คือ ย้อนกลับไปที่จุดเริ่มต้น document.write(tree.leftChild()); // 2 document.write("" + tree.level + tree.node + "
"); // ค่า 10 คือ ตำแหน่งของค่า 4 document.write(tree.rightChild()); // 5 document.write("" + tree.level + tree.node + "
"); // ค่า 21 คือ ตำแหน่งของค่า 5 function BinaryTree() { // ฐานของ node เริ่มต้นที่ 0 ทั้ง level และ node this.level = 0; // current level we're on this.node = 0; // current node we're on // shift เป็น operator สำคัญ สำหรับ binary tree // shift-based formula works only on a binary tree. // 1<<k is 2^k (อ่าน https://www.w3schools.com/jsref/jsref_operators.asp) // so location = node + 2^level - 1 // "binary tree Storage Management Function" คือ ตำแหน่งปัจจุบันใน binary tree หาก root=0 // ตำแหน่งของ btSMF ก็จะเป็น 0,1,2,3,4,5,6 หากมี 3 ระดับ และนับ root เป็น level 0 this.btSMF = function(level, node) { return node + (1<<level) - 1; } // btSMF ใช้หาจำนวน node ของ binary tree ที่ไม่นับ root // btSMF (BT:Binary Tree Storage Management Function) // ใช้ Math.pow ช่วยในการยกกำลัง this.btSMFPow = function(level, node) { return node + Math.pow(2, level) - 1; // ไม่ต่างกับ return node + (1<<level) - 1; เค้าเล่าว่าใช้แบบไหนก็ได้ } // ประกาศพื้นที่เก็บ Nodes เป็น new array() this.Nodes = new Array(); // อ่านค่าของ node จาก binary tree และคืนค่ากลับไป // if level isn't supplied, return value of the current node this.getNode = function(level, node) { if (level === undefined) { return this.Nodes[this.btSMF(this.level, this.node)]; } else { return this.Nodes[this.btSMF(level, node)]; } } // กำหนดค่าที่รับมา ลงไปใน node ของ binary tree // if level argument is supplied use it, otherwise use current location level this.setNode = function(value, level, node) { if (level === undefined) { this.Nodes[this.btSMF(this.level, this.node)] = value; } else { this.Nodes[this.btSMF(level, node)] = value; } } // อ่านค่าของ node จาก binary tree และคืนค่ากลับไป // ซึ่งเหมือนกับ this.getNode และ getNodePow ไม่ถูกใช้ใน script นี้ // didn't implement node position effects in this version this.getNodePow = function(level, node) { return this.Nodes[this.btSMF(level, node)]; } // กำหนดค่าที่รับมา ลงไปใน node ของ binary tree เป็นอีกทางเลือกที่ใช้ Math.pow // didn't implement node position effects in this version this.setNodePow = function(value, level, node) { this.Nodes[this.btSMFPow(level, node)] = value; } // กำหนดตำแหน่งปัจจุบันของ root เป็น 0,0 // set the current position to the root: tree.root() // set the value at the root: tree.root(100) // get the value at the root: rootvalue = tree.root() // this one uses the bitshifted SMF this.root = function(value) { this.level = 0; this.node = 0; // if a value was supplied, set it if (value !== undefined) { this.Nodes[this.btSMF(this.level, this.node)] = value; // level 0, node 0 } // return the root node value return this.Nodes[this.btSMF(this.level, this.node)]; } // กำหนดตำแหน่งปัจจุบันของ root เป็น 0,0 และนี่ก็เป็นตัวอย่างการใช้ Math.pow // alternate version of root using Math.pow, just to double-check this.rootPow = function(value) { this.level = 0; this.node = 0; if (value !== undefined) { this.Nodes[this.btSMFPow(this.level, this.node)] = value; } return this.Nodes[this.btSMFPow(this.level, this.node)]; } // get the left child of a parent: tree.leftChild() // set the left child of a parent: tree.leftChild(6); this.leftChild = function(value) { this.level++; this.node = this.node * 2; // see diagram above if (value !== undefined) { this.Nodes[this.btSMF(this.level, this.node)] = value; } return this.Nodes[this.btSMF(this.level, this.node)]; } // same but for right child this.rightChild = function(value) { this.level++; this.node = this.node * 2 + 1; // see diagram above if (value !== undefined) { this.Nodes[this.btSMF(this.level, this.node)] = value; } return this.Nodes[this.btSMF(this.level, this.node)]; } // get the parent of the current node this.parent = function(value) { this.level--; this.node = this.node >> 1; // alternatively, Math.floor(this.node / 2) prolly if (value !== undefined) { this.Nodes[this.btSMF(this.level, this.node)] = value; } return this.Nodes[this.btSMF(this.level, this.node)]; } // ท่องเข้าไปใน binary tree แบบ preorder // recursively traverse the tree in an inner function this.traverse = function() { var that = this, // reference to the tree stack = new Array(); // store traversal results // recursive inner function that immediately executes from current node position (innerTraverse = function() { // push current node value onto the stack stack.push(that.getNode()); // if it has a left child, go there and traverse, then come back if (that.leftChild() !== undefined) { innerTraverse(); } that.parent(); // if it has a right child, go there and traverse, then come back if (that.rightChild() !== undefined) { innerTraverse(); } that.parent(); })(); // done recursing, return our array return stack; // ท่องเข้าไปโดยใช้แนวคิดแบบ stack } } </script>
Binary Tree ด้วย BCC 5.5
// C program for different tree traversals 
// https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
#include  
using namespace std; 

/* A binary tree node has data, pointer to left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 

/* Given a binary tree, print its nodes according to the "bottom-up" postorder traversal. */
void printPostorder(struct Node* node) 
{ 
  if (node == NULL) return; 
  // first recur on left subtree 
  printPostorder(node->left); 
  // then recur on right subtree 
  printPostorder(node->right); 
  // now deal with the node 
  cout << node->data << " "; 
} 

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct Node* node) 
{ 
  if (node == NULL) return; 
  /* first recur on left child */
  printInorder(node->left); 
  /* then print the data of node */
  cout << node->data << " "; 
  /* now recur on right child */
  printInorder(node->right); 
} 

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct Node* node) 
{ 
  if (node == NULL) return; 
  /* first print data of node */
  cout << node->data << " "; 
  /* then recur on left sutree */
  printPreorder(node->left); 
  /* now recur on right subtree */
  printPreorder(node->right); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(1); 
  root->left = new Node(2); 
  root->right = new Node(3); 
  root->left->left	 = new Node(4); 
  root->left->right = new Node(5); 
  cout << "\nPreorder traversal of binary tree is \n"; 
  printPreorder(root); 
  cout << "\nInorder traversal of binary tree is \n"; 
  printInorder(root); 
  cout << "\nPostorder traversal of binary tree is \n"; 
  printPostorder(root); 
  return 0; 
} 
Output:
Preorder traversal of binary tree is
1 2 4 5 3 
Inorder traversal of binary tree is
4 2 5 1 3 
Postorder traversal of binary tree is
4 5 2 3 1
Binary Tree : Simulator
Click เพื่อทดสอบ

Code : https://codepen.io/m10digital/pen/egmJev
Web guides
+ http://embed.plnkr.co/NauLDO/
+ http://www.i-programmer.info
เอกสารฉบับเต็ม (Full Text)

รศ.ดร.สมชาย ประสิทธิ์จูตระกูล

Mark Allen Weiss

A Byte of Python
เอกสารอ้างอิง (Reference) [1] นิรุธ อำนวยศิลป์, "โครงสร้างข้อมูล : การเขียนโปรแกรมและการประยุกต์", บริษัท ดวงกมลสมัย จำกัด., กรุงเทพฯ, 2548.
[2] Guy J.Hale, Richard J.Easton, "Applied Daa Structures Using Pascal", D.C.Heath and Company. Canada. 2530.
[3] โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.
[4] วิวัฒน์ อภิสิทธิ์ภิญโญ, อมร มุสิกสาร, "โครงสร้างข้อมูล (Data Structures)", บริษัท เอ-บุ๊ค ดิสทริบิวชั่น จำกัด., กรุงเทพฯ, 2548.
[5] เนรมิต ชุมสาย ณ อยุธยา, "เรียนรู้โครงสร้างข้อมูลและอัลกอริทึมด้วย Java", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2550.
[6] ขนิษฐา นามี, "โครงสร้างข้อมูลและอัลกอริทึม", บริษัท ไอดีซี อินโฟ ดิสทริบิวเตอร์ เซ็นเตอร์ จำกัด., กรุงเทพฯ, 2548.
[7] Michael McMillan, "Data Structures and Algorithms with JavaScript", O’Reilly Media, Inc., USA., 2014.
[8] Loiane Groner, "Learning JavaScript Data Structures and Algorithms", Packt Publishing, 2014.
Thaiall.com