如何使用C++创建二叉树并实现非递归遍历 |21xrx.com

如何使用C++创建二叉树并实现非递归遍历

2023-06-28 19:04:09 深夜i 15 0

C++ 二叉树非递归遍历创建实现

二叉树是一种数据结构，在计算机科学中被广泛应用。C++是一种面向对象的编程语言，它提供了丰富的类和函数库来实现二叉树的创建和操作。

在C++中，可以实现二叉树的创建和操作的方法有很多。以下是一种基于指针的方法。

首先，我们需要定义一个二叉树节点的类，它包含三个成员变量——左子节点、右子节点和节点值。

class TreeNode {
public:
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

然后，我们可以利用节点类来创建二叉树。在创建二叉树时，我们需要先构造根节点，然后将左右子节点添加到根节点。

TreeNode* createBinaryTree(vector<int>& nums) {
  // 判断数组是否为空
  if (nums.empty())
    return NULL;
  
  TreeNode* root = new TreeNode(nums[0]);
  // 创建队列并将根节点入队
  queue<TreeNode*> q;
  q.push(root);
  int i = 1;
  while (!q.empty() && i < nums.size()) {
    // 从队列中取出一个节点，并将其左右子节点添加到队列中
    TreeNode* curNode = q.front();
    q.pop();
    if (i < nums.size()) {
      if (nums[i] != NULL) {
        curNode->left = new TreeNode(nums[i]);
        q.push(curNode->left);
      }
      i++;
    }
    if (i < nums.size()) {
      if (nums[i] != NULL) {
        curNode->right = new TreeNode(nums[i]);
        q.push(curNode->right);
      }
      i++;
    }
  }
  return root;
}

在创建完二叉树后，可以利用非递归方式来遍历二叉树。

非递归方式遍历二叉树有三种方法：前序遍历、中序遍历和后序遍历。以下是三种方法的实现。

// 前序遍历
vector<int> preorderTraversal(TreeNode* root) {
  vector<int> res;
  if (!root)
    return res;
  
  stack<TreeNode*> s;
  s.push(root);
  while (!s.empty()) {
    TreeNode* curNode = s.top();
    s.pop();
    res.push_back(curNode->val);
    if (curNode->right) {
      s.push(curNode->right);
    }
    if (curNode->left) {
      s.push(curNode->left);
    }
  }
  return res;
}
// 中序遍历
vector<int> inorderTraversal(TreeNode* root) {
  vector<int> res;
  if (!root)
    return res;
  
  stack<TreeNode*> s;
  TreeNode* curNode = root;
  while (curNode || !s.empty()) {
    while (curNode) {
      s.push(curNode);
      curNode = curNode->left;
    }
    curNode = s.top();
    s.pop();
    res.push_back(curNode->val);
    curNode = curNode->right;
  }
  return res;
}
// 后序遍历
vector<int> postorderTraversal(TreeNode* root) {
  vector<int> res;
  if (!root)
    return res;
  
  stack<TreeNode*> s;
  s.push(root);
  while (!s.empty()) {
    TreeNode* curNode = s.top();
    s.pop();
    res.insert(res.begin(), curNode->val);
    if (curNode->left) {
      s.push(curNode->left);
    }
    if (curNode->right) {
      s.push(curNode->right);
    }
  }
  return res;
}

以上是利用C++创建二叉树并实现非递归遍历的方法。二叉树是一个非常重要的数据结构，它的应用在计算机科学中是非常广泛和重要的。

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

下一篇: C++逆向开发：破解软件+安全提升

评论区

相似文章