Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2334583

Browse files
committed
Add setValue and nodeCopy methods to binary tree node.
1 parentbd5a16b commit2334583

File tree

3 files changed

+69
-8
lines changed

3 files changed

+69
-8
lines changed

‎src/data-structures/tree/BinaryTreeNode.js

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,16 @@ export default class BinaryTreeNode {
8585
returnthis.parent.parent.left;
8686
}
8787

88+
/**
89+
*@param {*} value
90+
*@return {BinaryTreeNode}
91+
*/
92+
setValue(value){
93+
this.value=value;
94+
95+
returnthis;
96+
}
97+
8898
/**
8999
*@param {BinaryTreeNode} node
90100
*@return {BinaryTreeNode}
@@ -168,6 +178,16 @@ export default class BinaryTreeNode {
168178
returnfalse;
169179
}
170180

181+
/**
182+
*@param {BinaryTreeNode} sourceNode
183+
*@param {BinaryTreeNode} targetNode
184+
*/
185+
staticcopyNode(sourceNode,targetNode){
186+
targetNode.setValue(sourceNode.value);
187+
targetNode.setLeft(sourceNode.left);
188+
targetNode.setRight(sourceNode.right);
189+
}
190+
171191
/**
172192
*@return {*[]}
173193
*/

‎src/data-structures/tree/__test__/BinaryTreeNode.test.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -257,4 +257,41 @@ describe('BinaryTreeNode', () => {
257257
expect(child.uncle).toBeDefined();
258258
expect(child.uncle).toEqual(uncle);
259259
});
260+
261+
it('should be possible to set node values',()=>{
262+
constnode=newBinaryTreeNode('initial_value');
263+
264+
expect(node.value).toBe('initial_value');
265+
266+
node.setValue('new_value');
267+
268+
expect(node.value).toBe('new_value');
269+
});
270+
271+
it('should be possible to copy node',()=>{
272+
constroot=newBinaryTreeNode('root');
273+
constleft=newBinaryTreeNode('left');
274+
constright=newBinaryTreeNode('right');
275+
276+
root
277+
.setLeft(left)
278+
.setRight(right);
279+
280+
expect(root.toString()).toBe('left,root,right');
281+
282+
constnewRoot=newBinaryTreeNode('new_root');
283+
constnewLeft=newBinaryTreeNode('new_left');
284+
constnewRight=newBinaryTreeNode('new_right');
285+
286+
newRoot
287+
.setLeft(newLeft)
288+
.setRight(newRight);
289+
290+
expect(newRoot.toString()).toBe('new_left,new_root,new_right');
291+
292+
BinaryTreeNode.copyNode(root,newRoot);
293+
294+
expect(root.toString()).toBe('left,root,right');
295+
expect(newRoot.toString()).toBe('left,root,right');
296+
});
260297
});

‎src/data-structures/tree/binary-search-tree/BinarySearchTreeNode.js

Lines changed: 12 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -99,7 +99,7 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
9999
parent.removeChild(nodeToRemove);
100100
}else{
101101
// Node has no parent. Just erase current node value.
102-
nodeToRemove.value=null;
102+
nodeToRemove.setValue(undefined);
103103
}
104104
}elseif(nodeToRemove.left&&nodeToRemove.right){
105105
// Node has two children.
@@ -108,20 +108,24 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {
108108
constnextBiggerNode=nodeToRemove.right.findMin();
109109
if(!this.nodeComparator.equal(nextBiggerNode,nodeToRemove.right)){
110110
this.remove(nextBiggerNode.value);
111-
nodeToRemove.value=nextBiggerNode.value;
111+
nodeToRemove.setValue(nextBiggerNode.value);
112112
}else{
113113
// In case if next right value is the next bigger one and it doesn't have left child
114114
// then just replace node that is going to be deleted with the right node.
115-
nodeToRemove.value=nodeToRemove.right.value;
116-
nodeToRemove.right=nodeToRemove.right.right;
115+
nodeToRemove.setValue(nodeToRemove.right.value);
116+
nodeToRemove.setRight(nodeToRemove.right.right);
117117
}
118118
}else{
119119
// Node has only one child.
120120
// Make this child to be a direct child of current node's parent.
121-
constchild=nodeToRemove.left||nodeToRemove.right;
122-
nodeToRemove.value=child.value;
123-
nodeToRemove.setLeft(child.left);
124-
nodeToRemove.setRight(child.right);
121+
/**@var BinarySearchTreeNode */
122+
constchildNode=nodeToRemove.left||nodeToRemove.right;
123+
124+
if(parent){
125+
parent.replaceChild(nodeToRemove,childNode);
126+
}else{
127+
BinaryTreeNode.copyNode(childNode,nodeToRemove);
128+
}
125129
}
126130

127131
returntrue;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp