二叉树前序、中序、后序遍历(原理及其C++实现)

  令L,R,D分别代表遍历一个节点的左子树、右子树和访问该结点的操作，则二叉树有六种规则：DLR,LDR,LRD,DRL,RDL,RLD。若规定先左后右，则仅剩下前面三种规则，即DLR（前序遍历) 、LDR（中序遍历）、LRD（后续遍历）。
  总结一下，之所以叫前序、中序、后序，是因为访问根的优先级分别在前、中、后。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {
    }
};
//前序遍历（根左右）
void DLR(TreeNode* root, vector& traversal) {
    if (nullptr!=root)
        traversal.push_back(root->val);
    else 
        return;
    DLR(root->left, traversal);
    DLR(root->right, traversal);
    return;
}

//中序遍历（左根右）
void LDR(TreeNode* root, vector& traversal) {
    if (nullptr == root) 
        return;
    LDR(root->left, traversal);
    traversal.push_back(root->val);
    LDR(root->right, traversal);
    return;
}

//后续遍历（左右根）
void LRD(TreeNode* root, vector& traversal) {
    if (nullptr== root)
        return;
    LRD(root->left, traversal);
    LRD(root->right, traversal);
    traversal.push_back(root->val);
    return;
}

模板实现的二叉树及其遍历方式

【1】殷人昆 数据结构