二叉排序树的构造过程C语言

二叉排序树是一种基于二叉树的数据结构，每个节点包含一个关键字，节点的左子树所有节点的关键字都小于该节点的关键字，右子树所有节点的关键字都大于该节点的关键字。下面从多个角度分析二叉排序树的构造过程C语言实现。

1. 节点的结构体定义

在C语言中，我们可以使用结构体来表示二叉排序树的节点。每个节点包含一个关键字，左右子树指针。具体的结构体定义如下：

```

typedef struct BSTNode {

int key; // 关键字

struct BSTNode *left; // 左子树指针

struct BSTNode *right; // 右子树指针

} BSTNode;

```

2. 插入节点

向二叉排序树中插入节点的过程可以使用递归实现。具体过程如下：

如果二叉排序树为空，新建一个节点。如果插入的关键字小于当前节点的关键字，递归地插入到左子树中；如果插入的关键字大于当前节点的关键字，递归地插入到右子树中。代码实现如下：

```

void insert(BSTNode **root, int key) {

if (*root == NULL) {

*root = (BSTNode *) malloc(sizeof(BSTNode));

(*root)->key = key;

(*root)->left = NULL;

(*root)->right = NULL;

} else if (key < (*root)->key) {

insert(&((*root)->left), key);

} else {

insert(&((*root)->right), key);

}

}

```

3. 查找节点

查找二叉排序树中的节点同样可以使用递归实现。具体过程如下：

如果节点为空，返回空指针；如果节点的关键字等于要查找的关键字，返回该节点；否则，如果要查找的关键字小于该节点的关键字，递归查找左子树；如果要查找的关键字大于该节点的关键字，递归查找右子树。代码实现如下：

```

BSTNode *search(BSTNode *root, int key) {

if (root == NULL || root->key == key) {

return root;

} else if (key < root->key) {

return search(root->left, key);

} else {

return search(root->right, key);

}

}

```

4. 删除节点

删除二叉排序树中的节点分为三种情况：删除叶子节点、删除只有一个子节点的节点、删除有两个子节点的节点。具体过程如下：

如果要删除的节点是叶子节点，直接删除即可；如果要删除的节点只有一个子节点，将该节点的子节点替换该节点即可；如果要删除的节点有两个子节点，找到中序遍历的前驱或后继节点替换该节点即可。代码实现如下：

```

void delete(BSTNode **root, int key) {

if (*root == NULL) {

return;

}

if (key < (*root)->key) {

delete(&((*root)->left), key);

} else if (key > (*root)->key) {

delete(&((*root)->right), key);

} else {

if ((*root)->left == NULL) {

BSTNode *temp = (*root)->right;

free(*root);

*root = temp;

} else if ((*root)->right == NULL) {

BSTNode *temp = (*root)->left;

free(*root);

*root = temp;

} else {

BSTNode *temp = getSuccessor(*root);

(*root)->key = temp->key;

delete(&((*root)->right), temp->key);

}

}

}

```

5. 中序遍历

中序遍历是指以左子树-根节点-右子树的顺序遍历二叉树。对于二叉排序树来说，中序遍历的结果是按照关键字从小到大排序的。中序遍历可以使用递归或者非递归方式实现。代码实现如下：

递归实现：

```

void inorder(BSTNode *root) {

if (root != NULL) {

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);

}

}

```

非递归实现：

```

void inorder(BSTNode *root) {

BSTNode *stack[100];

int top = -1;

while (root || top != -1) {

while (root) {

stack[++top] = root;

root = root->left;

}

if (top != -1) {

root = stack[top--];

printf("%d ", root->key);

root = root->right;

}

}

}

```