二叉树插入新节点的代码
时间: 2023-11-19 07:04:26 浏览: 74
二叉树插入新节点的代码可以分为两个步骤:
1. 查找插入位置
2. 插入新节点
具体代码如下(假设二叉树节点的定义如下):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
1. 查找插入位置
在二叉树中查找插入位置,需要从根节点开始遍历,如果待插入节点的值小于当前节点的值,则往左子树继续查找;如果待插入节点的值大于当前节点的值,则往右子树继续查找。如果遇到空节点,则说明找到了插入位置。
```python
def search_insert_pos(root, val):
if not root:
return None
prev = None
curr = root
while curr:
prev = curr
if val < curr.val:
curr = curr.left
else:
curr = curr.right
return prev
```
2. 插入新节点
在找到插入位置后,我们只需要在该位置插入新节点即可。如果待插入节点的值小于插入位置的值,则将新节点作为插入位置的左子节点;如果待插入节点的值大于插入位置的值,则将新节点作为插入位置的右子节点。
```python
def insert_node(root, val):
new_node = TreeNode(val)
if not root:
return new_node
pos = search_insert_pos(root, val)
if val < pos.val:
pos.left = new_node
else:
pos.right = new_node
return root
```
完整代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def search_insert_pos(root, val):
if not root:
return None
prev = None
curr = root
while curr:
prev = curr
if val < curr.val:
curr = curr.left
else:
curr = curr.right
return prev
def insert_node(root, val):
new_node = TreeNode(val)
if not root:
return new_node
pos = search_insert_pos(root, val)
if val < pos.val:
pos.left = new_node
else:
pos.right = new_node
return root
```