二叉树的建立 (运用先序序列来创建)c++
时间: 2023-12-07 21:02:22 浏览: 23
以下是一种用先序序列来创建二叉树的算法:
1. 定义一个树节点类,包含一个值属性和左右子节点属性。
2. 创建一个递归函数,接收一个先序序列和当前节点值。
3. 如果先序序列为空,返回 None。
4. 创建一个新的树节点,值为当前节点值。
5. 如果先序序列的下一个值不为 None,递归创建左子树,将左子树返回值赋给当前节点的左子节点属性。
6. 如果先序序列的下一个值不为 None,递归创建右子树,将右子树返回值赋给当前节点的右子节点属性。
7. 返回创建好的树节点。
代码如下:
```
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val is None:
return None
root = TreeNode(val)
root.left = build_tree(preorder)
root.right = build_tree(preorder)
return root
```
使用示例:
```
preorder = [1, 2, None, 3, 4, None, None, 5, None, None, 6, None, 7, None, None]
root = build_tree(preorder)
```
这个示例创建了如下的二叉树:
```
1
/ \
2 6
\ \
3 7
/ \
4 5
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)