需要二叉树遍历代码解释

Question

我对这个二叉树遍历代码的工作原理有疑问。

void BinaryTree_Functions::preorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        cout <<  bt->data <<endl;
        preorder(bt->Left);
        preorder(bt->Right);
    }

前序遍历

    void BinaryTree_Functions::inorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        inorder(bt->Left);
        cout << bt->data << endl;
        inorder(bt->Right);
    }

中序遍历

    void BinaryTree_Functions::postorder(Binary_TreeNode* bt)
    {
        if (bt == NULL) { return; }
        postorder(bt->Left);
        postorder(bt->Right);
        cout << bt->data << endl;
    }

后序遍历

我知道这些遍历是如何工作的，但我不明白代码。

Answer 1

当你不说具体是什么让你感到困惑时，很难解释。问题似乎是递归。要更轻松地查看发生了什么，您可以使用示例树并查看输出有何不同。要了解不同的订单如何以不同的方式遍历这三个，您还可以查看这棵假树：

#include<iostream>
#include<string>

struct fake_tree {
    unsigned size = 4;
    void preorder(const std::string& node){
        if (node.size() >= size) return;
        std::cout << node << "\n";
        preorder(node+"l");
        preorder(node+"r");
    }
    void postorder(const std::string& node){
        if (node.size() >= size) return;
        postorder(node+"l");    
        postorder(node+"r");
        std::cout << node << "\n";
    }
    void inorder(const std::string& node){
        if (node.size() >= size) return;
        inorder(node+"l");
        std::cout << node << "\n";
        inorder(node+"r");
    }
};

int main()
{
    fake_tree ft;
    ft.preorder("0");
    std::cout << "\n";
    ft.postorder("0");
    std::cout << "\n";
    ft.inorder("0");
}

输出为：

0
0l
0ll
0lr
0r
0rl
0rr

0ll
0lr
0l
0rl
0rr
0r
0

0ll
0l
0lr
0
0rl
0r
0rr

输出直接告诉您输出是在调用堆栈中的哪个位置产生的。例如，最后一个 0rr 是由 inorder("0") 调用 inorder("0r") 产生的，后者又调用 inorder("0rr")。因为 inorder("0") 首先调用 inorder("0l") 然后打印 "0" 然后调用 inorder("0r")，这就是您在输出中看到的顺序。

同样 inorder("0r") 首先调用 inorder("0rl") 然后打印 "0r" 然后调用 inorder("0rr").

如果您现在在纸上画树，您可以跟踪不同的遍历如何以不同的方式穿过树。

需要二叉树遍历代码解释

binary tree traversal code explaination needed

c++

binary-tree

tree-traversal