c++ 图解层序遍历和逐层打印智能指针建造的二叉树

1. 简介

二叉树是数据结构中最基本的结构之一，它可以非常自然地反映出很多实际问题。

本文主要介绍C++如何实现层序遍历和逐层打印智能指针建造的二叉树。

2. 二叉树的定义和建立

2.1 二叉树的定义

二叉树是一种树形结构，它的每个节点最多只有两个子节点。

一般来说这两个子节点被称为左子树和右子树。

二叉树节点的数据结构一般包括左子节点、右子节点、和节点本身的值。

用C++实现的话常常使用结构体来表示：

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

这里使用了C++的构造函数来初始化节点的值。

排除节点本身，节点的两个指针初始赋值为nullptr，即指向空节点。

2.2 二叉树的建立

要在C++中建立一棵二叉树，我们可以按照深度优先搜索的原则，在代码中递归地完成二叉树的建立。

以下是一个简单的示例代码，假设我们要建立的二叉树的先序遍历是 [1, 2, 4, 5, 3, 6, 7] 和中序遍历是 [4, 2, 5, 1, 6, 3, 7]：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  if(preorder.empty() || inorder.empty()) {
    return nullptr;
  }
  int rootValue = preorder[0];
  auto root = new TreeNode(rootValue);
  auto it = find(inorder.begin(), inorder.end(), rootValue);
  int leftSize = it - inorder.begin();
  
  vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftSize);
  vector<int> leftInorder(inorder.begin(), it);
  root->left = buildTree(leftPreorder, leftInorder);
  vector<int> rightPreorder(preorder.begin() + 1 + leftSize, preorder.end());
  vector<int> rightInorder(it + 1, inorder.end());
  root->right = buildTree(rightPreorder, rightInorder);
  
  return root;
}

在使用递归来实现二叉树建立的时候，每次递归需要指定一个区间（如上文代码中的leftPreorder、leftInorder、rightPreorder、rightInorder），表示当前层的这个节点的左、右子树所包含的节点。

最终的效果就是，在最上面一层递归中建立二叉树的根节点，然后在下一层递归中分别建立左子树和右子树，一层层向下递归下去，直到建立完整个二叉树。

3. 层序遍历

3.1 层序遍历的定义

层序遍历是一种广度优先搜索，也就是按层遍历。

通俗的理解是，从二叉树的根节点开始，从上到下按层遍历，同一层从左到右遍历完一层再遍历下一层直到结束。

3.2 层序遍历的实现

在C++中实现层序遍历需要用到队列，将每个节点插入到队列中，每次取出队列头部的节点，把它的左右儿子节点插入到队列尾部，然后继续处理队列中的下一个节点。

以下是c++中递归和迭代两种层序遍历的实现方式：

3.2.1 递归方法

void helper(TreeNode* root, int level, vector<vector<int>>& result) {
  if (!root) {
    return;
  }
  if (result.size() == level) {
    result.push_back({});
  }
  result[level].push_back(root->val);
  helper(root->left, level + 1, result);
  helper(root->right, level + 1, result);
}
vector<vector<int>> levelOrder1(TreeNode* root) {
  vector<vector<int>> result;
  helper(root, 0, result);
  return result;
}

在递归方法中，我们首先定义一个 helper 函数来递归地处理每个节点，通过传入参数 level 来区分节点处于二叉树的哪一层，通过这个参数来设置二维结果数组中每一行的位置。

如果当前节点不存在，那么我们直接返回。

接着，我们检查结果数组的行数，如果当前结果数组的行数等于 level，说明我们已经处理完了这一层的所有节点，为了保存这一层的结果，我们需要往结果数组中新增一行（每个节点的值以 vector 的形式保存）。

最后，我们通过递归依次处理左子树和右子树即可。

3.2.2 迭代方法

vector<vector<int>> levelOrder2(TreeNode* root) {
  vector<vector<int>> result;
  if (!root) {
    return result;
  }
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    vector<int> level;
    int size = q.size();
    for (int i = 0; i < size; i++) {
      auto node = q.front();
      q.pop();
      level.push_back(node->val);
      if (node->left) {
        q.push(node->left);
      }  
      if (node->right) {
        q.push(node->right);
      }
    }
    result.push_back(level);
  }
  return result;
}

