二叉排序树插入节点
时间: 2023-07-20 21:20:07 浏览: 45
二叉排序树的插入节点操作如下:
1. 如果树为空,插入的节点就是根节点,直接返回。
2. 如果插入的节点值小于根节点的值,递归地插入到左子树中。
3. 如果插入的节点值大于根节点的值,递归地插入到右子树中。
4. 如果插入的节点值等于根节点的值,说明该节点已经存在于树中,直接返回。
下面是 C++ 代码实现:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void insert(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insert(root->left, val);
}
else if (val > root->val) {
insert(root->right, val);
}
else {
// val already exists in the tree, do nothing
return;
}
}
```
其中 `TreeNode` 是二叉排序树的节点结构体,`insert` 函数的第一个参数是二叉排序树的根节点,第二个参数是要插入的节点的值。使用引用 `TreeNode*&` 是为了能够修改根节点的值。