树：二叉树的层序遍历算法（超简洁实现及详细分析） |
您所在的位置：网站首页 › 按层次遍历二叉树 › 树：二叉树的层序遍历算法（超简洁实现及详细分析） |
树：二叉树的层序遍历算法（超简洁实现及详细分析）
|
实现思路
我们来看看下图的二叉链表 如何实现层序遍历。 层序遍历顺序：ABECDG A为B、E的双亲结点，遍历顺序是 根->左->右 是不是。 而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队，出队时将其左右孩子入队，循环队列进行出队，每次出队将其左右孩子入队。当队列为空时，整棵树层序遍历完毕。还没明白请看下面过程。A->出队 队列：E、B B->出队 队列：D、C、E E->出队 队列：G、D、C C->出队 队列：G、D D->出队 队列：G G->出队 队列为空，层序遍历完毕。 二叉树层序遍历算法代码 层序遍历函数层序遍历核心代码，利用了一个自己底层封装的顺序队列。如果想知道怎么实现的呢，请看线性表：顺序队列算法实现。 //一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列 //直到队列为空 void SeqTraverse(BiTree tree) { SeqQueue queue = Init_SeqQueue(); Push_SeqQueue(queue, tree); while (!IsEmpty_SeqQueue(queue)) { BiTree root = Pop_SeqQueue(queue); printf("%c ", root->data); if (root->lchild) Push_SeqQueue(queue, root->lchild); if(root->rchild) Push_SeqQueue(queue, root->rchild); } printf("\n"); } 完整代码 #define _CRT_SECURE_NO_WARNINGS #include #include #include "SeqQueue.h" typedef char ElemType; typedef struct BiNode { ElemType data; struct BiNode* lchild; struct BiNode* rchild; }BiNode, *BiTree; //创建二叉链表 void CreateBiTree(BiTree* tree) { char c; scanf("%c", &c); if (c == ' ') { *tree = NULL; return; } *tree = malloc(sizeof(BiNode)); (*tree)->data = c; CreateBiTree(&(*tree)->lchild); CreateBiTree(&(*tree)->rchild); return; } //二叉链表 递归前序遍历 void PreTraverse(BiTree tree) { if (tree == NULL) { return; } printf("%c ", tree->data); PreTraverse(tree->lchild); PreTraverse(tree->rchild); } //一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列 //直到队列为空 void SeqTraverse(BiTree tree) { SeqQueue queue = Init_SeqQueue(); Push_SeqQueue(queue, tree); while (!IsEmpty_SeqQueue(queue)) { BiTree root = Pop_SeqQueue(queue); printf("%c ", root->data); if (root->lchild) Push_SeqQueue(queue, root->lchild); if(root->rchild) Push_SeqQueue(queue, root->rchild); } printf("\n"); } int main(int argc, char *argv[]) { BiTree tree = NULL; printf("请前序遍历输入结点："); CreateBiTree(&tree); printf("前序遍历："); PreTraverse(tree); printf("\n层序遍历："); SeqTraverse(tree); return 0; } 代码运行检测我们构建如下图的二叉树，注意创建二叉树输入序列为：ABC__D__E_G__，_代表一个空格哟。
|
【本文地址】
今日新闻 |
推荐新闻 |