C++二叉树前序遍历实现及示例 |21xrx.com

C++二叉树前序遍历实现及示例

2023-06-30 06:35:04 深夜i -- --

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

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

上一篇: idea打包java可执行jar包

下一篇: C++特殊数字：如何定义和使用？

评论区

()

相似文章