三种排序遍历的主体说的都是当前节点, 所以可以理解为:
- 前序: 中左右
- 中序: 左中右
- 后序: 左右中
这里有个例子,
# 一个最简单的树
A
B C
D E F G
struct Node {
Node *left;
Node *right;
char data;
};
void prePrint(Node *root) {
if (root == nullptr) return;
cout << root->data;
prePrint(root->left);
prePrint(root->right);
}
void inPrint(Node *root){
if (root == nullptr) return;
inPrint(root->left);
cout << root->data;
inPrint(root->right);
}
void afterPrint(Node *root){
if(root == nullptr) return;
afterPrint(root->left);
afterPrint(root->right);
cout << root->data;
}
int main() {
Node *d = new Node{nullptr, nullptr, 'D'};
Node *e = new Node{nullptr, nullptr, 'E'};
Node *f = new Node{nullptr, nullptr, 'F'};
Node *g = new Node{nullptr, nullptr, 'G'};
Node *b = new Node{d, e, 'B'};
Node *c = new Node{f, g, 'C'};
Node *root = new Node{b, c, 'A'};
cout << "pre :";
prePrint(root);
cout << endl;
cout << "in :";
inPrint(root);
cout << endl;
cout << "after:";
afterPrint(root);
cout << endl;
}
输出结果:
pre :ABDECFG
in :DBEAFCG
after:DEBFGCA
