DataStructure.js

去年照着严蔚敏的《数据结构》写了这个脚本，用Javascript实现了栈、队列、链表、树和二叉树。后来在工作中没发现能派上什么用场，丢在一边很久也没理会。今天偶然翻了一下觉得有些写得还挺有意思的。
例如求树的所有叶子节点数。

  1. 递归解法：
  2. getLeafCount:function(){
  3.     var _count = 0;
  4.     for(var i in this.children){
  5.         if(this.children[i].hasChild()) 
  6.             _count += this.children[i].getLeafCount();
  7.         else 
  8.             _count++;
  9.     }
  10.     return _count;
  11. }
  12. 使用堆栈的非递归解法：
  13. getLeafCount:function()
  14. {
  15.     var _stack = new BX.DataStructure.Stack();
  16.     var _tree = this;
  17.     var _count = 0;
  18.     while(_tree != null)
  19.     {
  20.         for(var i = 0; i < _tree.children.length; i++)
  21.             {
  22.                 if(_tree.children[i].hasChild()) 
  23.                     _stack.push(_tree.children[i]);
  24.                 else 
  25.                     _count++;
  26.             }
  27.         _tree = _stack.pop();
  28.     }
  29.     return _count;
  30. }
  31. 使用队列的非递归解法：
  32. getLeafCount:function()
  33. {
  34.     var _queue = new BX.DataStructure.Queue();
  35.     var _tree = this;
  36.     var _count = 0;
  37.     while(_tree != null)
  38.     {
  39.         for(var i = 0; i < _tree.children.length; i++)
  40.         {
  41.             if(_tree.children[i].hasChild()) 
  42.                 _queue.enQueue(_tree.children[i]);
  43.             else 
  44.                 _count++;
  45.         }
  46.         _tree = _queue.deQueue();
  47.     }
  48.     return _count;
  49. }

又如求二叉树同一深度的所有子节点。

  1. 广度优先(Queue实现)
  2. getChildrenByDepth:function(depth)
  3. {
  4.     if(depth < 1) return null;
  5.     if(depth == 1) return new Array(this);
  6.     var _queue = new BX.DataStructure.Queue();
  7.     //同一层元素的个数队列，对头为同一层元素的个数
  8.     var _depthQueue = new BX.DataStructure.Queue();
  9.     var _children = [];
  10.     var _treeNode = null;
  11.     var _depth = 1;
  12.     var _count = 0;
  13.     _queue.enQueue(this);
  14.     while(!_queue.isEmpty())
  15.     {
  16.         if(_depth == depth) { _children = _queue.elements; break;}
  17.         else
  18.         {
  19.             _depthQueue.enQueue(_queue.getLength());
  20.             _treeNode = _queue.deQueue();
  21.             if(_treeNode.hasLeftChild()) _queue.enQueue(_treeNode.leftChild);
  22.             if(_treeNode.hasRightChild()) _queue.enQueue(_treeNode.rightChild);
  23.             _count++;
  24.             //当计数等于同一层元素个数的时候，_depthQueue置0，下一次循环时推入下一层的个数
  25.             if(_count == _depthQueue.getHead())
  26.             {
  27.                 _depth++;
  28.                 _count = 0;
  29.                 _depthQueue.clear();
  30.             }
  31.         }
  32.     }
  33.     return _children;
  34. }
  35.  
  36. 深度优先(Stack实现)
  37. getChildrenByDepth:function(depth)
  38. {
  39.     if(depth < 1) return null;
  40.     if(depth == 1) return new Array(this);
  41.     var _stack = new BX.DataStructure.Stack();
  42.     var _depthStack = new BX.DataStructure.Stack();
  43.     var _children = [];
  44.     var _treeNode = null;
  45.     var _currentDepth = 1;
  46.     var isMatched = false;
  47.     _stack.push(this);
  48.     _depthStack.push(_currentDepth);
  49.     while(!_stack.isEmpty())
  50.     {
  51.         //元素和该元素相应的深度同时出栈
  52.         _treeNode = _stack.pop();
  53.         _currentDepth = _depthStack.pop();
  54.        
  55.         if(_treeNode.hasLeftChild() || _treeNode.hasRightChild()) 
  56.             _currentDepth++;
  57.         //判断是否到达所求深度，如果是则添加到_children数组，否则当前深度和子元素都入栈
  58.         isMatched = _currentDepth == depth ? true : false;
  59.         if(_treeNode.hasLeftChild())
  60.         {
  61.             if(isMatched) _children.push(_treeNode.leftChild);
  62.             else
  63.             {
  64.                 _stack.push(_treeNode.leftChild);
  65.                 _depthStack.push(_currentDepth);
  66.             }
  67.         }
  68.         if(_treeNode.hasRightChild())
  69.         {
  70.             if(isMatched) _children.push(_treeNode.rightChild);
  71.             else
  72.             {
  73.                 _stack.push(_treeNode.rightChild);
  74.                 _depthStack.push(_currentDepth);
  75.             }
  76.         }
  77.     }
  78.     return _children;
  79. }

脚本在线地址：http://panweizeng.com/others/DataStructure.js

[ 分类: 学习 Learning ] 由 Pan 发表于 April 6, 2008 2:59 pm  固定链接 

《DataStructure.js》 这篇文章一共有2 条评论   我也想说两句

  1. Heibaizhao

    April 24, 2008 2:54 am

    这个代码高亮很漂亮啊，请问是什么插件？

  2. Freeman. Pan

    April 26, 2008 9:50 am

    to Heibaizhao:
    WordPress的CoolCode插件
    http://www.coolcode.cn/show-26-1.html

RSS feed for comments on this post. TrackBack URI

相关文章：

发表评论