Haskell递归添加二叉树节点并跟踪访问次数实现求助

1. 先明确基础数据类型 #

假设你已经定义了类似如下的树节点与Zipper结构（如果你的定义有差异，可对应调整）：

-- 带访问次数的二叉树节点
data Tree a = Empty | Node { val :: a, count :: Int, left :: Tree a, right :: Tree a }
  deriving (Show, Eq)

-- Zipper上下文：记录父节点到当前节点的路径信息
data Direction a = LeftDir a Int (Tree a)  -- 父节点值、计数、父节点右子树
                 | RightDir a Int (Tree a) -- 父节点值、计数、父节点左子树
  deriving (Show, Eq)

-- Zipper结构：当前节点 + 上下文路径
type Zipper a = (Tree a, [Direction a])

2. 实现Zipper核心辅助操作 #

这些函数用于在树中移动并维护结构一致性：

-- 从子节点Zipper回溯到父节点，用新子树替换原位置
up :: Zipper a -> Zipper a
up (child, LeftDir pVal pCount pRight : ctx) = 
  (Node pVal pCount child pRight, ctx)
up (child, RightDir pVal pCount pLeft : ctx) = 
  (Node pVal pCount pLeft child, ctx)
up (_, []) = error "无法从根节点向上回溯"

-- 移动到当前节点的左子节点
left :: Zipper a -> Zipper a
left (Node v c l r, ctx) = (l, LeftDir v c r : ctx)
left (Empty, _) = error "空节点没有左子树"

-- 移动到当前节点的右子节点
right :: Zipper a -> Zipper a
right (Node v c l r, ctx) = (r, RightDir v c l : ctx)
right (Empty, _) = error "空节点没有右子树"

3. 实现addNode函数 #

递归导航到合适位置，完成插入或计数更新，同时回溯维护树结构：

addNode :: Ord a => a -> Zipper a -> Zipper a
addNode x (Empty, ctx) = 
  -- 当前为空节点，直接插入新节点（初始计数为1）
  (Node x 1 Empty Empty, ctx)
addNode x z@(Node v c l r, ctx)
  | x == v = 
      -- 值匹配，仅更新当前节点访问计数
      (Node v (c+1) l r, ctx)
  | x < v = 
      -- 向左子树递归插入，回溯后更新父节点左子树
      let newLeftZipper = addNode x (left z)
      in up newLeftZipper
  | otherwise = 
      -- 向右子树递归插入，回溯后更新父节点右子树
      let newRightZipper = addNode x (right z)
      in up newRightZipper

4. 使用示例 #

-- 初始化根节点为5（计数1）的Zipper
initialZipper :: Zipper Int
initialZipper = (Node 5 1 Empty Empty, [])

-- 插入5，根节点计数变为2
afterInsert5 :: Zipper Int
afterInsert5 = addNode 5 initialZipper
-- 输出：(Node 5 2 Empty Empty, [])

-- 再插入1，根节点计数保持2，左子节点为1（计数1）
afterInsert1 :: Zipper Int
afterInsert1 = addNode 1 afterInsert5
-- 输出：(Node 5 2 (Node 1 1 Empty Empty) Empty, [])

关键逻辑说明 #

• 递归过程中，每次先移动到目标子节点的Zipper完成操作，再通过up回溯更新父节点的子树引用，保证整个树结构正确。
• 值相等时仅递增访问计数，不新增节点；空节点位置直接插入新节点，计数初始化为1。
• 依赖Ord a约束保证二叉搜索树的排序规则生效。

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