Lines Matching refs:node
57 void TreeNodeDeleteSingleNode(treeNode* node)
59 free(node);
62 void TreeNodeDeleteWholeTree(treeNode* node)
64 if(node == NULL) return;
65 TreeNodeDeleteWholeTree(node->left);
66 TreeNodeDeleteWholeTree(node->right);
67 TreeNodeDeleteSingleNode(node);
70 void TreeNodePrint(treeNode* node,
73 if(node ==NULL) return;
74 TreeNodePrint(node->left, keyPrint);
75 keyPrint(node->key);
76 TreeNodePrint(node->right, keyPrint);
89 /*return the node with the key.
142 treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node)
147 if(node==NULL) return tree;
149 if(node->left == NULL || node->right == NULL) {
151 y = node;
171 else { /*node has two children*/
173 y = TreeNodeSuccessor(node);
176 if(y == node->right) /*y is the right child if node*/
178 y->parent = node->parent;
179 y->left = node->left;
180 node->left->parent = y;
183 else /*y != node->right*/
194 /*move y to the position of node*/
195 y->parent = node->parent;
196 y->left = node->left;
197 y->right = node->right;
198 node->left->parent = y;
199 node->right->parent = y;
201 if(node->parent != NULL) {
202 if(node->parent->left == node)
203 node->parent->left = y;
205 node->parent->right = y;
208 else /*node->parent is NULL: node is the root*/
212 /*finally free the node, and return the new root*/
213 TreeNodeDeleteSingleNode(node);
218 /*the minimum node in the tree rooted by node
220 treeNode* TreeNodeMinimum(treeNode* node)
222 treeNode* temp = node;
230 /*the maximum node in the tree rooted by node
232 treeNode* TreeNodeMaximum(treeNode* node)
234 treeNode* temp = node;
242 /*return the first node (in sorted order) which is to the right of this node
244 treeNode* TreeNodeSuccessor(treeNode* node)
246 if(node == NULL) return NULL;
247 if(node->right != NULL)
248 return TreeNodeMinimum(node->right);
249 else{ /*node->right is NULL*/
252 treeNode *y = node->parent;
253 treeNode* x = node;
264 /*return the first node (in sorted order) which is to the left of this node
266 treeNode* TreeNodePredecessor(treeNode* node)
268 if(node == NULL) return NULL;
269 if(node->left != NULL)
270 return TreeNodeMaximum(node->left);
271 else{ /*node->left is NULL*/
273 treeNode *y = node->parent;
274 treeNode *x = node;