source: Dev/trunk/src/client/dojox/collections/BinaryTree.js @ 532

Last change on this file since 532 was 483, checked in by hendrikvanantwerpen, 11 years ago

Added Dojo 1.9.3 release.
File size: 4.7 KB
Line 
1define(["dojo/_base/kernel", "dojo/_base/array", "./_base"], function(dojo, darray, dxc){
2
3        dxc.BinaryTree=function(data){
4                function node(data, rnode, lnode){
5                        this.value=data||null;
6                        this.right=rnode||null;
7                        this.left=lnode||null;
8                        this.clone=function(){
9                                var c=new node();
10                                if(this.value.value){
11                                        c.value=this.value.clone();
12                                }else{
13                                        c.value=this.value;
14                                }
15                                if(this.left!=null){
16                                        c.left=this.left.clone();
17                                }
18                                if(this.right!=null){
19                                        c.right=this.right.clone();
20                                }
21                                return c;
22                        }
23                        this.compare=function(n){
24                                if(this.value>n.value){ return 1; }
25                                if(this.value<n.value){ return -1; }
26                                return 0;
27                        }
28                        this.compareData=function(d){
29                                if(this.value>d){ return 1; }
30                                if(this.value<d){ return -1; }
31                                return 0;
32                        }
33                }
34
35                function inorderTraversalBuildup(current, a){
36                        if(current){
37                                inorderTraversalBuildup(current.left, a);
38                                a.push(current.value);
39                                inorderTraversalBuildup(current.right, a);
40                        }
41                }
42
43                function preorderTraversal(current, sep){
44                        var s="";
45                        if (current){
46                                s=current.value.toString() + sep;
47                                s+=preorderTraversal(current.left, sep);
48                                s+=preorderTraversal(current.right, sep);
49                        }
50                        return s;
51                }
52                function inorderTraversal(current, sep){
53                        var s="";
54                        if (current){
55                                s=inorderTraversal(current.left, sep);
56                                s+=current.value.toString() + sep;
57                                s+=inorderTraversal(current.right, sep);
58                        }
59                        return s;
60                }
61                function postorderTraversal(current, sep){
62                        var s="";
63                        if (current){
64                                s=postorderTraversal(current.left, sep);
65                                s+=postorderTraversal(current.right, sep);
66                                s+=current.value.toString() + sep;
67                        }
68                        return s;
69                }
70               
71                function searchHelper(current, data){
72                        if(!current){ return null; }
73                        var i=current.compareData(data);
74                        if(i==0){ return current; }
75                        if(i>0){ return searchHelper(current.left, data); }
76                        else{ return searchHelper(current.right, data); }
77                }
78
79                this.add=function(data){
80                        var n=new node(data);
81                        var i;
82                        var current=root;
83                        var parent=null;
84                        while(current){
85                                i=current.compare(n);
86                                if(i==0){ return; }
87                                parent=current;
88                                if(i>0){ current=current.left; }
89                                else{ current=current.right; }
90                        }
91                        this.count++;
92                        if(!parent){
93                                root=n;
94                        }else{
95                                i=parent.compare(n);
96                                if(i>0){
97                                        parent.left=n;
98                                }else{
99                                        parent.right=n;
100                                }
101                        }
102                };
103                this.clear=function(){
104                        root=null;
105                        this.count=0;
106                };
107                this.clone=function(){
108                        var c=new dxc.BinaryTree();
109                        var itr=this.getIterator();
110                        while(!itr.atEnd()){
111                                c.add(itr.get());
112                        }
113                        return c;
114                };
115                this.contains=function(data){
116                        return this.search(data) != null;
117                };
118                this.deleteData=function(data){
119                        var current=root;
120                        var parent=null;
121                        var i=current.compareData(data);
122                        while(i!=0&&current!=null){
123                                if(i>0){
124                                        parent=current;
125                                        current=current.left;
126                                }else if(i<0){
127                                        parent=current;
128                                        current=current.right;
129                                }
130                                i=current.compareData(data);
131                        }
132                        if(!current){ return; }
133                        this.count--;
134                        if(!current.right){
135                                if(!parent){
136                                        root=current.left;
137                                }else{
138                                        i=parent.compare(current);
139                                        if(i>0){ parent.left=current.left; }
140                                        else if(i<0){ parent.right=current.left; }
141                                }
142                        }
143                        else if(!current.right.left){
144                                if(!parent){
145                                        root=current.right;
146                                }else{
147                                        i=parent.compare(current);
148                                        if(i>0){ parent.left=current.right; }
149                                        else if(i<0){ parent.right=current.right; }
150                                }
151                        }
152                        else{
153                                var leftmost=current.right.left;
154                                var lmParent=current.right;
155                                while(leftmost.left!=null){
156                                        lmParent=leftmost;
157                                        leftmost=leftmost.left;
158                                }
159                                lmParent.left=leftmost.right;
160                                leftmost.left=current.left;
161                                leftmost.right=current.right;
162                                if(!parent){
163                                        root=leftmost;
164                                }else{
165                                        i=parent.compare(current);
166                                        if(i>0){ parent.left=leftmost; }
167                                        else if(i<0){ parent.right=leftmost; }
168                                }
169                        }
170                };
171                this.getIterator=function(){
172                        var a=[];
173                        inorderTraversalBuildup(root, a);
174                        return new dxc.Iterator(a);
175                };
176                this.search=function(data){
177                        return searchHelper(root, data);
178                };
179                this.toString=function(order, sep){
180                        if(!order){ order=dxc.BinaryTree.TraversalMethods.Inorder; }
181                        if(!sep){ sep=","; }
182                        var s="";
183                        switch(order){
184                                case dxc.BinaryTree.TraversalMethods.Preorder:
185                                        s=preorderTraversal(root, sep);
186                                        break;
187                                case dxc.BinaryTree.TraversalMethods.Inorder:
188                                        s=inorderTraversal(root, sep);
189                                        break;
190                                case dxc.BinaryTree.TraversalMethods.Postorder:
191                                        s=postorderTraversal(root, sep);
192                                        break;
193                        };
194                        if(s.length==0){ return ""; }
195                        else{ return s.substring(0, s.length - sep.length); }
196                };
197
198                this.count=0;
199                var root=this.root=null;
200                if(data){
201                        this.add(data);
202                }
203        }
204        dxc.BinaryTree.TraversalMethods={
205                Preorder: 1, Inorder: 2, Postorder: 3
206        };
207        return dxc.BinaryTree;
208});
Note: See TracBrowser for help on using the repository browser.