21xrx.com
2025-06-20 05:07:19 Friday
文章检索 我的文章 写文章
C++二叉树前序遍历实现及示例
2023-06-30 06:35:04 深夜i     22     0
C++ 二叉树 前序遍历 实现 示例

二叉树是计算机科学中的一种常见数据结构，它由一个根节点和最多两个子节点组成，其中每个节点都可以看作是一个独立的二叉树。二叉树的遍历是指按照某种顺序遍历所有的节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。在C++中，二叉树的前序遍历可以采用递归方式或栈的方式实现。

以下是C++二叉树前序遍历的递归实现：

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void preorderTraversal(TreeNode* root) {
  if (!root) return;
  cout << root->val << " ";
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

在上述代码中，preorderTraversal函数接收一个指向根节点的指针root作为参数，它首先检查root是否为空，如果是则返回。如果root不为空，则输出它的值，并递归遍历左子树和右子树。

以下是C++二叉树前序遍历的非递归实现：

void preorderTraversal(TreeNode* root) {
  stack<TreeNode*> s;
  TreeNode* p = root;
  while (!s.empty() || p) {
    if (p) {
      cout << p->val << " ";
      s.push(p);
      p = p->left;
    }
    else {
      TreeNode* node = s.top();
      s.pop();
      p = node->right;
    }
  }
}

在非递归实现中，我们使用一个栈来模拟递归调用的过程。我们首先将根节点压入栈中，然后不断地从栈中弹出元素，并输出它的值，依次遍历左子树和右子树。当遇到一个节点，它的左子树为空时，我们从栈中弹出上一个节点，然后遍历它的右子树。整个遍历过程直到栈为空时结束。

以下是一个示例，我们依次插入节点3、2、4、1、8到二叉树中：

TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(4);
root->left->left = new TreeNode(1);
root->right->right = new TreeNode(8);

然后我们可以使用preorderTraversal函数来遍历这个二叉树：

preorderTraversal(root);
// 输出: 3 2 1 4 8

可以看到，我们成功地输出了二叉树的前序遍历结果。这个方法也可以用来遍历其他类型的树，只需要稍作修改。

  
  

评论区