js:数据结构笔记9--二叉树

时间：2014-10-18 12:22:46 收藏：0 阅读：308

树：以分层的方式存储数据；节点：根节点，子节点，父节点，叶子节点（没有任何子节点的节点）；层：根节点开始0层；

二叉树：每个节点子节点不超过两个；查找快（比链表），添加，删除快（比数组）；

BST：二叉树查找：

设置根节点为当前节点；
如果要插入的节点小于当前节点，则设置其左节点为新的当前节点；大于的话选右节点；
如果如果选择的节点为null，则将要插入的节点放在这个位置，退出；否则继续向下查找；

实现的基本代码：

 function Node (data,left,right) {
   this.data = data;
   this.show = sh
 }
 function show() {
   console.log(this.data);
 }
 function BST() {
   this.root = root;
   this.insert = insert;
 }
 function insert(data) {
   var n = new Node(data,null,null);
   if(this.root === null) {
     this.root = n;
  } else {
     var currNode =  this.root,parent;
     while(true) {
       parent = currNode;
       if(data < currNode.data) {
         currNode = currNode.left;
         if(currNode === null) {
           parent.left = n;
           break;
         }
       } else {
         currNode = currNode.right;
         if(currNode === null) {
           parent.right = n;
           break;
         }
       }
     }
   }
 }

原文：http://www.cnblogs.com/jinkspeng/p/4032769.html