二叉树遍历问题

二叉树的层序遍历是按二叉树的层次顺序（即从根结点层至叶结点层），同一层按先左子树再右子树的次序遍历。给定如下图所示的二叉树，请输出对应的层序遍历的序列

设计参考：可以采用队列结构来实现（具体参见教材P170）。

A

B F

C E G

D

A B F C E G D

程序VS2003成功编译运行

#include "stdafx.h"

#include<iostream> using namespace std; typedef struct tree { char data; //数据域 struct tree *lchild; //左孩子 struct tree *rchild; //右孩子 struct tree *next; //用于构造队列 }bintree; //二叉树的建立 bintree *create(char* str, int pose, int size) { char ch; bintree * t; char* p=str; ch = p[pose];

if(ch==' '|| ch=='\n'|| pose>=size) return NULL; // 表示空结点 else { t=(bintree *)malloc(sizeof(bintree)); //非空则构造新结点 t->data=ch; //新结点数据域即为读入字符 t->next=NULL; //新结点next域暂时不用，赋空 t->lchild=create(p, 2*pose+1,size); //建立左子树 t->rchild=create(p, 2*pose+2,size); //建立右子树 } return(t);

}

void PrintTree(bintree *T,int Layer) {// 按竖向树状打印的二叉树// int i; if(T==NULL) return; PrintTree(T->rchild,Layer+1); for(i=0;i<Layer;i++) printf(" "); printf("%c \n",T->data); //按逆中序输出结点，用层深决定结点的左右位置 PrintTree(T->lchild,Layer+1); }

void visitT(char e) { printf("%c ",e); }

//先序遍历 void preorder(bintree *root, void(*vi)(char)) { bintree *t=root; if(NULL!=t) { vi(t->data); //访问根结点 preorder(t->lchild, vi); //先序遍历左子树 preorder(t->rchild, vi); //先序遍历右子树 } } //层次遍历 void levelorder(bintree *root, void(*vi)(char)) { bintree *t=root; struct tree *head=t,*tail=t; //head指向源结点，称头指针；tail指向末结点，称尾指针// while(NULL!=head) //若源结点非空，且有左或右孩子，则将其孩子依次入队；若源结点为空，则跳出循环// { if(NULL!=head->lchild) { tail->next=head->lchild; tail=tail->next; } //若源结点有左孩子，则该左孩子入队，尾指针后移一位// if(NULL!=head->rchild) { tail->next=head->rchild; tail=tail->next; } //若源结点有右孩子，则该右孩子入队，尾指针后移一位// head=head->next; //依次访问完源结点的左右孩子后，头指针后移一个，进入下次循环// } while(t!=NULL) { vi(t->data); //访问根结点 t=t->next; } }

//主函数 void main() { bintree *root; char a[20]; printf("给出建立二叉树的字符串:"); cout <<"输入CH" <<endl; cin >> a; root=create(a, 0,strlen(a));

printf("\n二叉树的凹入表示:\n"); PrintTree(root,0); printf("\n先序遍历序列: "); preorder(root,visitT);

printf("\n层次遍历序列: "); levelorder(root,visitT);

printf("\n"); system("pause"); }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息