数据结构二叉树创建二叉树函数
时间: 2023-11-18 12:56:08 浏览: 51
二叉树的创建可以通过链式存储或者顺序存储来实现。其中链式存储是比较常用的方式。创建二叉树的函数可以按照以下步骤实现:
1. 定义一个二叉树节点类,包含节点值、左子树和右子树三个属性。
2. 定义一个创建节点的函数,用于创建一个新的节点。
3. 定义一个创建二叉树的函数,该函数接收一个列表作为参数,列表中的元素按照从上到下、从左到右的顺序表示二叉树中的节点。该函数通过递归的方式创建二叉树,具体实现如下:
a. 如果列表为空,则返回None。
b. 取出列表的第一个元素作为当前节点的值。
c. 创建一个新的节点,并将当前节点的值赋给该节点。
d. 递归创建当前节点的左子树,将左子树的根节点赋给当前节点的左子树属性。
e. 递归创建当前节点的右子树,将右子树的根节点赋给当前节点的右子树属性。
4. 返回二叉树的根节点。
下面是一个示例代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_node(val):
return TreeNode(val)
def create_tree(lst):
if not lst:
return None
root_val = lst.pop(0)
if not root_val:
return None
root = create_node(root_val)
root.left = create_tree(lst)
root.right = create_tree(lst)
return root
```
使用示例:
```
lst = [1, 2, 3, None, None, 4, 5]
root = create_tree(lst)
```