按层次给定一棵二叉树的元素,建立该二叉树。请利用递归方法输出所建二叉树的先序序列。
时间: 2023-03-26 13:03:36 浏览: 77
二叉树的先序遍历是指先访问根节点,然后遍历左子树,最后遍历右子树。利用递归方法输出先序序列的代码如下:
```
void preOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " "; // 访问根节点
preOrderTraversal(root->left); // 遍历左子树
preOrderTraversal(root->right); // 遍历右子树
}
```
其中,`TreeNode` 是二叉树节点的结构体,包含 `val`、`left` 和 `right` 三个成员变量,分别表示节点的值、左子节点和右子节点。建立二叉树的方法可以根据题目给定的元素进行递归构建,具体实现可以参考以下代码:
```
TreeNode* buildTree(vector<int>& elements, int index) {
if (index >= elements.size() || elements[index] == -1) {
return nullptr;
}
TreeNode* root = new TreeNode(elements[index]);
root->left = buildTree(elements, 2 * index + 1);
root->right = buildTree(elements, 2 * index + 2);
return root;
}
```
其中,`elements` 是按层次给定的二叉树元素,`index` 表示当前节点在 `elements` 中的下标。如果当前节点的值为 -1 或者下标越界,则返回 `nullptr`,否则创建一个新的节点,并递归构建左右子树。最后,可以调用 `preOrderTraversal` 函数输出先序序列。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)