chapter_tree/binary_tree_traversal/

[giscus[bot]]

chapter_tree/binary_tree_traversal/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_tree/binary_tree_traversal/

[Slone123c]

点进去好像没有看见go的代码显示？ 想知道有没有机会贡献go的代码

[krahets]

哈喽，感谢您哇～你可以关注这个 issue ，Go 代码有 Reanon 同学在翻译了，还剩一章～我会尽快把 Go 代码贴到文章中

[gltianwen]

结点总数为 n 的二叉树的高度 Log2(n+1) - 1

[gltianwen]

所谓的前中后序遍历：先遍历父节点为preOrder，第二个遍历父节点为inOrder，最后遍历父节点为postOrder

[L-Super]

遍历方式：

• 前序遍历（先根，再左，最后右）
• 中序遍历（先左，再根，最后右）
• 后序遍历（先左，再右，最后根）

[zh-h]

用栈实现 dfs

[imarman]

这里的前中后序，指的是根结点吧

[krahets]

确实，含义是“根结点在何时被访问”

[yuelinxin]

问：为什么DFS遍历二叉树有前、中、后三种顺序，分别有什么用呢？

[yuelinxin]

答：DFS的前、中、后序遍历和访问数组的顺序类似，是遍历二叉树的基本方法，利用这三种遍历方法，我们可以得到一个特定顺序的遍历结果。

[krahets]

补充：例如在二叉搜索树中，由于结点大小满足 左子结点值 < 根结点值 < 右子结点值 ，因此我们只要按照 左 -> 根 -> 右 的优先级遍历树，即可获得有序序列。而这种优先级对应的正是「中序遍历」

[fallenleavesguy]

举个例子，UI结构一般是树结构，显示的层叠顺序，开发者采用的访问顺序不一样，会影响哪个元素会最后显示在最上面，即最后访问并渲染的那个元素。很多时候访问顺序产生不一样的程序结果

[chenwenstar]

递归利用栈的数据结构，代码的真少啊

[chen8866]

为啥没有c的代码，描述数据结构最好的代码就是c啊

[krahets]

呜呜，会尽快添加 C 语言版本的

[viogami]

你这个前、中、后序遍历的图简直太好了，把我至今抽象的理解具现化了 ❤️

[krahets]

这张图画了很久！哈哈哈

[fjiangfan]

真的，这张图太优美了，一个在我看来只能用动态图展示的道理用静态的形式就绝佳地呈现了出来，优雅！:bow:

[Telly-S]

binary_tree_bfs.c

/* 辅助队列 */
queue = (TreeNode **)malloc(sizeof(TreeNode) * MAX_NODE_SIZE);
这里的malloc是不是应该写为sizeof(TreeNode*) * MAX_NODE_SIZE呢？因为数组里面存的好像都是指针。

[Gonglja]

是的，queue中存储的为指针（在外部已经 malloc ），所以此处仅需为指针分配空间，也就是 sizeof(TreeNode *) * MAX_NODE_SIZE

[ronalgao]

空间复杂度：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 （N+1）/2个节点——满二叉树，bfs遍历到最底层之前，队列中的节点就是叶节点2的h次方吧？

[krahets]

是的，拿高度 h = 2 的满二叉树举例，节点总数 n = 7 ，易得底层节点数量 = 2^h = (n + 1) / 2

[ronalgao]

谢谢哈~

[Ares-bit]

给没看明白的朋友们推导下:
设满二叉树高度为h，总结点数为n，则有A：n = 2^(h+1) - 1
又知满二叉树最下层的叶子结点个数为：2^h
故由A可知2^h = (n + 1) / 2

[bukexiusi]

太牛啦，每次面试都需要复习一遍，这次永远不会忘记了

[WhiteRhinos]

前序遍历结合栈使用迭代

public void preOrder2(TreeNode root)
    {
        // 创建栈,加入根节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty())
        {
            TreeNode pop = stack.pop();
            System.out.println(pop.data);
            if (pop.right!=null)
            {
                stack.push(pop.right);
            }
            if (pop.left!=null)
            {
                stack.push(pop.left);
            }

        }

    }

[zhuasdfg]

牛哇，我结合画图才看明白，感觉栈比队列复杂一点，脑子有点转不过来

[WhiteRhinos]

队列是怎么实现前序遍历的

[is-liu]

用双向队列可以前序遍历，不过也是利用栈的思想，单纯的队列在我的认知里不能。
前序遍历的顺序是 根结点 -> 左子树 -> 右子树，如果左子树深度不为0会继续以这个顺序来查找左子树，直到左子树为空才会查找右子树。
广度优先搜索是逐层查找，只要深度相同即使两个结点的父节点不同也会一起查找。这就和前序遍历的顺序相违背

[zhuasdfg]

太棒了，对递归了解更多了一点，其他的广度优先和深度优先遍历是不是也用递归

[skllai11000]

广度优先搜索不是应该分析最后一层的节点数量吗，这里为什么要写到底最底层之前？

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[fuochai]

python3迭代实现已通过力扣

def pre_order(root: TreeNode | None):
    """前序遍历"""
    # 访问优先级：根节点 -> 左子树 -> 右子树
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        res.append(node.val)
        stack.append(node.right)
        stack.append(node.left)

def in_order(root: TreeNode | None):
    """中序遍历"""
    # 访问优先级：左子树 -> 根节点 -> 右子树
    stack = [root]
    while stack:
        node = stack[-1]
        if node is None:
            stack.pop()
            if not stack:
                return
            node = stack.pop()
            res.append(node.val)
            stack.append(node.right)
            continue
        stack.append(node.left)

    assert False

def post_order(root: TreeNode | None):
    """后序遍历"""
    # 访问优先级：左子树 -> 右子树 -> 根节点
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        res.append(node.val)
        stack.append(node.left)
        stack.append(node.right)
    res.reverse()

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[yuukidesu1]

pre_order(root=root.right) -> pre_order(root.right) 会不会更好？

[jiuerya7]

这两个没啥区别,root=root.right就是root.right,但是后者更加直观一些,建议使用后者

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[xiaozhuge123]

day06

[bx33661]

太棒了

[Introsb]

全文背诵

[guanshangshui]

"深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。"
这段话初学者真的能理解吗?我认为在这段话前面加上"前序遍历是以根-左-右的顺序遍历树的逻辑,中序是以左-根-右的顺序遍历,后序是以右-根-左的顺序遍历"更好,这样或许更能帮助初学者明白什么叫做"三个位置".

[Feng-Leave]

我认为这个很好，反而是左根右……不好理解，那个图清晰直观，比抽象的左根右要好的多，能更方便的在大脑中想象，然后沿着节点走一圈

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[guanshangshui]

这种二叉树基础功的练习我认为可以贴出一些题目链接加以练习,辅助理解.
https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked
https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/636119320/?envType=study-plan-v2&envId=top-100-liked
不知道为什么链接不能显示建议大家直接复制粘贴,搜索就好.

[fug-0117]

总结：1.层序遍历：用队列 添加一层节点 处理一层节点 然后迭代；2.前中后序遍历：根据根的遍历顺序来划分，根在前（根、左、右）处理为前序，中间（左、根、右）处理跟为中序，最后（左、右、根）处理跟为后续。

[liuyanqing1023]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[2450635073]

太绕了，但是对递归和二叉树的理解更深一点了，对于接触指针比较少的python选手理解起来有点费劲