【数据结构 二叉树 递归与非递归遍历】

0二叉树结构体定义

typedef struct BTNode{
   int data;
   struct BTNode * lchild;
   struct BTNode * rchild;
}BTNode;
1
2
3
4
5

1.递归遍历

先序(访问根结点，先序遍历左子树，先序遍历右子树)

void PreOrder(BTNodey T){
   if(T!=NULL){
       visit(T);
       preOrder(T->lchild);
       preOrder(T->rchild);
   }
}
1
2
3
4
5
6
7

中序(中序遍历左子树，访问根结点，中序遍历右子树)

void InOrder(BTNode T){
   if(T!=NULL){
       InOrder(T->lchild);
       visit(T);
       InOrder(T->rchild);
   }
}
1
2
3
4
5
6
7

后序(后序遍历左子树，后序遍历右子树，访问根结点)

void PostOrder(BTNode T){
   if(T!=NULL){
       PostOrder(T->lchild);
       PostOrder(T->rchild);
       visit(T);
   }
}
1
2
3
4
5
6
7

2.非递归遍历

先序遍历

1. 沿着根的左孩子，先访问并依次入栈，直到左孩子为空(一直到最下层的左孩子停止)；
   2.(判断:没有右子树了) 栈顶元素出栈，接着若右孩子为空，继续执行2；若不为空，将右子树的操作转为1；

// 先序遍历（非递归）
void PreOrder(BTNode T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BTNode p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {
   
        if(p) {
            visit(p);
            Push(S, 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

中序遍历

1. 沿着根的左孩子，依次入栈，直到左孩子为空(一直到最下层的左孩子停止)；
   2.(判断:没有左子树了) 栈顶元素出栈并访问，接着若右孩子为空，继续执行2；若不为空，将右子树的操作转为1；

// 中序遍历（非递归）
void InOrder(BTNode T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BTNode p = T;
    // 树和链表有一者不为空则循环继续进行
    while(p || !IsEmpty(S)) {

        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
20
21

后序遍历

1. 沿着根的左孩子，依次入栈，直到左孩子为空(一直到最下层的左孩子停止)；
   2.读取栈顶元素：若其右孩子不空且未被访问过，将右子树转执行1；否则，栈顶元素出栈并访问。 ；

// 后序遍历（非递归）
void PostOrder(BTNode T) {
    LinkStack S;
    // 初始化栈
    InitStack(S);
    // 遍历指针
    BTNode p = T;
    // 辅助指针，用于记录最近访问过的结点
    BTNode 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指针
                // 由于每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，所以需要将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
30
31
32
33
34
35
36