基于R语言R6类创建二叉搜索树的错误排查与正确实现

问题场景 #

使用R6类实现二叉搜索树时遇到两个问题：

1. 运行代码触发错误：Error in self$node <- Node$new(data) : cannot add bindings to a locked environment
2. 若在BST类的public中添加node <- NULL，会导致递归插入失败，所有节点始终为NULL

原代码如下：

library(R6)

Node <- R6Class(  
  classname = 'Node',  
  public = list(
    
    val = NULL,
    left = NULL,
    right = NULL,
    
    initialize = function(val = NULL, left = NULL, right = NULL){
      
      self$val <- val
      self$left <- left
      self$right <- right
      
    }
  )
)

BST <- R6Class(
  
  classname = 'BST',
  
  public = list(
    
    root = NULL,
    # node = NULL,
    
    insert = function(data){
      
      if(is.null(self$root)){
        self$node <- Node$new(data)
      }else{
        self$insert_recur(data, self$root)
      }
      
    },
    
    insert_recur = function(data, cur_node){
      
      if(data < cur_node$val){
        if(is.null(cur_node$self)){
          cur_node$left <- Node$new(data)
        }else{
          insert_recur(data, cur_node$left)
        }
      }else if(data > cur_node$val){
        if(is.null(cur_node$self)){
          cur_node$right <- Node$new(data)
        }else{
          insert_recur(data, cur_node$right)
        }
      }else{
        print('value already in tree')
      }
      
    },
    
    get_height = function(cur_node){
      
      if(is.null(cur_node$val)){
        return(-1)
      }else{
        return(max(self$get_height(cur_node$left),self$get_height(cur_node$right))+1)
      }
    }
    
  )
)

bst <- BST$new()
bst$insert(3)
bst$insert(2)
bst$insert(1)
bst$insert(5)
bst$insert(6)
bst$insert(4)
bst$insert(7)

错误原因分析 #

1. 动态添加成员报错：R6类的环境是锁定的，不能在运行时动态添加未预先声明的成员。原代码中self$node未在BST类的public列表中定义，直接赋值会触发锁定环境错误；且实际上二叉搜索树只需要维护root节点，完全不需要额外的node成员。
2. 递归逻辑错误：
   • 判断子节点是否为空时，错误使用cur_node$self（Node类中不存在self成员），应该判断cur_node$left或cur_node$right是否为NULL。
   • 递归调用insert_recur时未使用self$前缀，导致无法找到类内的方法。
3. 高度计算逻辑错误：get_height函数中先判断cur_node$val是否为NULL，当cur_node本身为NULL时，访问cur_node$val会直接报错，应该先判断cur_node是否为NULL。

修正后的完整代码 #

library(R6)

Node <- R6Class(  
  classname = 'Node',  
  public = list(
    val = NULL,
    left = NULL,
    right = NULL,
    
    initialize = function(val = NULL, left = NULL, right = NULL){
      self$val <- val
      self$left <- left
      self$right <- right
    }
  )
)

BST <- R6Class(
  classname = 'BST',
  public = list(
    root = NULL,
    
    insert = function(data){
      if(is.null(self$root)){
        # 直接初始化root节点，不需要额外的node成员
        self$root <- Node$new(data)
      }else{
        self$insert_recur(data, self$root)
      }
    },
    
    insert_recur = function(data, cur_node){
      if(data < cur_node$val){
        # 判断左子节点是否为空
        if(is.null(cur_node$left)){
          cur_node$left <- Node$new(data)
        }else{
          # 递归调用需加self$前缀
          self$insert_recur(data, cur_node$left)
        }
      }else if(data > cur_node$val){
        # 判断右子节点是否为空
        if(is.null(cur_node$right)){
          cur_node$right <- Node$new(data)
        }else{
          self$insert_recur(data, cur_node$right)
        }
      }else{
        print('value already in tree')
      }
    },
    
    get_height = function(cur_node){
      # 先判断节点本身是否为空
      if(is.null(cur_node)){
        return(-1)
      }else{
        return(max(self$get_height(cur_node$left), self$get_height(cur_node$right)) + 1)
      }
    }
  )
)

# 测试代码
bst <- BST$new()
bst$insert(3)
bst$insert(2)
bst$insert(1)
bst$insert(5)
bst$insert(6)
bst$insert(4)
bst$insert(7)

# 验证高度计算
cat("BST高度：", bst$get_height(bst$root), "\n")

修正说明 #

• 移除了无用的node成员，初始化时直接赋值给self$root
• 修正递归插入时的节点空判断逻辑，改为检查left/right子节点
• 递归调用类方法时添加self$前缀，确保方法能被正确找到
• 修复get_height函数的空节点判断逻辑，先检查节点本身是否为NULL

内容的提问来源于stack exchange，提问作者Ankur Lahiri