C++二叉树代码 |21xrx.com

C++二叉树代码

2023-07-03 04:45:03 深夜i 8 0

C++ 二叉树代码

C++是一种高效的编程语言，被广泛应用于各种计算机领域。其中，二叉树是一种常见的数据结构，被用来处理树形数据。下面是一个简单的C++二叉树代码，用于插入、查找和删除二叉树节点。

定义二叉树节点结构体：

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

该结构体包含节点的值、左孩子节点和右孩子节点。

插入节点：

void insert(TreeNode* &root, int val)
{
  if (root == NULL)
  {
    root = new TreeNode(val);
    return;
  }
  if (val < root->val)
  {
    insert(root->left, val);
  }
  else if (val > root->val)
  {
    insert(root->right, val);
  }
  else // 若val已存在于树中，则不插入
  
    return;
  
}

该函数通过比较节点值，将新节点插入到合适的位置上。若该值已经存在，则不进行插入。

查找节点：

bool find(TreeNode* root, int val)
{
  if (root == NULL)
  
    return false;
  
  if (val == root->val)
  
    return true;
  
  else if (val < root->val)
  {
    return find(root->left, val);
  }
  else
  {
    return find(root->right, val);
  }
}

该函数通过比较节点值，找到与目标值相同的节点。若没找到，则返回false。

删除节点：

void del(TreeNode* &root, int val)
{
  if (root == NULL) // 该树为空
  
    return;
  
  if (val < root->val)
  {
    del(root->left, val);
  }
  else if (val > root->val)
  {
    del(root->right, val);
  }
  else // 若该节点是目标节点，进行删除操作
  {
    if (root->left == NULL) // 该节点没有左孩子
    {
      TreeNode* temp = root;
      root = root->right;
      delete temp;
    }
    else if (root->right == NULL) // 该节点没有右孩子
    {
      TreeNode* temp = root;
      root = root->left;
      delete temp;
    }
    else // 该节点有左右孩子
    {
      TreeNode* temp = root->right; // 找到右子树最小值节点
      while (temp->left != NULL)
      
        temp = temp->left;
      
      root->val = temp->val; // 用右子树最小值节点替换目标节点
      del(root->right, temp->val); // 递归删除右子树最小值节点
    }
  }
}

该函数通过比较节点值，找到与目标值相同的节点，并根据节点的情况进行删除操作。若该节点有左右孩子，则需要找到右子树的最小值节点，并替换目标节点。同时，需要递归删除右子树最小值节点。

通过这些简单的代码，我们可以实现插入、查找和删除二叉树节点的功能。这些功能是在C++中常用的数据结构和算法之一，可以用于各种计算机领域的应用，如游戏开发、机器学习等。

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

下一篇: C++中对象的定义及特点

评论区

相似文章