数据结构之-二叉查找树的实现（C语言版）

chiyx

修正：前驱与后继操作有误，修正

二叉查找树是满足如下性质的二叉树：

• 设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x]
  
• 如果y是x的右子树，则key[x]<=key[y]
  

二叉查找树的数据结构和操作定义如下：
/*file:biTree.h*/#ifndef CHIYX_BITREE#define CHIYX_BITREE#ifndef NULL#define NULL 0#endiftypedef int DataType;//二叉树的节点结构typedef struct BiTreeNode {DataType data;struct BiTreeNode *parent;struct BiTreeNode *left;struct BiTreeNode *right;}BiTreeNode, *BiTree;//查找：返回第一个等于data域等于key的节点，不存在返回NULLBiTreeNode *search(BiTree *biTree, DataType key);//返回二叉树的最小节点,空树返回NULLBiTreeNode *minImum(BiTree *biTree);//返回二叉树的最大节点,空树返回NULLBiTreeNode *maxImum(BiTree *biTree);//返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULLBiTreeNode *successor(BiTreeNode *x);//返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULLBiTreeNode *predecessor(BiTreeNode *x);//将值data插入到二叉树中（生成一个值为data的节点）void insertNode(BiTree *biTree, DataType data);//删除一个值为data的节点void deleteNode(BiTree *biTree, DataType data);//中序遍历二叉树void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node));#endif
它的实现如下：
/*file:biTree.c*/#include <stdlib.h>#include "biTree.h"//查找：返回第一个等于data域等于key的节点，不存在返回NULLBiTreeNode *search(BiTree *biTree, DataType key) {BiTreeNode *curNode = *biTree;while (curNode != NULL && curNode->data != key) {if (key < curNode->data) {curNode = curNode->left;} else {curNode = curNode->right;}}return curNode;}//返回二叉树的最小节点,空树返回NULLBiTreeNode *minImum(BiTree *biTree) {BiTreeNode *curNode = *biTree;while (curNode != NULL && curNode->left != NULL) {curNode = curNode->left;}return curNode;}//返回二叉树的最大节点,空树返回NULLBiTreeNode *maxImum(BiTree *biTree) {BiTreeNode *curNode = *biTree;while (curNode != NULL && curNode->right != NULL) {curNode = curNode->right;}return curNode;}//返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULLBiTreeNode *successor(BiTreeNode *x) {         if (x == NULL) return NULL;//存在右子树，则后继节点为其右子树中最小的节点if (x != NULL && x->right != NULL) {return minImum(&(x->right));}while (x->parent != NULL && x->parent->right == x) {x = x->parent;}return x->parent; //错误版本为 x， 此处应该返回父结点}//返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULLBiTreeNode *predecessor(BiTreeNode *x) {         if (x == NULL) return NULL;//存在左子树，则后继节点为其左子树中最大的节点if (x != NULL && x->left != NULL) {return maxImum(&(x->left));}while (x->parent != NULL && x->parent->left == x) {x = x->parent;}return x->parent; //错误版本为 x， 此处应该返回父结点}void insertNode(BiTree *biTree, DataType data) {//创建节点BiTreeNode *targetNode;targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode));//没有足够内存if (targetNode == NULL) return;targetNode->data = data;targetNode->parent = NULL;targetNode->left = NULL;targetNode->right = NULL;BiTreeNode *p, *y; p = *biTree;y = NULL;while (p != NULL ) {y = p;if (targetNode->data < p->data) {p = p->left;} else {p = p->right;}}//空树，将新节点置为树根if (y == NULL) {*biTree = targetNode;} else {if (targetNode->data < y->data) {y->left = targetNode;} else {y->right = targetNode;}}targetNode->parent = y;}//删除一个值为data的节点void deleteNode(BiTree *biTree, DataType data) {//查找待删除的节点BiTreeNode *targetNode, *x, *y;targetNode = search(biTree, data);if (targetNode == NULL) return;//找出真正的删除节点，如果目标节点最多只有一个子树，则其为真正删除的节点//否则其后继节点（最多只有一个子树，想想为什么）为真正删除的节点，然后将后继节点的值赋给目标节点if (targetNode->left == NULL || targetNode->right == NULL) {y = targetNode;} else {y = successor(targetNode);}if (y->left != NULL) {x = y->left;} else {x = y->right;}if (x != NULL) {x->parent = y->parent;}//如果y是根节点, 则根节点变为xif (y->parent == NULL) {*biTree = x;} else {if (y->parent->right == y) {y->parent->right = x;} else {y->parent->left = x;}}if (y != targetNode) {targetNode->data = y->data;} //释放y占有的空间free(y);}//中序遍历二叉树void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) {BiTreeNode *curNode;curNode = *biTree;if (curNode != NULL) {//遍历左子树inorderTraversal(&(curNode->left), visitor);//访问节点visitor(curNode);//遍历右子树inorderTraversal(&(curNode->right), visitor);}}
测试代码如下：
#include <stdio.h>#include <stdlib.h>#include "biTree.h"#define N  10void printNode(BiTreeNode *node);int main(int argc, char *argv[]) {BiTreeNode *root;int i;root = NULL;int data[N] = {10, 23, 11, 98, 111, 87, 34, 11, 33, 8};for (i = 0; i < N; i++) {insertNode(&root, data);}printf("before delete:\n");inorderTraversal(&root, printNode);printf("\n");deleteNode(&root, 11);deleteNode(&root, 8);printf("after delete:\n");inorderTraversal(&root, printNode);printf("\n");exit(0);}void printNode(BiTreeNode *node) {printf("%d\t", node->data);}
运行结果:
before delete:
8       10      11      11      23      33      34      87      98      111

after delete:
10      11      23      33      34      87      98      111