在迭代方法中，我们首先判断根节点是否存在。如果不存在，我们直接返回一个空的二维 vector。

接着，声明一个队列，将根节点插入队列。

循环遍历队列，每一次处理队列中所有等待处理的节点，这正是广度优先搜索的过程模拟。

取出队列头部的节点，将节点的值存入 vector，然后检查节点的左右儿子是否存在，如果存在，就将它们加入队列中，以便后续处理。

循环完一轮后，我们将存储着这一层节点的值的 vector 插入到结果数组中，再次进入循环处理队列中的下一层节点。

4. 逐层打印

4.1 逐层打印的定义

在层序遍历的基础上，逐层打印是指按层顺序逐层打印出每个节点的值，同一层的节点要分行打印，每行按照从左到右的顺序输出节点的值。

4.2 逐层打印的实现

逐层打印可以看作是将层序遍历的结果稍作处理，在每一层的节点的值后添加换行符即可。

下面是c++的实现代码：

vector<vector<int>> levelOrder3(TreeNode* root) {
  vector<vector<int>> result;
  if (!root) {
    return result;
  }
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    vector<int> level;
    int size = q.size();
    for (int i = 0; i < size; i++) {
      auto node = q.front();
      q.pop();
      level.push_back(node->val);
      if (node->left) {
        q.push(node->left);
      }
      if (node->right) {
        q.push(node->right);
      }
    }
    result.push_back(level);
  }
  return result;
}
void printTree(TreeNode* root) {
  auto levels = levelOrder3(root);
  for (auto& level : levels) {
    for (auto& val : level) {
      cout << val << " ";
    }
    cout << endl;
  }
}

同层的节点使用一个 vector 去存储，然后在将 node的左右子节点加入队列的处理过程中顺带统计一下需要换行的位置。

接下来，只需要按照规定的格式输出即可。

5. 智能指针建造二叉树

5.1 智能指针的定义

C++智能指针是一种自动管理内存的智能机制。

当程序员使用普通指针管理内存时，经常需要手动释放分配到的内存，很容易出现内存泄露或者使用了已经被释放的内存。

因此 C++ 可以使用智能指针来管理对象生命周期，使得程序员不需要关心释放对象的问题。

5.2 智能指针建造二叉树的实现

实际上，建立二叉树的时候也可以使用智能指针，智能指针作为一种智能的内存管理方式，可以很好地解决内存泄漏问题。

C++11 中的 std::unique_ptr，可以将一个指针转换为智能指针，并且当智能指针失效时，所指向的空间会自动被回收并且释放内存。

因此，建立二叉树时候使用 unique_ptr 可以有效地防止内存泄露。以下是使用 unique_ptr 建立二叉树的实现代码：

unique_ptr<TreeNode> buildTree(vector<int>& preorder, vector<int>& inorder) {
  if (preorder.empty() || inorder.empty()) {
    return nullptr;
  }
  auto rootValue = preorder[0];
  auto root = make_unique<TreeNode>(rootValue);
  auto it = find(inorder.begin(), inorder.end(), rootValue);
  int leftSize = it - inorder.begin();
  vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftSize);
  vector<int> leftInorder(inorder.begin(), it);
  root->left = buildTree(leftPreorder, leftInorder);
  vector<int> rightPreorder(preorder.begin() + 1 + leftSize, preorder.end());
  vector<int> rightInorder(it + 1, inorder.end());
  root->right = buildTree(rightPreorder, rightInorder);
  return root;
}

建立二叉树时候使用 unique_ptr 可以有效地防止内存泄露。

另外，对于不能删除智能指针的指针，我们可以使用 shared_ptr， 带引用计数的指针，来赋值。

6. 总结

本文主要介绍了 C++ 中如何实现二叉树的创建、层序遍历和逐层打印，还详细讲解了使用 unique_ptr 的智能指针来创建二叉树，避免内存泄漏的情况。

对于掌握二叉树基础知识的读者来说，这篇文章应该可以很好地辅助你理解和使用相关的算法和数据结构。