层序遍历算法

A. 试完成二叉树按层次（同一层自左至右）遍历的算法。

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"

typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//层序遍历

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不为空，入队
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不为空，入队
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{

stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/

typedef struct
{
BiTree ptr;
int tag;
}stacknode;

void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top++;
p=p->lchild;
}

while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<<p->data; //tag为R，表示右子树访问完毕，故访问根结点
}

if (top>0)
{
s[top-1].tag =2; //遍历右子树
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec

int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

void main(){
BiTree T;
T=NULL;
int select;
//cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n请选择要执行的操作:\n";
cout<<"1.创建二叉树\n";
cout<<"2.二叉树的递归遍历算法（前、中、后）\n";
cout<<"3.二叉树的层次遍历算法\n";
cout<<"4.求二叉树的深度\n";
cout<<"5.求二叉树的叶子结点\n";
cout<<"6.求二叉树的结点总数\n";
cout<<"7.二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout<<"0.退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
PreOrderTraverse(T);
cout<<"\n中序遍历:\n";
InOrderTraverse(T);
cout<<"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉树的深度为:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n叶子节点数:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"总节点数:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立树，请先建树！";
else{
cout<<"\n先序遍历:\n";
NRPreOrder(T);
cout<<"\n中序遍历:\n";
NRInOrder(T);
cout<<"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout<<"请确认选择项:\n";
}//end switch
}//end while

}
参考资料：找来的，你看看吧！

B. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是

辅助的就是队列了，如果是堆栈就成了深度优先算法了；其实这里辅助结构决定了算法的性质，你可以换成最大堆，最小堆等，就可以达到很多不同的效果

C. 这个层序遍历的算法错在哪里了想不明白

你没有更新指针 p 的值，它一直指向树根

D. 试写一个建立二叉树在内存的双链表示算法，并实现先根、中根、后根以及层序遍历算法。

你先把三元组化为链表，然后按下述算法：
/*二叉树的建立、递归遍历sy6_1.c*/
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#define MAXSIZE 30
typedef struct btnode
{
char c;
struct btnode *l,*r;
}BTNode;
BTNode *Create_BiTree()/*二叉树的建立*/
{/*用辅助数组建立二叉树*/
int i,j;
char ch;
BTNode *s,*t,*p[MAXSIZE];
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
while(i!=0 &&ch!='#')/*建立二叉树的存储结构*/
{s=(BTNode*)malloc(sizeof(BTNode));
s->c=ch;
s->l=s->r=NULL;
p[i]=s;
if(i==1) t=s;/*判断输入结点是根结点、左孩子还是右孩子*/
else
{j=i/2;
if(i%2==0) p[j]->l=s;
else p[j]->r=s;
}
printf("输入顶点编号及信息，输入0和#结束:i,ch");
scanf("%d,%c",&i,&ch);
}
return t;
}/* Create_BiTree1*/
void DLR(BTNode *bt)
{/*前序递归遍历*/
if(bt)
{
printf("%c",bt->c);
DLR(bt->l);
DLR(bt->r);
}
}/* DLR*/
void LDR(BTNode *bt)
{/*中序递归遍历*/
if(bt)
{
LDR(bt->l);
printf("%c",bt->c);
LDR(bt->r);
}
}/* LDR*/
void LRD(BTNode *bt)
{/*后序递归遍历*/
if(bt)
{
LRD(bt->l);
LRD(bt->r);
printf("%c",bt->c);
}
}/* LRD*/
void LevelOrder(BTNode *bt) /*层次遍历二叉树bt*/
{ BTNode* queue[MAXSIZE];
int front,rear;
if (bt==NULL) return;
front=0; /*非循环队列*/
rear=0;
queue[rear++]=bt;
while(front!=rear)
{printf("%c",queue[front]->c); /*访问队首结点的数据域*/
if (queue[front]->l!=NULL) /*队首结点左孩子指针入队*/
{ queue[rear]=queue[front]->l;rear++;}
if (queue[front]->r!=NULL) /*队首结点右孩子指针入队*/
{ queue[rear]=queue[front]->r; rear++; }
front++;
}
}
void main()
{
int i,j=1;
BTNode *t;
t=Create_BiTree();
while(j)
{
printf("\n"); /*功能菜单*/
printf("请选择操作:\n");
printf("1: 二叉树的前序遍历\n");
printf("2: 二叉树的中序遍历\n");
printf("3: 二叉树的后序遍历\n");
printf("4: 二叉树的层次遍历\n");
printf("0: 退出程序\n");
scanf("%d",&j);
switch(j)
{
case 0: printf(" 程序退出!\n ");exit(0);
case 1: printf("前序遍历结果:\n"); DLR(t); break;
case 2: printf("中序遍历结果:\n"); LDR(t);break;
case 3: printf("后序遍历结果:\n"); LRD(t);break;
case 4: printf("按层遍历结果:\n");LevelOrder(t);break;
default : printf("\n输入无效，请重新选择操作!\n" );break;
}
}
}

E. 二叉树层次遍历怎么进行

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}

DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！

F. 问一个层序遍历的问题

typedef struct node
{
int *date;
struct node *nxet;
}node;

typedef struct queue
{
node *front;
node *rear;
}queue;

void empty(queue *equeue)
{
equeue->front=equeue->rear=NULL;
}

void push(queue *equeue,int *date)
{
node *t;
t=new node;
t->date=date;
t->nxet=NULL;
if(equeue->front==NULL)
{
equeue->front=t;
equeue->rear=t;
}
else
{
equeue->rear->nxet=t;
equeue->rear=t;
}
}

int pop(queue *equeue)
{
int *s;
node *t;
t=new node;
s=new int;
t=equeue->front;
equeue->front=equeue->front->nxet;
s=t->date;
delete t;
return s;
}
//以上是一个队，用来存放树的结点变量的地址；
//下面是树的层序遍历函数；
void fun(struct TreeNode *p)
{
queue *q;
q=new queue;
empty(q);
cout<<p->key;
while(p!=NULL)
{
if(p=->LeftChild!=NULL){
cout<<p->LeftChild->key;
push(q,p->LeftChild);
}
if(p=->RightChild!=NULL){
cout<<p->RightChild->key;
push(q,p->RightChild);
}
if(equeue->front!=NULL)
p=pop(q);
else
p=NULL;
}
}

G. 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法

//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;

void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}

}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;

createBTree(&(*tree)->left);

createBTree(&(*tree)->right);

}
}

void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}

void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}

visitBTree(q);
}
}

H. 设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。

按层次遍历算法如下：
#include <iostream>
using namespace std;

typedef struct treenode { //树结点结构
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;

typedef struct stack{ //栈结点结构
TreeNode *node;
struct stack *next;
}STACK;

void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根结点入栈
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //栈顶结点的左结点入栈
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}

if (head->node->right != NULL) //栈顶结点的右结点入栈
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //结点出栈
temp = head;
head = head->next;
delete(head);
}
}