二叉树的创建与遍历方式

二叉树是一种常见的数据结构，它由若干个节点组成，每个节点最多有两个子节点，根节点不要求一定有子节点。在计算机科学中，二叉树结构被广泛应用于搜索、排序以及压缩等算法的实现中。

本文将从二叉树的基本概念、节点的表示、二叉树的创建以及二叉树的遍历方式等多个角度进行分析。

一、二叉树的基本概念

二叉树是树的一种特殊情况，它具有以下几个基本概念：

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 s;

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;

}

}

```