層序遍歷演算法

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);
}
}