二叉树的遍历：前序、中序、后序遍历，递归

image.png

性质：

  • 已知先序和中序，可以确定出二叉树
  • 已知中序和后序，可以确定出二叉树
  • 已知先序和后序，不可以确定出二叉树
  1. // 链式存储结构
  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. struct node{
  7.     char data;
  8.     node *lchild, *rchild;
  9. };
  11. node *root;
  13. // 按先序输入二叉树的结点，输入$表示空树
  14. void build(node* &p){
  15.     char c;
  16.     scanf("%c", &c);
  18.     if (c == '$') p = NULL;
  19.     else{
  20.         p = new node();
  21.         p->data = c;
  22.         build(p->lchild); build(p->rchild);
  23.     }
  24. }
  26. void pre_order(node *p){
  27.     if (p == NULL) return;
  29.     if (p->data != '$') cout << p->data;
  30.     pre_order(p->lchild);
  31.     pre_order(p->rchild);
  32. }
  34. void in_order(node *p){
  35.     if (p == NULL) return;
  37.     in_order(p->lchild);
  38.     if (p->data != '$') cout << p->data;
  39.     in_order(p->rchild);
  40. }
  42. void post_order(node *p){
  43.     if (p == NULL) return;
  45.     post_order(p->lchild);
  46.     post_order(p->rchild);
  47.     if (p->data != '$') cout << p->data;
  48. }
  50. int main(){
  51.     build(root);
  53.     pre_order(root);
  54.     puts("");
  56.     in_order(root);
  57.     puts("");
  59.     post_order(root);
  60.     puts("");
  62.     return 0;
  63. }
  65. /*
  67. 输入：AB$$C$$
  69. 输出：
  70. ABC
  71. BAC
  72. BCA
  74. */

例题，【例3-4】求后序遍历

  1. //给出先序和中序，求后续
  2. void dfs(int l1, int r1, int l2, int r2)
  3. //根据先序l1位置的根，去找中序中根的位置

例题，【例3-5】扩展二叉树

  1. //给出扩展二叉树的先序序列，输出中序和后序
  2. //题解给出的是指针写法【指针】

例题，二叉树遍历(flist)

  1. //给出中序序列和按层序列，求先序序列
  2. //在按层遍历序列中先遇到根，在中序序列中，找到根的位置，break出来
  3. //进行递归处理
  4. void dfs(int l1, int r1, int l2, int r2)