Golang实现二叉树节点弹出操作指南

Golang实现二叉树节点弹出操作指南 我正在尝试使用二叉树实现栈。在保持栈概念的前提下，如何从二叉树中弹出元素，这一点让我感到困惑。

3 回复

非常感谢

更多关于Golang实现二叉树节点弹出操作指南的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


要使用二叉树实现栈，你可以将栈深度作为键值。栈深度即二叉树中的元素数量。

要从二叉树中弹出元素，你需要移除键值为元素数量的条目。

func (t *BinaryTree) Push(value interface{}) {
    t.Insert(t.Len()+1, value)
}

func (t *BinaryTree) Pop() interface{} {
    if t.Len() == 0 {
        panic("pop empty stack")
    }
    value := t.Value(t.Len())
    t.Remove(t.Len())
    return value
}

在二叉树中实现栈的弹出操作，需要将二叉树视为后进先出（LIFO）结构。通常，这可以通过维护一个指向最后插入节点的指针来实现。弹出时，需要找到当前节点的父节点，并更新指针。以下是具体实现示例：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Stack struct {
    root   *TreeNode
    top    *TreeNode
    parent *TreeNode // 用于跟踪top的父节点
}

func (s *Stack) Push(val int) {
    newNode := &TreeNode{Val: val}
    if s.root == nil {
        s.root = newNode
        s.top = newNode
        s.parent = nil
        return
    }
    // 始终将新节点作为top的右子节点插入（模拟栈顶）
    s.parent = s.top
    s.top.Right = newNode
    s.top = newNode
}

func (s *Stack) Pop() (int, bool) {
    if s.top == nil {
        return 0, false
    }
    val := s.top.Val
    // 如果top是根节点
    if s.parent == nil {
        s.root = nil
        s.top = nil
        return val, true
    }
    // 断开top节点
    s.parent.Right = nil
    s.top = s.parent
    // 向上查找新的父节点
    s.parent = s.findParent(s.root, s.top)
    return val, true
}

func (s *Stack) findParent(root, target *TreeNode) *TreeNode {
    if root == nil || root == target {
        return nil
    }
    var parent *TreeNode
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node.Left == target || node.Right == target {
            parent = node
            break
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    return parent
}

这个实现中，Push操作始终将新节点添加为当前top节点的右子节点，以保持栈的顺序。Pop操作移除top节点，并将top更新为其父节点，同时通过findParent方法重新定位新的父节点。这种方法确保了二叉树模拟栈的后进先出行为。

回到顶部