介绍

二叉树的遍历可以说是二叉树最重要的一个内容，如果想对树的算法有一定的认识，那么二叉树的遍历是一定要熟练使用的，本文将主要介绍一下二叉树的遍历。

算法实现

先序遍历

先序、中序、后序遍历中的序就是访问根节点的顺序。先序遍历也就是先访问根节点。

递归先序遍历

void order_traversal(BiTree T)

{
  if(T!=NULL)
  {
​    visit(T);
​    order_traversal(T->lchild);
​    order_traversal(T->rchild);
  }
}
1
2
3
4
5
6
7
8
9
10

非递归先序遍历

void Preorder_traversal(BiTree T)
{
    initStack(S);
    BiTree p;
    p=T;
    while(p!=null||(!isEmpty(S)))
    {
    if(p!=null)
    {
        push(S,p);
        visit(p);
        p=p->lchild;
    }
    else
    {
        pop(S,p);
        p=p->rchild;
    }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

中序遍历

递归二叉树遍历

void order_traversal(BiTree T)
{
    if(T!=NULL)
    {
        order_traversal(T->lchild);
        visit(T);
        order_traversal(T->rchild);
    }
}
1
2
3
4
5
6
7
8
9

非递归中序遍历

算法思路：

1. 沿着根节点的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的节点
2. 栈顶元素出栈并访问：若其右孩子为空，继续执行 2；若其右孩子不空，将右子树转执行1.

void Medorder_traversal(BiTree T)
{
    InitStack(S);
    BiTree p=T;
    while(!IsEmpty(S)||p)
    {
        if(p)   //一路向左
        {
        push(S,p);
        p=p->lchild;
        }
        else
        {
            pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

后序遍历

递归后序遍历

void order_traversal(BiTree T)
{
    if(T!=NULL)
    {
        order_traversal(T->lchild);
        order_traversal(T->rchild);
        visit(T);
    }
}
1
2
3
4
5
6
7
8
9

非递归后序遍历

非递归后序遍历的算法比较难，这里着重介绍一下。

后序遍历二叉树应该先访问左子树，再访问右子树，最后访问根节点。

算法思路：

从根节点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左子树的节点，但是此时不能出栈并访问，因为如果有其右子树，还需按相同的规则对其右子树进行处理。直到上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早就访问完），这样就保证了正确的访问顺序。

1. 沿着根节点的左孩子，依次入栈，直到左孩子为空

2. 读栈顶元素：若其右孩子非空，且未被访问过，则右子树转来执行 1 ，否则栈顶元素出栈并访问。

上述算法思路中，第2步必须分清是从左子树返回的，还是右子树返回的。因此设定一个辅助指针，指向最近访问过的节点，也可在节点中增加一个标志域，记录是否已被访问。

void PostOrder(BiTree T)
{
    initStack(S);
    p=T;
    r=NULL;
    while (p||!IsEmpty(S))
    {
        if(p)
    {
        push(S,p);
        p=p->lchild;
    }
    else
    {
    GetTop(S,p);
    if(p->rchild&&p->rchild!=r)
    {
        p=p->rchild;
    }
    else
    {
        pop(S,p);
        visit(p);
        r=p;
        p=NULL;
    }
    }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注：每次出栈访问完一个节点就相当于遍历完以该节点为根节点的子树，所以要将该节点置NULL;

对于后序非递归遍历，当一个节点的左右子树都被访问后才能出栈。实际上，访问一个节点p时，栈中节点恰好是p节点的所有祖先，从栈底到栈顶节点再加上p节点，刚好构成从根节点到p节点的一条路径，此算法在求根节点到某节点的路径，两个节点的最近公共祖先上都有其作用。

层次遍历

层次遍历一般借助于一个队列。

void LevelOrder(BiTree T)
{
     InitQueue(Q);
     BiTree p=T;
     Enqueue(p);
     while(!QueueEmpty(Q))
     {
        Dequeue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
        Enqueue(p->lchild);
        if(p->rchild!=NULL)
        Enqueue(p->rchild);
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

后续

欢迎关注公众号：物联网知识