dojox/collections/BinaryTree.js

  • Provides:

    • dojox.collections.BinaryTree
  • Requires:

    • dojox.collections._base in common
  • dojox.collections.BinaryTree.TraversalMethods

    • type
      Object
    • summary
  • dojox.collections.BinaryTree.TraversalMethods.Preorder

    • summary
  • dojox.collections.BinaryTree

    • type
      Function
    • parameters:
      • data: (typeof )
    • source: [view]
       function node(data, rnode, lnode){
        this.value=data||null;
        this.right=rnode||null;
        this.left=lnode||null;
        this.clone=function(){
         var c=new node();
         if(this.value.value){
          c.value=this.value.clone();
         }else{
          c.value=this.value;
         }
         if(this.left!=null){
          c.left=this.left.clone();
         }
         if(this.right!=null){
          c.right=this.right.clone();
         }
         return c;
        }
        this.compare=function(n){
         if(this.value>n.value){ return 1; }
         if(this.value   return 0;
        }
        this.compareData=function(d){
         if(this.value>d){ return 1; }
         if(this.value   return 0;
        }
       }


       function inorderTraversalBuildup(current, a){
        if(current){
         inorderTraversalBuildup(current.left, a);
         a.push(current.value);
         inorderTraversalBuildup(current.right, a);
        }
       }


       function preorderTraversal(current, sep){
        var s="";
        if (current){
         s=current.value.toString() + sep;
         s+=preorderTraversal(current.left, sep);
         s+=preorderTraversal(current.right, sep);
        }
        return s;
       }
       function inorderTraversal(current, sep){
        var s="";
        if (current){
         s=inorderTraversal(current.left, sep);
         s+=current.value.toString() + sep;
         s+=inorderTraversal(current.right, sep);
        }
        return s;
       }
       function postorderTraversal(current, sep){
        var s="";
        if (current){
         s=postorderTraversal(current.left, sep);
         s+=postorderTraversal(current.right, sep);
         s+=current.value.toString() + sep;
        }
        return s;
       }

       
       function searchHelper(current, data){
        if(!current){ return null; }
        var i=current.compareData(data);
        if(i==0){ return current; }
        if(i>0){ return searchHelper(current.left, data); }
        else{ return searchHelper(current.right, data); }
       }


       this.add=function(data){
        var n=new node(data);
        var i;
        var current=root;
        var parent=null;
        while(current){
         i=current.compare(n);
         if(i==0){ return; }
         parent=current;
         if(i>0){ current=current.left; }
         else{ current=current.right; }
        }
        this.count++;
        if(!parent){
         root=n;
        }else{
         i=parent.compare(n);
         if(i>0){
          parent.left=n;
         }else{
          parent.right=n;
         }
        }
       };
       this.clear=function(){
        root=null;
        this.count=0;
       };
       this.clone=function(){
        var c=new dojox.collections.BinaryTree();
        var itr=this.getIterator();
        while(!itr.atEnd()){
         c.add(itr.get());
        }
        return c;
       };
       this.contains=function(data){
        return this.search(data) != null;
       };
       this.deleteData=function(data){
        var current=root;
        var parent=null;
        var i=current.compareData(data);
        while(i!=0&¤t!=null){
         if(i>0){
          parent=current;
          current=current.left;
         }else if(i<0){
          parent=current;
          current=current.right;
         }
         i=current.compareData(data);
        }
        if(!current){ return; }
        this.count--;
        if(!current.right){
         if(!parent){
          root=current.left;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=current.left; }
          else if(i<0){ parent.right=current.left; }
         }
        }
        else if(!current.right.left){
         if(!parent){
          root=current.right;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=current.right; }
          else if(i<0){ parent.right=current.right; }
         }
        }
        else{
         var leftmost=current.right.left;
         var lmParent=current.right;
         while(leftmost.left!=null){
          lmParent=leftmost;
          leftmost=leftmost.left;
         }
         lmParent.left=leftmost.right;
         leftmost.left=current.left;
         leftmost.right=current.right;
         if(!parent){
          root=leftmost;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=leftmost; }
          else if(i<0){ parent.right=leftmost; }
         }
        }
       };
       this.getIterator=function(){
        var a=[];
        inorderTraversalBuildup(root, a);
        return new dojox.collections.Iterator(a);
       };
       this.search=function(data){
        return searchHelper(root, data);
       };
       this.toString=function(order, sep){
        if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
        if(!sep){ sep=","; }
        var s="";
        switch(order){
         case dojox.collections.BinaryTree.TraversalMethods.Preorder:
          s=preorderTraversal(root, sep);
          break;
         case dojox.collections.BinaryTree.TraversalMethods.Inorder:
          s=inorderTraversal(root, sep);
          break;
         case dojox.collections.BinaryTree.TraversalMethods.Postorder:
          s=postorderTraversal(root, sep);
          break;
        };
        if(s.length==0){ return ""; }
        else{ return s.substring(0, s.length - sep.length); }
       };


       this.count=0;
       var root=this.root=null;
       if(data){
        this.add(data);
       }
    • summary
  • dojox.collections.BinaryTree.value

    • summary
  • dojox.collections.BinaryTree.right

    • summary
  • dojox.collections.BinaryTree.left

    • summary
  • dojox.collections.BinaryTree.count

    • summary
  • dojox.collections.BinaryTree.root

    • summary
  • dojox.collections.BinaryTree.clone

    • type
      Function
    • source: [view]
        var c=new dojox.collections.BinaryTree();
        var itr=this.getIterator();
        while(!itr.atEnd()){
         c.add(itr.get());
        }
        return c;
    • summary
  • dojox.collections.BinaryTree.compare

    • type
      Function
    • parameters:
      • n: (typeof )
    • source: [view]
         if(this.value>n.value){ return 1; }
         if(this.value   return 0;
    • summary
  • dojox.collections.BinaryTree.compareData

    • type
      Function
    • parameters:
      • d: (typeof )
    • source: [view]
         if(this.value>d){ return 1; }
         if(this.value   return 0;
    • summary
  • dojox.collections.BinaryTree.add

    • type
      Function
    • parameters:
      • data: (typeof )
    • source: [view]
        var n=new node(data);
        var i;
        var current=root;
        var parent=null;
        while(current){
         i=current.compare(n);
         if(i==0){ return; }
         parent=current;
         if(i>0){ current=current.left; }
         else{ current=current.right; }
        }
        this.count++;
        if(!parent){
         root=n;
        }else{
         i=parent.compare(n);
         if(i>0){
          parent.left=n;
         }else{
          parent.right=n;
         }
        }
    • summary
  • dojox.collections.BinaryTree.clear

    • type
      Function
    • source: [view]
        root=null;
        this.count=0;
    • summary
  • dojox.collections.BinaryTree.contains

    • type
      Function
    • parameters:
      • data: (typeof )
    • source: [view]
        return this.search(data) != null;
    • summary
  • dojox.collections.BinaryTree.deleteData

    • type
      Function
    • parameters:
      • data: (typeof )
    • source: [view]
        var current=root;
        var parent=null;
        var i=current.compareData(data);
        while(i!=0&¤t!=null){
         if(i>0){
          parent=current;
          current=current.left;
         }else if(i<0){
          parent=current;
          current=current.right;
         }
         i=current.compareData(data);
        }
        if(!current){ return; }
        this.count--;
        if(!current.right){
         if(!parent){
          root=current.left;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=current.left; }
          else if(i<0){ parent.right=current.left; }
         }
        }
        else if(!current.right.left){
         if(!parent){
          root=current.right;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=current.right; }
          else if(i<0){ parent.right=current.right; }
         }
        }
        else{
         var leftmost=current.right.left;
         var lmParent=current.right;
         while(leftmost.left!=null){
          lmParent=leftmost;
          leftmost=leftmost.left;
         }
         lmParent.left=leftmost.right;
         leftmost.left=current.left;
         leftmost.right=current.right;
         if(!parent){
          root=leftmost;
         }else{
          i=parent.compare(current);
          if(i>0){ parent.left=leftmost; }
          else if(i<0){ parent.right=leftmost; }
         }
        }
    • summary
  • dojox.collections.BinaryTree.getIterator

    • type
      Function
    • source: [view]
        var a=[];
        inorderTraversalBuildup(root, a);
        return new dojox.collections.Iterator(a);
    • summary
  • dojox.collections.BinaryTree.search

    • type
      Function
    • parameters:
      • data: (typeof )
    • source: [view]
        return searchHelper(root, data);
    • summary
  • dojox.collections.BinaryTree.toString

    • type
      Function
    • parameters:
      • order: (typeof )
      • sep: (typeof )
    • source: [view]
        if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
        if(!sep){ sep=","; }
        var s="";
        switch(order){
         case dojox.collections.BinaryTree.TraversalMethods.Preorder:
          s=preorderTraversal(root, sep);
          break;
         case dojox.collections.BinaryTree.TraversalMethods.Inorder:
          s=inorderTraversal(root, sep);
          break;
         case dojox.collections.BinaryTree.TraversalMethods.Postorder:
          s=postorderTraversal(root, sep);
          break;
        };
        if(s.length==0){ return ""; }
        else{ return s.substring(0, s.length - sep.length); }
    • summary
  • dojox.collections

    • type
      Object
    • summary
  • dojox

    • type
      Object
    • summary