二叉树的遍历

Posted on | In | Visitors:

递归算法虽然简单，但是执行效率并不高。对于二叉树的遍历，可以根据工作栈的状态的变化来将递归算法化得非递归算法

前序遍历

在访问某个结点后，应该将该结点的指针保存到栈中，以便以后通过它能访问其右子树。一般的，设要遍历的二叉树的根为root，初始时工作指针bt指向root，有两种情况：

  • bt != NULL，表明当前二叉树不为空， 此时输出bt的值，然后将bt保存到栈中，准备继续遍历bt的左子树。
  • bt == NULL，表明以bt为根的二叉树遍历完毕，并且bt是栈顶指针所指结点的左子树，如果此时栈非空，则根据栈顶指针所指结点找到待遍历右子树的根指针并赋予bt，继续遍历；若栈空，则表明整个二叉树遍历完毕。程序结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(BiTree *root){
    BiTree *S[MAXN],*bt = root;    //定义顺序栈和工作指针
    int top = -1;    //初始化顺序栈
    while(bt != NULL || top != -1){
        while(bt != NULL){
            print(bt->data);
            S[++top] = bt;
            bt = bt->lchild;
        }
        if(top != -1){
            bt = S[top--];
            bt = bt->rchild;
        }
    }

}

中序遍历

中序遍历中访问结点的操作发生在遍历完其左子树并准备访问其右子树时，所以在遍历过程中遇到结点不能立即访问它，应先将其压栈，等它的左子树访问完毕时，再弹出访问之。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void midOrder(BiTree *root){
    BiTree *S[MAXN],*bt = root;
    int top = -1;
    while(bt != NULL || top != -1){
        while(bt != NULL){
            S[++top] = bt;
            bt = bt->lchild;
        }
        if(top != -1){
            bt = S[top--];
            print(bt->data);
            bt = bt->rchild;
        }
    }
}

后序遍历

后序遍历与前序中序有点不同，当访问完结点的左子树后，由于右子树还没有遍历，所以栈顶结点不能出栈，通过栈顶结点找到它的右子树，当遍历完右子树，将栈顶结点出栈并访问。
为区别对栈顶结点的不同处理，可以设置一个标志位flag，flag==1表示左子树遍历完毕，栈顶结点不能出栈，flag==2表示右子树遍历完毕，可以将栈顶元素出栈访问。

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
typedef struct{
    BiTree *ptr;
    int flag;
}ElemType;
void postOrder(BiTree *root){
    ElemType S[MAXN];
    int top = -1;
    BiTree *bt = root;
    while(bt != NULL || top != -1){
        while(bt != NULL){
            top++;
            S[top].ptr = bt;
            S[top].flag = 1;
            bt = bt->lchild;
        }
        while(top !=-1 || bt->flag == 2){
            bt = S[top--].ptr;
            print(bt->data);
        }
        if(top != -1){
            S[top].flag = 2;
            bt = S[top].ptr->rchild;
        }
    }
}

层序遍历

在进行层序遍历的时候，访问某一层的结点后，还需要对其左右孩子进行顺序访问，这样一层一层的进行，先访问的结点，其左右孩子也会先访问，符合队列的FIFO，故设置一个顺序队列记录已经访问了的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(BiTree *root){
    BiTree *bt = NULL , *Q[MAXN];
    int front = real = -1;
    if(root == NULL)
        return ;
    Q[++real] = root;
    while(front != real){
        bt = Q[++front];
        print(bt->data);
        if(bt->lchild != NULL)
            Q[++real] = bt->lchild;
        if(bt->rchild != NULL)
            Q[++real] = bt->rchild;
    }
}

参考资料：
《数据结构——从概念到C实现》
《数据结构——殷人昆》