ทรี (Tree)
ไบนารีทรี (Binary Tree)

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

Binary Tree
<script>
var tree=new BinaryTree();
tree.setNode(1,0,0);
tree.setNode(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.rightChild()); // 3
document.write(tree.leftChild()); // 6
document.write(tree.root()); // 1
document.write(tree.getNode(0,0)); //1
document.write(tree.getNode(2,3)); //7
document.write(tree.btSMF(2,3)); // 6
document.write(tree.traverse()); // 1,2,3,4,5,6,7

function BinaryTree() {

  // for node-based navigation
  this.level = 0; // current level we're on
  this.node = 0;  // current node we're on

  // shift-based formula works only on a binary tree.
  // 1<<k is 2^k
  // so location = node + 2^level - 1
  // "binary tree Storage Management Function"
  this.btSMF = function(level, node) {
    return node + (1<<level) - 1;
  }
  
  // I think this is the easier-to-grok equivalent with Math.pow...
  this.btSMFPow = function(level, node) {
    return node + Math.pow(2, level) - 1;
  }
  
  // where we keep 'em
  this.Nodes = new Array();
  
  // get a node using the bit-shift
  // 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)];
    }
  }
  
  // set a node using the bit-shift
  // 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;  
    }
  }
  
  // get a node using the Math.pow alternative
  // didn't implement node position effects in this version
  this.getNodePow = function(level, node) {
    return this.Nodes[this.btSMF(level, node)];    
  }
  
  // set a node using the Math.pow alternative
  // didn't implement node position effects in this version
  this.setNodePow = function(value, level, node) {
    this.Nodes[this.btSMFPow(level, node)] = value;
  }
  
  // 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)];
  }
  
  // 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)];
  }
  
  // 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;
  }
  
}
</script>
http://embed.plnkr.co/NauLDO/ - ok
http://www.i-programmer.info/programming/javascript/1899-javascript-data-structures-the-binary-tree.html
เอกสารฉบับเต็ม (Full Text)

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

Bruno R. Preiss

Mark Allen Weiss

William H. Ford

DB: พัฒณืรพี

Michael Mcmillan
เอกสารอ้างอิง (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.


"Imagination is more important than knowledge" - Albert Einstein
http://goo.gl/72BPC