C++实现树结构 |21xrx.com

C++实现树结构

2023-06-30 19:24:59 深夜i -- --

C++ 树结构实现

树是一种常见的数据结构，在实际的计算机应用中也可以很好地解决很多问题。这里我们介绍使用C++语言实现树结构的方法。

要实现一棵树，我们可以通过定义节点的结构体来实现。其中，每个节点包括数据域和指向该节点的子节点的指针域，如下所示：


struct TreeNode
{
  int val; // 数据域
  TreeNode* left; // 左子节点指针域
  TreeNode* right; // 右子节点指针域
  TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

接下来，我们可以通过构造函数实现树的创建。以二叉搜索树为例，我们可以按照如下方式实现：


TreeNode* createBST(vector<int>& nums)
{
  if (nums.empty())
    return NULL;
  
  int mid = nums.size() / 2;
  TreeNode* root = new TreeNode(nums[mid]);
  vector<int> leftNums(nums.begin(), nums.begin() + mid);
  vector<int> rightNums(nums.begin() + mid + 1, nums.end());
  root->left = createBST(leftNums);
  root->right = createBST(rightNums);
  
  return root;
}

上述代码实现了通过给定一组有序整数序列，构建一棵二叉搜索树。其中，我们将序列分为左右两部分，然后递归构建左子树和右子树，并将子树根节点赋值给父节点的左右子节点指针域。

最后，我们可以通过遍历方式实现对树的访问。其中，主要有三种遍历方式：前序遍历，中序遍历和后序遍历。以中序遍历为例，我们可以如下实现：


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

上述代码实现了对一棵树的中序遍历。具体来说，我们可以遍历左子树，输出父节点，然后遍历右子树，以实现对一棵树的访问。

综上所述，我们可以通过定义节点结构体，构造函数和遍历方式实现树的创建和访问。具体实现可以根据需求来进行调整和改进，以达到更好的效果和应用。

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

下一篇: C++ C11简介及特性介绍

评论区

()

相似文章