二叉树是一种非常重要的数据结构，它可以用来表示一些比较复杂的问题，例如文件系统、DOM树、表达式求值等等。在C++中，我们可以通过指针来实现二叉树的建立和遍历，这些操作是非常基础的数据结构知识，在学习算法和数据结构的时候必不可少。

一、 二叉树的建立

二叉树的建立是从一个空树开始，通过不断添加节点来形成的。每个节点都有一个值和两个指针，指向左儿子和右儿子。我们可以通过递归的方式来建立二叉树，具体实现如下：

#include <iostream>
using namespace std;
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void insert(TreeNode*& root, int value) {
  if (root == NULL) {
    root = new TreeNode(value);
    return;
  }
  if (value < root->val) {
    insert(root->left, value);
  }
  else {
    insert(root->right, value);
  }
}

二、 二叉树的遍历

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。这三种方式的遍历顺序不同，访问节点的顺序也不同，下面一一介绍。

1. 前序遍历

前序遍历的顺序是 根节点 -> 左子树 -> 右子树，即先访问当前节点，再访问左子树，最后访问右子树。

void preorderTraversal(TreeNode* root) {
  if (root == NULL)
    return;
  
  cout << root->val << " ";
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

2. 中序遍历

中序遍历的顺序是 左子树 -> 根节点 -> 右子树，即先访问左子树，再访问当前节点，最后访问右子树。

void inorderTraversal(TreeNode* root) {
  if (root == NULL)
    return;
  
  inorderTraversal(root->left);
  cout << root->val << " ";
  inorderTraversal(root->right);
}

3. 后序遍历

后序遍历的顺序是 左子树 -> 右子树 -> 根节点，即先访问左子树，再访问右子树，最后访问当前节点。

void postorderTraversal(TreeNode* root) {
  if (root == NULL)
    return;
  
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  cout << root->val << " ";
}

三、 总结

通过以上的介绍，我们可以知道，在C++中实现二叉树的建立和遍历是非常简单的，只需要用指针来维护节点之间的连接关系，然后使用递归的方式来访问节点即可。学习这些基础知识可以帮助我们更好地理解和应用更高级的算法和数据结构，也能够让我们写出更加高效和优雅的代码。

相似文章
• C++二叉树前序遍历实现及示例
  二叉树是计算机科学中的一种常见数据结构，它由一个根节点和最多两个子节点组成，其中每个节点都可以看作是一个独立的二叉树。二叉树的遍历是指按照某种顺序遍历所有的节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。在C++中，二叉树的前序遍历可以
  
  
• C++代码-二叉树前序遍历
  二叉树是一种数据结构，它由根节点和两个子树（左子树和右子树）组成。二叉树具有许多优点，例如它可以用作搜索树或平衡树等。
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政