用c语言写左子树中的所有节点的数据域都小于根节点的数据域, 而右子树中的所有节点的数据域都大于根节点的数据域。 递归插入数据域为key的节点,插入之后整个BST任然满足BST的定义 参数:(BSTree *pTree, ElemType key) 二叉树的指针与查找关键字 返回值: void
时间: 2024-03-23 17:42:57 浏览: 63
好的,我知道了您的问题。以下是用C语言实现的左子树小于根节点,右子树大于根节点的二叉搜索树插入节点的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
// 定义二叉树节点
typedef struct BSTNode {
ElemType data; // 数据域
struct BSTNode *left; // 左子树指针
struct BSTNode *right; // 右子树指针
} BSTNode, *BSTree;
// 创建新节点
BSTNode* createNode(ElemType key) {
BSTNode* node = (BSTNode*)malloc(sizeof(BSTNode));
node->data = key;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
void insertNode(BSTree *pTree, ElemType key) {
if (*pTree == NULL) { // 如果树为空,则新建节点作为根节点
*pTree = createNode(key);
return;
}
if (key < (*pTree)->data) { // 如果关键字小于根节点,则插入到左子树
if ((*pTree)->left == NULL || (*pTree)->left->data > key) { // 左子树为空或者左子树的根节点大于关键字
BSTNode* node = createNode(key);
node->left = (*pTree)->left;
(*pTree)->left = node;
} else {
insertNode(&((*pTree)->left), key); // 递归插入节点
}
} else { // 如果关键字大于等于根节点,则插入到右子树
if ((*pTree)->right == NULL || (*pTree)->right->data < key) { // 右子树为空或者右子树的根节点小于关键字
BSTNode* node = createNode(key);
node->right = (*pTree)->right;
(*pTree)->right = node;
} else {
insertNode(&((*pTree)->right), key); // 递归插入节点
}
}
}
int main() {
BSTree tree = NULL; // 初始化空树
// 插入节点
insertNode(&tree, 6);
insertNode(&tree, 4);
insertNode(&tree, 8);
insertNode(&tree, 2);
insertNode(&tree, 5);
insertNode(&tree, 7);
insertNode(&tree, 9);
// 遍历输出二叉搜索树
printf("Preorder traversal: ");
preorderTraversal(tree);
printf("\n");
printf("Inorder traversal: ");
inorderTraversal(tree);
printf("\n");
printf("Postorder traversal: ");
postorderTraversal(tree);
printf("\n");
return 0;
}
```
注意:在插入节点时,为了保证左子树中的所有节点的数据域都小于根节点的数据域,而右子树中的所有节点的数据域都大于根节点的数据域,我们需要在比较大小时,将等于根节点的情况归为右子树中的情况。同时,如果插入的节点的值与已有节点的值相同,我们也需要将新节点插入到右子树中。
阅读全文