本例是采用一般的队列来存储和访问二叉树
访问过程描述如下：
访问根结点，并将该结点记录下来；
若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。
取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；
若它有右孩子，则访问右孩子，并记录下来。
     在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；
     而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：
（1）访问根结点，并将根结点入队；
（2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
其基本算法为:
//按层次遍历树中结点
void traverse(bitree bt)
{
 linkqueue q;
 bitree p;
 initqueue(q);      //初始化一个空的队列
 p=bt;
 enqueue(q,p);      //入队
 while(queueempty(q)!=1)
 {
  dequeue(q,p);      //出队
   if(p->lchild!=NULL)
   enqueue(q,p->lchild);             //访问左子树
  if(p->rchild!=NULL)
   enqueue(q,p->rchild);             //访问右子树
 }
 printf("\n");
}
     为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉
    树的位置上填补一个特殊的字符，比如，' '。在算法中，需要对每个输入的字符进行判
    断，如果对应的字符是' '，则在相应的位置上构造一棵空二叉树；否则，创建一个新结
    点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针
    参数在递归调用返回时完成。
int createbitree(bitree &T,int &sum)
{
 char ch;
 scanf("%c",&ch);
 if(ch==' ')
  T=NULL;
 else
 {
  if(!(T=(bitree)malloc(sizeof(binode))))
   return 0;
  T->data=ch;
  sum++;
  createbitree(T->lchild,sum);
  createbitree(T->rchild,sum);
 }
 return 1;
}
具体实现过程为:
#include<stdio.h>
#include<malloc.h>
typedef struct binode
{
 char data;
 struct binode *lchild,*rchild;
}binode,*bitree;                        //定义树结点结构
typedef struct queuenode
{
 bitree ch;
 struct queuenode *next;
}queuenode,*queueptr;                   //定义队列结点结构
typedef struct
{
 queueptr front;
 queueptr rear;
}linkqueue;                  //定义队列指针
//建树
int createbitree(bitree &T,int &sum)
{
 char ch;
 scanf("%c",&ch);
 if(ch==' ')
  T=NULL;
 else
 {
  if(!(T=(bitree)malloc(sizeof(binode))))
   return 0;
  T->data=ch;
  sum++;
  createbitree(T->lchild,sum);
  createbitree(T->rchild,sum);
 }
 return 1;
}//初始化一个带头结点的队列
void initqueue(linkqueue &q)
{
 q.ar=(queueptr)malloc(sizeof(queuenode));
 q.front->next=NULL;
}
//入队列
void enqueue(linkqueue &q,bitree p)
{
 queueptr s;
 int first=1;
 s=(queueptr)malloc(sizeof(queuenode));
 s->ch=p;
 s->next=NULL;二叉树中序遍历非递归算法
&ar->next=s;
&ar=s;
}
//出队列
void dequeue(linkqueue &q,bitree &p)
{
 char data;
 queueptr s;
 s=q.front->next;
 p=s->ch;
    data=p->data;
 q.front->next=s->next;
 ar==s)
  q.rear=q.front;
 free(s);
 printf("%c ",data);
}//判断队列是否为空
int queueempty(linkqueue q)
{
 if(q.front->next==NULL)
  return 1;
 return 0;
}//按层次遍历树中结点
void traverse(bitree bt)
{
 linkqueue q;
 bitree p;
 initqueue(q);
 p=bt;
 enqueue(q,p);
 while(queueempty(q)!=1)
 {
  dequeue(q,p);
   if(p->lchild!=NULL)
   enqueue(q,p->lchild);
  if(p->rchild!=NULL)
   enqueue(q,p->rchild);
 }
 printf("\n");
}
//主函数
void main()
{
 int n=0;
 bitree bt;
 createbitree(bt,n);
 printf("该二叉树共有%d个结点.\n",n);
 printf("按层次遍历树中结点其输出顺序为: \n");
 traverse(bt);
}
通过上机实践，帮助学生进一步掌握指针变量和动态变量的含义，掌握二叉树的结构特性，以及各种存储结构的特点及适用范围，掌握用指针类型描述、访问和处理二叉树的运算。【实验内容】
实验题目一：层序遍历二叉树
【实验步骤】
1 已知二叉树以二叉链表作为存储结构，写一个算法按层序遍历它，通过程序在终端屏幕上打印出它的层序序列。
2 先建立二叉树的二叉链表存储结构，再遍历它。
3 利用队列完成算法。
编程实现以二叉链表存储的二叉树的中序遍历的非递归算法。
编程实现二叉树的中序线索链表的生成（线索化）及其遍历的算法。
实验题目二：交换二叉树的所有结点的左右子树
【实验步骤】
1 已知二叉树以二叉链表作为存储结构，写一个算法交换该二叉树的所有结点的左右子树。
2 先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式!
3 利用栈。可设二叉树的根指针为t，且以二叉链表表示，可利用一个指针栈来实现，且设栈
单元包括数据域和指针域，当树非空时，将当前的树根结点进栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左右指针交换；再将交换后的左指针或右指针入栈，如此反复，直到栈空。
【程序说明】
该程序集成了如下功能：
（1）    二叉树的建立
（2）    递归和非递归先序，中序和后序遍历二叉树
（3）    按层次遍历二叉树
（4）    交换二叉树的左右子树
（5）    输出叶子结点
（6） 递归和非递归计算叶子结点的数目
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
typedef struct Binnode{
    char data;
    struct Binnode *lchild;
    struct Binnode *rchild;
  }Binnode;
  /*按照前序遍历建立二叉树*/
void Creat_Bintree(Binnode **t)
{
  char ch;
  scanf("\n%c",&ch);
  if(ch=='0') *t=NULL;
  else
    {
      *t=(Binnode*)malloc(sizeof(Binnode));
      if(!*t)exit(OVERFLOW);
      (*t)->data=ch;
      printf("%c: left",ch); Creat_Bintree(&(*t)->lchild);
      printf("%c: right",ch);Creat_Bintree(&(*t)->rchild);
    }
}
/*按照前序递归遍历二叉树*/
void Preorder1(Binnode *t)
{
    if(t!=NULL)
    {
        printf("%c",t->data);
        Preorder1(t->lchild);
        Preorder1(t->rchild);
    }
}
/*按照中序递归遍历二叉树*/
void Inorder1(Binnode *t)
{ /* printf("\n输出中序递归遍历序列:");*/
    if(t!=NULL)
    {
        Inorder1(t->lchild);
        printf("%c",t->data);
        Inorder1(t->rchild);
    }
 
}
/* 按照后序递归遍历二叉树*/
void Posorder1(Binnode *t)
{  /* printf("\n输出后序递归遍历序列:");*/
    if(t!=NULL)
    {
        Posorder1(t->lchild);
        Posorder1(t->rchild);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。