C++用队列遍历二叉树(非递归).docx

#includeiostreamusing namespace std;struct Tree //创建树的结构体{char element;Tree *lchilden;Tree *rchilden;};Tree *Create()//创建一颗树{char ch;cin ch;if (ch == #){return NULL;}else{Tree *root = (Tree*)malloc(sizeof(Tree));root-element = ch;root-lchilden = Create();root-rchilden = Create();return root;}}void visit(Tree*t)//访问树的方法{cout t-element;}void preOrder(Tree *t)//用递归的方法先序的访问数{if (t != NULL) {visit(t);preOrder(t-lchilden);preOrder(t-rchilden);}}struct Qnode{//创建链表队列的节点char data;Qnode *next;Tree* tree;//用来标志在树中的位置（沟通的树和下面创建的链表队列）};struct LinkQueue{//创建队列Qnode* front;Qnode* rear;};LinkQueue* InitQueue(LinkQueue *q){//构造一个空队列//q = (LinkQueue*)malloc(sizeof(LinkQueue));q-front = q-rear = (Qnode*)malloc(sizeof(Qnode));if (!q-front) exit(OVERFLOW);q-front-next = NULL;return q;}LinkQueue* DestroyQueue(LinkQueue *q){//销毁队列while (q-front){q-rear = q-front-next;free(q-front);q-front = q-rear;}return q;}LinkQueue* EnQueue(LinkQueue *q, Tree *m){Qnode *p = (Qnode*)malloc(sizeof(Qnode));//插入元素e为Q的新的队尾元素p-data = m-element;p-next = NULL;q-rear-next = p;q-rear = p;q-rear-tree = m;//保存下现在节点在树中的位置；return q;}char DeQueue(LinkQueue *q, Tree *m){//若队列不为空，则删除Q的对头元素，用e返回其值Qnode *p = q-front-next;char e = p-data;m = p-tree;//把要销毁的队列的节点在树中的位置用m指针引用q-front-next = p-next;if (q-rear == p) q-rear = q-front;free(p);if (m-lchilden != NULL){//判断销毁后的节点的左孩子还有吗；EnQueue(q, m-lchilden);}if (m-rchilden != NULL){//判断销毁后的节点的右孩子还在吗；EnQueue(q, m-rchilden);}return e;}int queueempty(LinkQueue *q)//判断队列是否为空{if (q-front-next == NULL)return 1;return 0;}int main(){Tree *q;q = Create();LinkQueue *p = new LinkQueue;InitQueue(p);EnQueue(p, q); Tree *t=q; Tree *k=q; bool step = 0;while (queueempty(p) != 1){coutDeQueue(p, q);}system(pause);return 0;}运行结果如下?说明：在创建链表节点时一定要多一个树的指针；用来标志位置如下图