本文主要是介绍二叉树(按层遍历——队列模拟),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
"队列.h"文件#include <stdio.h>
#include <stdlib.h>typedef struct biTree elemType ;struct node{elemType * elem;struct node * next;
};struct queue{struct node * front;struct node * rear;
};struct queue * initQueue();struct queue * enQueue(struct queue * q,elemType elem);struct queue * deQueue(struct queue * q);struct queue * initQueue(){struct queue * q;q=(struct queue *)malloc(sizeof(struct queue));q->front=(struct node *)malloc(sizeof(struct node));q->rear=q->front;q->front->next=NULL;return q;
}struct queue * enQueue(struct queue * q,elemType * elem){struct node * p;p=(struct node *)malloc(sizeof(struct node));p->elem=elem;p->next=NULL;q->rear->next=p;q->rear=p;return q;
}struct queue * deQueue(struct queue * q){struct node * p;if(q->front==q->rear){printf("队列为空!无法删除!\n");}else{p=q->front->next;q->front->next=p->next;if(q->rear==p){q->rear=q->front;}free(p);}return q;
}"二叉树.h"文件#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>struct biTree{char data;struct biTree * lchild, * rchild;
};struct biTree * initBiTree();struct biTree * createBiTree(struct biTree * bt);int preOrderTraverse(struct biTree * bt);int inOrderTraverse(struct biTree * bt);int postOrderTraverse(struct biTree * bt);int levelOrderTraverse(struct biTree * bt);int test();.c文件#include "二叉树.h"
#include "队列.h"#define MAX 100struct biTree * createBiTree(struct biTree * bt){int front,rear;char ch;struct biTree * p,* Queue[MAX];front=1,rear=0;printf("按层输入二叉树,虚结点输入'#'(结束符为'@'):\n");while((ch=getchar())!='@'){p=NULL;if(ch!='#'){p=(struct biTree *)malloc(sizeof(struct biTree));p->data=ch;p->lchild=p->rchild=NULL;}rear++;Queue[rear]=p;if(rear==1){bt=p;}else{if(p!=NULL&&Queue[front]!=NULL){if(rear%2==0){Queue[front]->lchild=p;}else{Queue[front]->rchild=p;}}if(rear%2==1){front++;}}}return bt;
}int preOrderTraverse(struct biTree * bt){if(bt!=NULL){printf("%c ",bt->data);preOrderTraverse(bt->lchild);preOrderTraverse(bt->rchild);}return 0;
}int inOrderTraverse(struct biTree * bt){if(bt!=NULL){inOrderTraverse(bt->lchild);printf("%c ",bt->data);inOrderTraverse(bt->rchild);}return 0;
}int postOrderTraverse(struct biTree * bt){if(bt!=NULL){postOrderTraverse(bt->lchild);postOrderTraverse(bt->rchild);printf("%c ",bt->data);}return 0;
}int levelOrderTraverse(struct biTree * bt){struct queue * queue;struct biTree * p;queue=initQueue();if(bt!=NULL){p=bt;enQueue(queue,p);printf("%c ",p->data);while(queue->front!=queue->rear){p=queue->front->next->elem;if(p->lchild!=NULL){enQueue(queue,p->lchild);printf("%c ",p->lchild->data);}if(p->rchild!=NULL){enQueue(queue,p->rchild);printf("%c ",p->rchild->data);}deQueue(queue);}}return 0;
}int test(){struct biTree * bt;bt=(struct biTree *)malloc(sizeof(struct biTree));bt=createBiTree(bt);preOrderTraverse(bt);printf("\n");inOrderTraverse(bt);printf("\n");postOrderTraverse(bt);printf("\n");levelOrderTraverse(bt);printf("\n");return 0;
}int main(){test();return 0;
}
这篇关于二叉树(按层遍历——队列模拟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!