创建二叉树的三种算法
1.递归算法
递归算法是最直观也是最常用的创建二叉树的方法之一、递归算法通过递归地创建左子树和右子树来构建完整的二叉树。
具体步骤如下：
-创建一个二叉树结构的定义，包含一个存储数据的变量和左右子节点。
-如果当前节点为空，直接将新节点插入当前位置。
-如果新节点的值小于当前节点的值，递归地将新节点插入当前节点的左子树。
-如果新节点的值大于等于当前节点的值，递归地将新节点插入当前节点的右子树。
递归算法的示例代码如下所示：
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
elif val >= root.val:
root.right = insert(root.right, val)
return root
```
2.先序遍历算法
完全二叉树算法先序遍历算法通过遍历给定的节点集合，按照先序的顺序将节点逐个插入到二叉树中。这种算法可以使用栈来实现。
具体步骤如下：
-创建一个空栈，同时创建一个新节点的拷贝作为当前节点。
-依次遍历给定的节点集合，如果新节点的值小于当前节点的值，将当前节点的左子节点指向新节点，并将新节点入栈，并将新节点移动到当前节点的左子节点。
-如果新节点的值大于等于当前节点的值，重复上述过程，直到到一个合适的位置并插入新节点。
-当遍历完所有节点后，返回二叉树的根节点。
先序遍历算法的示例代码如下所示：
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if root is None:
return TreeNode(val)
stack = []
cur = root
while True:
if val < cur.val:
if not cur.left:
cur.left = TreeNode(val)
break
else:
cur = cur.left
else:
if not cur.right:
cur.right = TreeNode(val)
break
else:
cur = cur.right
return root
```
3.层次遍历算法
层次遍历算法通过逐层遍历给定的节点集合，按照从上到下、从左到右的顺序将节点逐个插入到二叉树中。这种算法可以使用队列来实现。
具体步骤如下：
-创建一个空队列，同时创建一个新节点的拷贝作为当前节点，并将当前节点入队。
-依次遍历给定的节点集合，从队列中取出一个节点作为当前节点。
-如果新节点的值小于当前节点的值，将当前节点的左子节点指向新节点，并将新节点入队。
-如果新节点的值大于等于当前节点的值，将当前节点的右子节点指向新节点，并将新节点入队。
-当遍历完所有节点后，返回二叉树的根节点。
层次遍历算法的示例代码如下所示：
```python
from collections import deque
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if root is None:
return TreeNode(val)
queue = deque
cur = root
queue.append(cur)
while queue:
cur = queue.popleft

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。