21xrx.com
2024-06-03 04:27:42 Monday
登录
文章检索 我的文章 写文章
C++实现二叉树的创建
2023-06-27 12:03:15 深夜i     --     --
C++ 二叉树 实现 创建 节点

二叉树是一种常见的数据结构,它由节点组成,每个节点最多有两个子树。C++语言中可以使用指针和结构体来实现二叉树的创建。

首先,定义一个结构体表示二叉树中的一个节点,它包含三个成员变量:节点数据、左子树指针和右子树指针。代码如下:


struct TreeNode {

  int val;

  TreeNode* left;

  TreeNode* right;

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

};

其中,val表示节点存储的数据,left和right分别表示左子树指针和右子树指针,这里使用nullptr表示空指针。

接下来,利用递归算法来创建二叉树。递归算法的思想是先递归创建左子树,再递归创建右子树,最后返回当前节点的指针。代码如下:


class Solution {

public:

  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

    if (preorder.empty() || inorder.empty())

      return nullptr;

    

    int rootVal = preorder[0];

    int rootIndex = 0;

    for (int i = 0; i < inorder.size(); i++) {

      if (inorder[i] == rootVal)

        rootIndex = i;

        break;

      

    }

    vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);

    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);

    vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());

    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());

    TreeNode* root = new TreeNode(rootVal);

    root->left = buildTree(leftPreorder, leftInorder);

    root->right = buildTree(rightPreorder, rightInorder);

    return root;

  }

};

在上述代码中,buildTree函数接收两个参数:preorder和inorder,它们分别表示二叉树的前序遍历和中序遍历。函数的返回值为二叉树的根节点指针。

具体实现过程如下:首先判断preorder和inorder是否为空,如果都为空则返回空指针;取preorder的第一个元素作为根节点的值;在inorder中找到根节点所在的位置rootIndex;将preorder和inorder分别拆分为左右子树的前序和中序遍历;创建根节点,递归创建左右子树,将它们分别作为根节点的左右子树指针,最后返回根节点指针。

通过上述递归算法,我们可以创建二叉树,而且可以通过前序遍历和中序遍历快速重构一棵二叉树。这里的方法可以具体在leetcode上测试,加深理解。

  
  

评论区

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