星期三, 十月 25, 2006

基本算法连载(14)-BST(Binary Search Tree)的笔记

插入实现(传指针地址的地址):

void InsertNode(struct node **node_ptr, struct node *newNode) {
struct node *node = *node_ptr;
if (node == NULL)
*node_ptr = newNode;
else if (newNode->value <= node->value)
InsertNode(&node->left, newNode);
else
InsertNode(&node->right, newNode);
}

删除节点:

void DeleteNode(struct node*& node) {
struct node*&amp; temp = node;
if (node->left == NULL) {
node = node->right;
delete temp;
} else if (node->right == NULL) {
node = node->left;
delete temp;
} else {
// Node has two children - get max of left subtree
temp = node->left;
while (temp->right != NULL) {
temp = temp->right;
}
node->value = temp->value;
DeleteNode(temp);
}
}

没有评论: