汉扬编程 编程大纲 学过二叉树的遍历吗?非递归算法之二叉树层次遍历

学过二叉树的遍历吗?非递归算法之二叉树层次遍历

二叉树层次遍历

学过二叉树的遍历吗?非递归算法之二叉树层次遍历

按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是:通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后顺序就是层次遍历的最终结果。

学过二叉树的遍历吗?非递归算法之二叉树层次遍历

图1 二叉树

层次遍历的实现过程例如,层次遍历图 1 中的二叉树:

首先,根结点 1 入队;根结点 1 出队,出队的同时,将左孩子 2 和右孩子 3 分别入队;队头结点 2 出队,出队的同时,将结点 2 的左孩子 4 和右孩子 5 依次入队;队头结点 3 出队,出队的同时,将结点 3 的左孩子 6 和右孩子 7 依次入队;不断地循环,直至队列内为空。实现代码#include <stdio.h>#define TElemType int//初始化队头和队尾指针开始时都为0int front=0,rear=0;typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}//入队函数void EnQueue(BiTree *a,BiTree node){ a[rear++]=node;}//出队函数BiTNode* DeQueue(BiTNode** a){ return a[front++];}//输出函数void displayNode(BiTree node){ printf(\”%d \”,node->data);}int main() { BiTree tree; //初始化二叉树 CreateBiTree(&tree); BiTNode * p; //采用顺序队列,初始化创建队列数组 BiTree a[20]; //根结点入队 EnQueue(a, tree); //当队头和队尾相等时,表示队列为空 while(front<rear) { //队头结点出队 p=DeQueue(a); displayNode(p); //将队头结点的左右孩子依次入队 if (p->lchild!=NULL) { EnQueue(a, p->lchild); } if (p->rchild!=NULL) { EnQueue(a, p->rchild); } } return 0;}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/5863.html

大学学了一学期的C语言,继续深入的话应该学什么?为你答疑解惑

1编码完成二叉树的相关操作

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部