实验四  树结构的应用
一、 实验目的
    掌握二叉树的创建、遍历的方法。
二、 实验内容
    利用二叉树的按层遍历序列创建二叉树，然后实现二叉树的前序、中序和后序遍历。
三、 实验内容准备
    在二叉树做任何运算之前，二叉树本身必须存在。因此，首先必须创建二叉树，实际上就是建立二叉树的存储结构。建立二叉树的存储结构就是建立二叉链表。下面介绍一种按完全二叉树的层次顺序，依次输入结点的信息建成立二叉链表的算法。该算法的基本思想是：首先对一般的二叉树添加若干个虚结点，使其成为完全二叉树，然后依次输入结点信息。若输入的结不是虚结点，则建立一个新结点；若是第一个令其为根结点；否则将新结点插入到双亲结点上。如此重复下去，直到输入信息“@”为止。
  为了使新结点能正确链接到其双亲结点上，可设置一个指针数组作为队列，保存已输入的结点的地址。因为按层自左至右输入结点的，所以首先输入结点的孩子先进队列，因此利用队列的队头指针front指向当前结点的双亲结点，利用队尾指针rear指向当前结点。若rear为偶数，则说明当前结点应作为左孩子链接到front所指向的结点上；否则，当前结点应作为右孩子链接到front所指向的结点上。若当前结点为虚结点则不需要链接。之后，使队头指针front指向下一个双亲结点。具体实现算法如下：
                        BinTree CreateBinTree(BinTree bt)
                        {//]是BinTNode类型的指针，front和rear是队头指针和队尾指针}
BinTNode *Q[num];
BinTNode *s;
Int front,rear;char ch;
Ch=getchar();bt=NULL;
front=1;rear=0;
while(ch!=’#’) {
s=NULL;
if (ch!=’@’) {
  s=(BinTNode *)malloc(sizeof(BinTNode));
  s->data=ch;s->leftchild=NULL;
  }
  rear++;
  Q[rear]=s;
  If (rear==1)  bt=s;
else
  { if (s!=NULL&&Q[front]!=NULL)
      if (rear%2==0)
        Q[front]->leftchild=s;
      else
        Q[front]->rightchild=s;
    If (rear%2!=0)
          front++;
    }
    ch=getchar()
完全二叉树算法
  }
  return bt;
}
四、 程序部分代码如下：
                          #include “stdio.h”
                          #include “stdlib.h”
                          #define num 100
                          typedef char datatype;
                          typedef struct node {
datatype data;
struct node leftchild,rightchild;
}BinTNode;
                          typedef BinTNode *BinTree;
                          BinTree CreateBinTree(BinTree bt)
                        {//]是BinTNode类型的指针，front和rear是队头指针和队尾指针}
BinTNode *Q[num];
BinTNode *s;
Int front,rear;char ch;
Ch=getchar();bt=NULL;
front=1;rear=0;
while(ch!=’#’) {
s=NULL;
if (ch!=’@’) {
  s=(BinTNode *)malloc(sizeof(BinTNode));
  s->data=ch;s->leftchild=NULL;
  }
  rear++;
  Q[rear]=s;
  If (rear==1)  bt=s;
else
  { if (s!=NULL&&Q[front]!=NULL)
      if (rear%2==0)
        Q[front]->leftchild=s;
      else
        Q[front]->rightchild=s;
    If (rear%2!=0)
          front++;
    }
    ch=getchar()
  }
  return bt;
}
preorder(BinTree bt)
{//前序遍历
if (bt!=NULL)
  { printf(“%c”,bt->data);
  preorder(btleftchild);
  preorder(bt->rightchild);
}
inorder(BinTree bt)
{//中序遍历
填完整
}
postorder(BinTree bt)
{//后序遍历
  填完整
}
void main()
{ BinTree bt;
int xz=1;
char ch1;
while(xz) {
printf(“          二叉树的遍历    \n”);
printf(“==========================\n”);
printf(“    1.建立二叉树的存储结构  \n”);
printf(“    2.求二叉树的前序遍历    \n”);
printf(“    3.求二叉树的中序遍历    \n”);
printf(“    4.求二叉树的后序遍历    \n”);
printf(“    0.退  出  系  统        \n”);
printf(“      请选择：0-4：          \n”);
scanf(“%d”,*xz);
switch(xz) {
case 1:
    printf(“输入二叉树的按层结点值（完全二叉树）:\n);
    bt=CreateBinTree(bt);
    printf(“二叉树的链式存储结构建成立完成!\n”);
    break;
case 2:
      printf(“该二叉树的前序遍历序列为：”);
      preorder(bt);
      printf(“\n”);
      break;
case 2:
      printf(“该二叉树的中序遍历序列为：”);
      preorder(bt);
      printf(“\n”);
      break;
  case 2:
      printf(“该二叉树的后序遍历序列为：”);
      preorder(bt);
      printf(“\n”);
      break;
    }
  }
}
五、 完成下列问题：
（1） 程序中所缺部分首先填成递归形式完成遍历并求出结果。
（2） 把遍历算法中其中一个写成非递归形式后重新调试。
（3） 写出实验报告。

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