二叉树的层次遍历
二叉树的层次遍历。#include<stdio.h>#include<stdlib.h>typedef char DataType;//树结点的数据类型定义typedef struct BTnode{DataType data;struct BTnode* lchild,*rchild;}BTree;//队列的结点数据类型定义typedef struct node{BTree * tdata; //存放树结点类型的指针struct node *next;}qnode;//队头指针 和 队尾指针typedef struct {qnode *front,*rear;}linkQueue;//初始化队列void Init(linkQueue *q){q->front=q->rear=NULL;}//元素入队void InsertQueue(linkQueue * &q,BTree * e){qnode * node;node=(qnode*)malloc(sizeof(qnode));node->tdata=e;node->next=NULL;if(NULL==q->front){q->front=q->rear=node;}else{q->rear->next=node;q->rear=node;}}//元素出队BTree * outQueue(linkQueue * &q){BTree * e;qnode *temp;if(NULL==q->front)e=NULL;else{temp=q->front;e=temp->tdata;q->front=temp->next;free(temp);}return e;}//创建二叉树,以先序的方式输入，如果左孩子或右孩子为空，则输入#/* 例子A 输入为:ABD##E##CF### /\ B C / \ / D EF */ void createBTree(BTree * &t){char c; c=getchar();if(c=='#')t=NULL;else{t=(BTree*)malloc(sizeof(BTree));t->data=c;createBTree(t->lchild);//创建左子树createBTree(t->rchild);//创建右子树}}/*二叉树的层次遍历算法: 1.队列queue初始化；2. 将根指针入队；3. 循环直到队列queue为空 3.1 q=队列queue出队的元素; 3.2 访问结点q的数据域; 3.3 若结点q存在左孩子，则将左孩子入队; 3.4 若结点q存在右孩子，则将右孩子入队;*///二叉树的层次遍历void hierarchyTtraversal(linkQueue *queue,BTree * root){BTree *q;InsertQueue(queue,root);while(NULL!=queue->front){q=outQueue(queue);printf("%c",q->data);if(q->lchild)InsertQueue(queue,q->lchild);if(q->rchild)InsertQueue(queue,q->rchild);}}int main(){BTree *root;linkQueue queue;Init(&queue);createBTree(root);hierarchyTtraversal(&queue,root);printf("\n");return 0;}
页:
[1]