实验4 二叉树操作

实验4 二叉树操作

 

一、实验目的

1．熟悉树的存储结构；

2．熟悉二叉链表的创建；

3．熟悉二叉树的遍历操作和其他操作。

二、实验内容

1、针对如图所示的二叉树，用先序遍历方法创建该二叉树的二叉链表存储；

2、 在第1步基础上，用非递归中序遍历方法和后序递归遍历方法，分别输出遍历结果；

3、用非递归方法找出该二叉树的所有叶子结点并输出。

 

 

 

三、实验要求

1．每个同学必须独立完成；

2．程序中的开头部分必须对本程序的总体功能进行注释；程序中每个函数段必须要有注释说明该函数的功能或作用；

3．上机进行调试和修改并填写实验报告；

4．实验报告中的源程序必须调试通过。

5．在体会中描述如下内容：

（1）对算法与程序的区别上的体会。

（2）本次实验过程的体会，是否自己独立完成？最大的困难是什么？自己准备如何解决这个困难？

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 Posorder1(Binnode *t)
{  /* printf("\n输出后序递归遍历序列:");*/
    if(t!=NULL)
    {
        Posorder1(t->lchild);
        Posorder1(t->rchild);
        printf("%c",t->data);
    }
}

/*按照中序非递归遍历二叉树*/
void Inorder2(Binnode *root)/*中序非递归遍历二叉树*/
{   Binnode  *p,*stack[100];
     int top=0;
      p=root;
do{
    while(p!=NULL)
    {
      top++;
      stack[top]=p;
      p=p->lchild;
    }
    if(top>0)
   {
     p=stack[top];/*p所指的节点为无左子树或其左子树已经遍历过*/
      top--;
     printf("%c",p->data);
     p=p->rchild;
   }
}while(p!=NULL||top!=0);
}

/*非递归法求叶子结点个数*/
int Leaves_Num2(Binnode *t)
{
    Binnode *s[100];
    int count=0,top=0;
    while(t||top>0)
    {
        if(t)
        {
             s[top++]=t;
             if(t->lchild==NULL&&t->rchild==NULL)
             {
                count++;
              printf("%c",t->data);/*输出叶子结点*/
             }
             t=t->lchild;
         }
        else
         {
            t=s[--top]->rchild;
         }
    }
    return count;
}
 
int main()
{
    Binnode *proot=NULL;
    int p,q;
    printf("1.CreateBitree:\n");
    Creat_Bintree(&proot); /*建立二叉树时，无左右孩子的结点输入’0’值*/
    printf("\n5.Output Not Digui InOrder:\n");
    Inorder2(proot);
    printf("\n6.Output Digui PostOrder:\n");
    Posorder1(proot);
    printf("\n11.Leaves_Node:\n");
    q=Leaves_Num2(proot);
    printf("\n12.Output Not Digui Leaves_Num:%d\n",q);
 
    return 0;
}