21xrx.com
2024-11-22 13:14:52 Friday
登录
文章检索 我的文章 写文章
C++ 实现二叉树的创建方法
2023-06-26 14:50:06 深夜i     --     --
C++ 二叉树 创建方法

二叉树是一种常见的数据结构,它由根节点以及每个节点的左右子树组成,它可以用来存储有层次结构的数据。在 C++ 中,我们可以使用指针和动态内存分配来实现二叉树的创建和操作。

具体实现方法如下:

1. 定义二叉树节点的结构体,包含数据域和指向左右子树的指针(nullptr 表示空节点):


struct TreeNode {

  int val;

  TreeNode* left;

  TreeNode* right;

  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

2. 定义一个函数,用于根据给定的数据创建二叉树。函数接收一个数组作为参数,数组元素为每个节点的数值,其中第一个元素为根节点的数值。函数返回指向根节点的指针。


TreeNode* createTree(vector<int>& nums) {

  if (nums.empty()) return nullptr;

  int i = 0;

  TreeNode* root = new TreeNode(nums[i++]); // 创建根节点

  queue<TreeNode*> q{{root}}; // 用队列保存每一层的节点

  while (i < nums.size()) {

    TreeNode* cur = q.front();

    if (nums[i] != -1) { // 左子树非空

      cur->left = new TreeNode(nums[i]);

      q.push(cur->left);

    }

    i++;

    if (i < nums.size() && nums[i] != -1) { // 右子树非空

      cur->right = new TreeNode(nums[i]);

      q.push(cur->right);

    }

    i++;

    q.pop();

  }

  return root;

}

3. 在主函数中调用 createTree 函数,传入数据数组。


int main() {

  vector<int> nums = -1;

  TreeNode* root = createTree(nums);

  // 对二叉树进行其他操作

  return 0;

}

在上述代码中,数据数组 1 表示二叉树的形状为:


   1

  /  \

 2   3

    /

   4

    \

    5

其中,-1 表示空节点。接下来,我们可以对二叉树进行其他操作,例如搜索某个节点、遍历整棵树等。

二叉树虽然是一种基础的数据结构,但是它在算法和数据结构设计中扮演着重要的角色,是其他更为复杂的数据结构和算法设计的基础。了解二叉树的实现方法和使用场景,对于 C++ 开发和算法设计都是非常有益的。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复