ทรี (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>

// 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