二叉树的层次遍历c++_层序遍历c++简单二叉树

树的层次遍历，又称为树的广度遍历

算法

大致思路：

1. 借助一个队列，先将二叉树根节点入队列，然后出队列，访问出队结点。
2. 若出队结点有左子树，则将左子树根结点入队；
   若出队结点有右子树，则将右子树根节点入队。
3. 然后出队，访问出队结点，重复 2，直至队列为空

具体算法步骤：
① 若树非空，则根节点入队
② 若队列非空，队头元素出队并访问，同时将该元素的左右孩子依次入队
③ 重复②直到队列为空

层次遍历代码

void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p=T;
    EnQueue(Q,p);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild){
            EnQueue(Q,p->lchild);//左子树不空，则左子树根节点入队列
        }
        if(p->rchild){
            EnQueue(Q,p->rchild);//右子树不空，则右子树根节点入队列
        }
    }
    /*因为在DeQueue时会执行free操作，所以这里不用再销毁队列
    if(IsEmpty(Q)){
        printf("\nQueue Empty\n");
    }*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

完整测试代码

//队列的链式存储，链队列   不带头结点
//实际上是一个同时带有队头指针和队尾指针的单链表
//头指针指向头结点，尾指针指向尾结点
#include<stdlib.h>
#include<stdio.h>
#define Elemtype BiTree
#define ElemType char
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


typedef struct LinkNode{//链式队列结点
    Elemtype data;
    struct LinkNode *next;
}LinkNode;
typedef struct{//链式队列
    LinkNode *front,*rear;//队列的队头和队尾指针
}LinkQueue;




void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=NULL;
}

bool IsEmpty(LinkQueue Q){
    return (Q.front==NULL);
    //或者return (Q.rear==NULL);
}

bool EnQueue(LinkQueue &Q, Elemtype x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){//原来为空队列

        Q.front = s;
        Q.rear=s;
    }
    else{
        Q.rear->next = s;//新结点插到尾部
        Q.rear=s;//@@@修改尾指针！！！
        //printf("？？？%d \n",Q.rear->data);
    }
    return true;
}

bool DeQueue(LinkQueue &Q, Elemtype &x){
    if(Q.front == NULL){//@@@
        printf("空队列\n");
        return false;
    }
    LinkNode *p=Q.front;//p指向此次出队的结点
    x=Q.front->data;
    Q.front=p->next;
    if(Q.rear==p){//此次出队的是最后一个结点
        Q.front=Q.rear=NULL;
    }
    free(p);//@@@
    p=NULL;
    return true;
}

bool PrintQueue(LinkQueue Q){
    if(!Q.front){
        printf("空队列无法打印\n");
        return false;
    }
    LinkNode *p=Q.front;
    printf("Queue is:");
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return true;
}

void visit(BiTree T){
    printf("%c ",T->data);
}

void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p=T;
    EnQueue(Q,p);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild){
            EnQueue(Q,p->lchild);//左子树不空，则左子树根节点入队列
        }
        if(p->rchild){
            EnQueue(Q,p->rchild);//右子树不空，则右子树根节点入队列
        }
    }
    /*因为在DeQueue时会执行free操作，所以这里不用再销毁队列
    if(IsEmpty(Q)){
        printf("\nQueue Empty\n");
    }*/
}

//按前序输入二叉树中节点的值(一个字符)
// ' '表示空树， 构造二叉链表表示二叉树T
bool CreateBiTree(BiTree &T){
    ElemType ch;

    scanf("%c",&ch);//@@@
    if(ch == '#'){
        //printf("您要创建一棵空树吗？\n");
        T=NULL;//
        return false;
    }
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T){
            printf("malloc failure\n");
            return false;
        }
        T->data=ch;//生成根节点
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树
        return true;
    }
}


bool DestroyBiTree(BiTree T){//@@@
    if(T == NULL){
        //printf("空结点#\n");
        return false;
    }
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    printf("销毁%c\n",T->data);
    free(T);//@@@
    T=NULL;//防止产生野指针
    return true;
}

int main(){
    BiTree T=NULL;//@@@
    printf("按前序输入二叉树中节点的值(输入#表示空节点)\n");
    CreateBiTree(T);

    printf("层次遍历结果为：\n");
    LevelOrder(T);

    printf("\n\n开始destroy二叉树(按后序遍历来销毁):\n\n");
    DestroyBiTree(T);

    return 0;

}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

按前序遍历的结果输入二叉树的结点(#表示空节点)
ABD##E##CFH##I##G##