二叉树的基本运算2

Salamander · · 457 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

这一篇是接上一篇文章二叉树的基本运算

二叉树的遍历

二叉树遍历分为三种:前序、中序、后序:

  • 前序遍历:根结点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根结点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根结点

另外还有一种层次遍历,即每一层都从左向右遍历。
譬如,对于下面的二叉树
14591414567288.jpg

前序遍历:abdefgc
中序遍历:debgfac
后序遍历:edgfbca
层次遍历:abcdfeg

实现方法

因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点

中序遍历

go实现

// 中序遍历,用栈实现
func inOrderBinaryTree1(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    stack := []*BinaryTreeNode{}
    top := -1

    for top >= 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            top++
            root = root.lChild
        }
        item := stack[top]
        stack = stack[:top]
        top-- // 出栈

        fmt.Print(item.data)
        if item.rChild != nil {
            root = item.rChild
        }
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:Salamander

查看原文:二叉树的基本运算2

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

457 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传