数据结构教程二叉树的创建
时间: 2023-12-18 17:04:36 浏览: 40
二叉树是一种非常常见的数据结构,它的每个节点最多只有两个子节点,分别称为左子节点和右子节点。二叉树有很多应用场景,例如搜索树、堆、表达式树等。在这里,我将简单介绍二叉树的创建方法。
二叉树的创建可以通过递归的方式实现。具体步骤如下:
1. 定义二叉树的节点结构体,包括节点值、左子节点指针和右子节点指针。
2. 通过递归的方式创建二叉树。从根节点开始,如果左子节点为空,则新建节点并将其作为左子节点;如果左子节点不为空,则递归创建其左子树。同理,如果右子节点为空,则新建节点并将其作为右子节点;如果右子节点不为空,则递归创建其右子树。
下面是一段示例代码,用于创建一棵二叉树:
```
#include <iostream>
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 递归创建二叉树
TreeNode* createBinaryTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
int main() {
TreeNode* root = createBinaryTree();
return 0;
}
```
这段代码定义了一个二叉树节点的结构体,包含节点值、左子节点指针和右子节点指针。在 `createBinaryTree` 函数中,通过递归的方式创建二叉树。具体实现如下:
1. 读入一个整数 `val`。
2. 如果 `val` 等于 -1,则返回空节点。
3. 否则,新建一个值为 `val` 的节点,并递归创建其左子树和右子树。
4. 返回根节点。
在主函数中,调用 `createBinaryTree` 函数创建二叉树。输入样例可以为:
```
1 2 4 -1 -1 5 -1 -1 3 -1 -1
```
其中 -1 表示空节点。以上输入样例表示的二叉树如下:
```
1
/ \
2 3
/ \
4 5
```
希望这个简单的二叉树创建方法能够帮助你更好地理解二叉树的基础知识。
相关推荐
![](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)