先中后序遍历

先中后的含义

  • 先中后代表了根节点的访问次序
  • 一定会先遍历左结点再遍历右结点

假设对于一个结点（N） 他的左结点（L） 他的右节点（R）按照先中后序进行遍历的遍历顺序如下

遍历方法 遍历结果
先序遍历 NLR
中序遍历 LNR
后续遍历 LRN

遍历时的注意点

对于某个结点来说一定要将此结点按照指定的遍历顺序遍历完全

  • 例如如果按照中序遍历准备开始遍历某个结点时，就要依照遍历顺序先遍历左结点
  • 并且在遍历左结点时，也要按照遍历顺序进行遍历，对当前左结点的左结点进行中序遍历
  • 只有当某个结点的左节点为空时，才能按照指定的遍历顺序选择当前遍历中的下一个应该遍历的结点 在当前例子中应该选择根节点进行遍历
  • 在当前遍历的所有左中右结点都遍历过一遍后才向上继续遍历
  • 在执行时应该具有递归思维

遍历的例子

二叉树-loop.drawio

按照先序遍历（中左右）

  1. 从结点1开始先遍历到结点1 输出1
  2. 接着开始遍历结点2
  3. 对于以结点2为根节点的遍历先遍历到结点2 输出2
  4. 接着开始遍历结点4
  5. 对于以结点4为根节点的遍历先遍历到结点4 输出4
  6. 由于结点4没有左右结点 所以紧接着的遍历都为空
  7. 由于左中右结点都被遍历完全 因此现在回到以结点2作为根节点的遍历当中
  8. 由于已经按照顺序 中左右遍历了结点2和结点4 所以现在开始遍历结点5
  9. 对于以结点5为根节点的遍历先遍历到结点5 输出5
  10. 由于结点5没有左右结点 所以紧接着的遍历都为空
  11. 由于左中右结点都被遍历完全 因此现在回到以结点2作为根节点的遍历当中
  12. 由于结点2作为根节点的遍历 已经将左中右结点都遍历完全 因此现在回到以结点1作为根节点的遍历当中
  13. 由于已经按照顺序 中左右遍历了结点1和结点2 所以现在开始遍历结点3
  14. 对于以结点3为根节点的遍历先遍历到结点3 输出3
  15. 接着按照顺序接着遍历左结点6
  16. 对于以结点6为根节点的遍历先遍历到结点6 输出6
  17. 由于结点6没有左右结点 所以紧接着的遍历都为空
  18. 由于左中右结点都被完全遍历 因此现在回到以结点3作为根节点的遍历当中
  19. 接着按照顺序遍历右节点 但由于结点3没有右结点
  20. 由于左中右结点都被完全遍历 因此现在回到以结点1作为根节点的遍历当中
  21. 由于左中右结点都被完全遍历 并且现在已经在结点1上 往上没有结点了 所以遍历结束
  22. 遍历序列为 1 2 4 5 3 6

代码语言实现先中后序遍历

先序遍历

1
2
3
4
5
6
7
8
9
10
int PreOrderLoop(BinaryTree tree) {
    if (tree != NULL) {
        // 先序遍历在对每一个结点的遍历都遵循先遍历中间结点，再遍历左结点，再遍历右节点
        PreOrderLoop(tree);
        PreOrderLoop(tree -> lchild);
        PreOrderLoop(tree -> rchild);
        
    }
    
}

中序遍历

1
2
3
4
5
6
7
8
9
10
int MidOrderLoop(BinaryTree tree) {
    if (tree != NULL) {
        // 中序遍历在对每一个结点的遍历都遵循先遍历左结点，再遍历中间结点，再遍历右节点
        MidOrderLoop(tree -> lchild);
        MidOrderLoop(tree);
        MidOrderLoop(tree -> rchild);
        
    }
    
}

后序遍历

1
2
3
4
5
6
7
8
9
10
int LatOrderLoop(BinaryTree tree) {
    if (tree != NULL) {
        // 后序遍历在对每一个结点的遍历都遵循先遍历左结点，再遍历右结点，再遍历中间节点
        LatOrderLoop(tree -> lchild);
        LatOrderLoop(tree -> rchild);
        LatOrderLoop(tree);
        
    }
    
}

层序遍历

层序遍历的顺序

从第一层开始 从左往右 从上到下依次输出结点的数据

对于一个完全二叉树而言

输出的序列按照结点编号而言就是$1\sim n$ 依次输出

代码语言

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义链式二叉树的结构体
typedef struct {
    ElemType value;			// 结点存放的值
    Node *lchild,*rchild;	// 结点的指向结点的左结点和右结点的指针
}BinaryTree, *Node;

// 定义队列
typedef struct {
    *Node value;		// 结点存放的值
    SNode *next;		// 结点指向的下一个结点指针
}*SNode;

typedef struct {
    SNode *front,*rear;	// 队列的队头指针和队列的队尾指针
}LinkQueue;

进行层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int loopWithNum(BinaryTree tree) {   //标准命名为 LevelOrder
    // 1. 读取二叉树的根节点并放入队列
    
    // 2. 移除根节点并按左结点、右节点的顺序 加入左结点和右结点到队列当中
    
    // 3. 对于每个在队列即将出队的结点都将重复此操作
    
    LinkQueue.push(tree);		//  EnQueue(Queue,Tree);
    while (LinkQueue -> next) {
        // 取出队列的队头结点
        Node* out = LinkQueue.pop(); // DeQueue(Q)
        // 在这里可以打印结点的value
        //  ..... 
        // 加入取出结点的左结点和右节点（如果有得话）
        if (out -> lchild) {
            LinkQueue.push(out -> lchild);
        }
        if (out -> rchild) {
            LinkQueue.push(out -> rchild);
        }
        
    }
}