数据结构：实验三二叉树操作实现

骑猪看日落 2023-07-11 12:36 48阅读 0赞

# 实验三 二叉树操作实现 #

## 一、实验目的 ##

1.进一步掌握指针变量、动态变量的含义；  
2.掌握二叉树的概念和结构特征，以及各种存储结构的特点及适用范围；  
3.掌握用指针类型描述、访问和处理二叉树的运算。掌握二叉链表的建立、递归和非递归时二叉树的遍历方法

## 二、实验环境 ##

1、PC微机；  
2、Windows 操作系统；  
3、VC6.0或以上

## 三、实验内容 ##

已知以二叉链表作存储结构，编写二叉链表的建立、递归和非递归时二叉树的先序遍历、中序遍历、后序遍历。并编写按层次顺序遍历二叉树的算法。  
测试数据： 输入先序遍历序列：ABC\#\#D\#E\#\#FG\#I\#\#\#\#

## 四、实验步骤、测试及结果 ##

1.运行代码

#include<stdlib.h>
    #include<stdio.h>
    #define TRUE   1
    #define FALSE  0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    typedef  int Status;
    typedef  char ElemType;
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    /*①二叉树的二叉链表存储结构定义*/
    typedef struct BiTNode
    {
        
    	ElemType data;
    	struct BiTNode *lchild,*rchild;      //左右孩子指针
    }BiTNode,*BiTree;
     
    /*栈的顺序存储结构定义*/
    typedef BiTree SElemType;
    typedef struct 
    {
        
    	SElemType  *base ;
    	SElemType  *top ; 
    	int  stacksize ;    
    }SqStack; 
    
    //判断栈是否为空
    Status StackEmpty(SqStack S);
     
    // 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
      // 构造二叉链表表示的二叉树T。
    Status CreateBiTree(BiTree &T)
    {
          
      ElemType ch;
      ch=getchar();
      if (ch=='#') T = NULL;
      else 
      {
        
    	  
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))  exit(OVERFLOW);
        T->data = ch;              // 生成根结点
        CreateBiTree(T->lchild);      // 构造左子树
        CreateBiTree(T->rchild);      // 构造右子树
      }
      return OK;
    } // CreateBiTree
     
    //打印元素
    Status PrintElement(ElemType e)
    {
        
    	printf("%c ",e);
    	return OK;
    }
     
    //2-先序遍历二叉树(递归算法)
    //先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
    Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType e) )
    {
        
    	if(T)
    	{
        
    		if(Visit(T->data)) 
    			if(PreOrderTraverse(T->lchild,Visit))
    				if(PreOrderTraverse(T->rchild,Visit)) return OK;				
    		return ERROR;
    	}
    	else return OK;
    }//PreOrderTraverse
     
     
     
    //3-中序遍历二叉树(递归算法)
    //中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
    Status InOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    {
        
    	if(T)
    	{
         
    		if(InOrderTraverse(T->lchild,Visit))
            	if(Visit(T->data)) 
    				if(InOrderTraverse(T->rchild,Visit))
    					return OK;
    		return ERROR;
    	}else return OK;
    }//PreOrderTraverse
     
     
    //4-后序遍历二叉树(递归算法)
    //后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
    Status PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    {
        
    	if(T)
    	{
        
    		if(PostOrderTraverse(T->lchild,Visit))
    			if(PostOrderTraverse(T->rchild,Visit))
    				if(Visit(T->data))  return OK;					
    		return ERROR;
    	}else return OK;
    }//PreOrderTraverse
     
     
    //构造一个空栈
    Status InitStack(SqStack &S)
    {
        
     S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
     if (!S.base){
        
      printf("栈溢出！\n");
      exit(OVERFLOW);
     }
     S.top = S.base;
     S.stacksize = STACK_INIT_SIZE;
     return OK;
    }
     
    //进栈
    Status Push(SqStack &S, SElemType e)
    {
        
    	if (S.top - S.base >= S.stacksize)
    	{
        
    		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
            if (!S.base)
    		{
        
    			printf("栈溢出!\n");
                return OVERFLOW;
    		}
         S.top = S.base + S.stacksize;
         S.stacksize += STACKINCREMENT;
    	}//若栈满，追加存储空间
        *S.top++ = e;
        return OK;
    }
     
    //出栈
    Status Pop(SqStack &S, SElemType &e)
    {
        
    	if (StackEmpty(S))
    		return ERROR; //判空
            e = *(--S.top);
        return OK;
    }
     
    //判断栈是否为空
    Status StackEmpty(SqStack S)
    {
        
    	if( S.top == S.base )
    		return TRUE;
    	else
    		return FALSE;
     }
     
    //5-中序遍历二叉树(非递归算法)
    Status InOrderTraverse1( BiTree T, Status(*Visit)(ElemType) )
    {
        
        SqStack S;
        BiTree p;
    	p=T;
    	InitStack(S);
    	while (p || !StackEmpty(S)) 
    	{
        
    		if (p) {
         Push(S,p);  p=p->lchild; }  // 非空指针进栈，继续左进
            else {
               // 上层指针退栈，访问其所指结点，再向右进
                  Pop(S,p);  
                  if(!Visit(p->data))
    				return ERROR;
                  p = p->rchild;
        }
      }
      return OK;
    } // InOrderTraverse
     
    //6-层次遍历二叉树
    Status LevelOrderTraverse( BiTree T, Status(*Visit)(ElemType) )
    {
         
    	BiTNode  *Queue[100] ,*p=T ;
                   int  front=0 , rear=0 ;
                   if (p!=NULL) 
    	{
          
    	       Queue[++rear]=p;    /*   根结点入队  */
                        while (front<rear)
    	   {
          
    		   p=Queue[++front];  Visit( p->data );
    		   if (p->lchild!=NULL)
    			   Queue[++rear]=p->lchild;    /*   左结点入队  */
    		   if (p->rchild!=NULL)
    			   Queue[++rear]=p->rchild;    /*   左结点入队  */
    	   }
    	   return OK;
    	}
    	return ERROR;
    }
     
    //7-统计树的叶子结点个数
    Status CountLeafs(BiTree T,int &numofleafs)
    {
        
    	if (T) 
       {
        
          if (T->lchild==NULL&&T->rchild==NULL) numofleafs++;
          CountLeafs(T->lchild,numofleafs); 
          CountLeafs(T->rchild,numofleafs); 
          return OK;
       } 
       else 
    	   return ERROR;
    }
     
    //8-统计树的层次数
    Status CountLevels(BiTree T)
    {
        
       int levelsoflchild=0;
       int levelsofrchild=0;
       if (T) 
       {
         
            levelsoflchild=CountLevels(T->lchild);
            levelsofrchild=CountLevels(T->rchild);
            if(levelsoflchild>levelsofrchild)
    		  return 1+levelsoflchild;
                else return 1+levelsofrchild;
    	}
        else   return 0;
    }
     
    void main()
    {
        
    	BiTree T;
    	int n=0;
    	printf("按先序次序输入二叉树中结点的值:\n");
    	CreateBiTree(T);
    	CountLeafs(T,n);
    	printf("树的叶子结点个数为:%d",n);
        printf("\n树的层次数为:%d\n",CountLevels(T));
        printf("先序遍历二叉树(递归算法):");
    	PreOrderTraverse(T,PrintElement);
        printf("\n中序遍历二叉树(递归算法):");
    	InOrderTraverse(T,PrintElement);
    	printf("\n后序遍历二叉树(递归算法):");
        PostOrderTraverse(T,PrintElement);
    	printf("\n中序遍历二叉树(非递归算法):");
        InOrderTraverse1(T,PrintElement);
    	printf("\n层次遍历二叉树(递归算法):");
        LevelOrderTraverse(T,PrintElement);
    	printf("\n");
    
    }

1.  实验结果  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]

## 五、实验小结 ##

1.  每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除。了根结点外，每个子结点可以分为多个不相交的子树

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305162220546.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70