21xrx.com
2025-04-02 01:04:57 Wednesday
文章检索 我的文章 写文章
C++实现二叉树的代码
2023-07-14 02:04:13 深夜i     11     0
C++ 二叉树 实现 代码 节点

二叉树是一种非常常见的数据结构，它能够快速的进行查找、插入和删除操作。在C++中，我们可以使用类来实现二叉树的代码，这样可以方便的存储二叉树的节点和相关信息。

在二叉树的代码实现中，我们首先需要定义二叉树的节点类。节点类存储了当前节点的值以及左右子树的指针，代码如下所示：

class TreeNode{
public:
  int val;      //当前节点的值
  TreeNode* left;   //左子树指针
  TreeNode* right;  //右子树指针
  TreeNode(int val):val(val),left(nullptr),right(nullptr){}  //构造函数
};

接下来，我们可以定义二叉树的类。在二叉树的类中，我们可以实现二叉树的插入、删除和查找操作。代码如下所示：

class BinaryTree{
public:
  TreeNode* root;   //二叉树的根节点指针
  BinaryTree():root(nullptr){}  //构造函数
  void Insert(int val){    //插入节点
    if(root==nullptr){   //如果二叉树为空
      root=new TreeNode(val); //直接将节点插入到根节点
    }else{   //如果二叉树不为空
      TreeNode* cur=root;   //从根节点开始遍历
      while(true){
        if(val<cur->val){  //如果插入的值小于当前节点的值
          if(cur->left==nullptr){   //如果左子树为空
            cur->left=new TreeNode(val);  //直接将新节点作为左子树插入
            return;
          }else   //如果左子树不为空
            cur=cur->left;   //继续向下遍历左子树
          
        }else if(val>cur->val){   //如果插入的值大于当前节点的值
          if(cur->right==nullptr){  //如果右子树为空
            cur->right=new TreeNode(val);  //直接将新节点作为右子树插入
            return;
          }else   //如果右子树不为空
            cur=cur->right;   //继续向下遍历右子树
          
        }else   //如果插入的值已经存在
          return;
        
      }
    }
  }
  bool Search(int val){    //查找节点
    TreeNode* cur=root;   //从根节点开始遍历
    while(cur!=nullptr){
      if(cur->val==val)   //如果找到了对应的节点
        return true;
      else if(val<cur->val)   //如果要查找的值小于当前节点的值
        cur=cur->left;   //向下遍历左子树
      else   //如果要查找的值大于当前节点的值
        cur=cur->right;   //向下遍历右子树
      
    }
    //如果找不到对应的节点，返回false
    return false;
  }
  void Delete(int val){    //删除节点
    //先查找节点是否存在
    if(Search(val)){
      DeleteHelper(root,val);
    }else
      std::cout<<"Node not found!"<<std::endl;
    
  }
  //删除节点的辅助函数
  TreeNode* DeleteHelper(TreeNode* cur,int val){
    if(cur==nullptr)    //如果当前节点为空
      return cur;
    else if(val<cur->val){   //如果要删除的节点在左子树中
      cur->left=DeleteHelper(cur->left,val);   //递归删除左子树中的节点
      return cur;
    }else if(val>cur->val){   //如果要删除的节点在右子树中
      cur->right=DeleteHelper(cur->right,val);  //递归删除右子树中的节点
      return cur;
    }else{   //如果找到了要删除的节点
      //如果当前节点没有左右子树
      if(cur->left==nullptr && cur->right==nullptr)
        delete cur;
        return nullptr;
      
      //如果当前节点只有左子树或右子树
      else if(cur->left==nullptr){
        TreeNode* temp=cur->right;
        delete cur;
        return temp;
      }else if(cur->right==nullptr){
        TreeNode* temp=cur->left;
        delete cur;
        return temp;
      }
      //如果当前节点左右子树均存在
      else{
        //找到右子树中的最小节点
        TreeNode* temp=cur->right;
        while(temp->left!=nullptr)
          temp=temp->left;
        
        //将当前节点的值修改为右子树中最小节点的值
        cur->val=temp->val;
        //递归删除右子树中的最小节点
        cur->right=DeleteHelper(cur->right,temp->val);
        return cur;
      }
    }
  }
};

通过以上的代码实现，我们就可以快速的实现二叉树的操作，从而方便的进行查找、插入和删除等操作。在实际的应用中，二叉树还有很多优化和扩展的操作，可以根据具体的需求进行实现。

  
  

评论区