二叉树的创建与遍历方式
二叉树是一种常见的数据结构，它由若干个节点组成，每个节点最多有两个子节点，根节点不要求一定有子节点。在计算机科学中，二叉树结构被广泛应用于搜索、排序以及压缩等算法的实现中。
本文将从二叉树的基本概念、节点的表示、二叉树的创建以及二叉树的遍历方式等多个角度进行分析。
一、二叉树的基本概念
二叉树是树的一种特殊情况，它具有以下几个基本概念：
1. 根节点：二叉树的最顶端节点。
2. 叶子节点：没有子节点的节点。
3. 子树：以某个节点为根节点的子树。
4. 深度：从根节点到节点所在层数的层数。
5. 高度：从节点到叶子节点的最长路径长度。
6. 完全二叉树：除了最后一层外，其他层的节点数都是满的，最后一层节点都在最左边。
7. 满二叉树：每层节点数都是满的。
二、节点的表示
二叉树的每个节点都由三个元素组成：节点本身的值、指向左子节点的指针以及指向右子节点的指针。
在一些语言中，可以使用类或结构体来表示二叉树的节点，例如C++中的以下代码：
```cpp
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
在Java中，可以使用以下代码：
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
```
三、二叉树的创建
1. 手动创建：手动创建二叉树需要先创建根节点，然后依次创建左右子树。这种方法适用于较小的二叉树。
2. 数组创建：将节点放入数组中，并将数组下标与节点的左右指针对应起来。使用这种方法的前提是已经知道节点的数量和位置。
3. 前序遍历创建：根据二叉树的前序遍历序列来创建二叉树，对递归较为熟悉的程序员可以用这种方法。
4. 层序遍历创建：层序遍历可以按照树的结构直接生成二叉树。层序遍历一般采用队列来实现。
四、二叉树的遍历方式
对二叉树的遍历方式包括三种：前序遍历、中序遍历和后序遍历。其中，前序遍历即按根-左-右的顺序遍历，中序遍历是按左-根-右的顺序遍历，后序遍历是按左-右-根的顺序遍历。
递归是二叉树遍历的常规方法，下面分别列举三种遍历方式的递归算法：
```cpp
//前序遍历
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
visit(root);
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
visit(root);
inOrder(root->right);
}
//后序遍历
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
visit(root);
}
```
对于非递归算法，可以使用栈来实现，以下是中序遍历的非递归算法：
```cpp
void inOrderWithStack(TreeNode* root) {
stack
TreeNode* cur = root;
while (cur != nullptr || !s.empty()) {
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
visit(cur);
cur = cur->right;
}
}
```
