1. AI技术聚合首页
  2. IT

《数据结构》实验报告五：二叉树

乘风 • • IT • 阅读 33

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法

3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念

1、二叉树：

       二叉树是n个结点（n>=0）的有限集合。该集合或为空集（n=0）；或由一个根节点和两棵互不相交的、分别称为该根节点的左子树的右子树的二叉树构成。（递归定义）

2、递归遍历：

       二叉树的递归遍历常见有三种：前序、中序、后序遍历。（这里的前、中、后指的是根结点的访问次序）

       前序遍历按照“根结点->左孩子->右孩子”的顺序访问结点；

       中序遍历按照“左孩子->根结点->右孩子”的顺序访问结点；

       后序遍历按照“左孩子->右孩子->根结点”的顺序访问结点。

       其中在访问左孩子和右孩子的时候依然使用对应的前序、中序或后序遍历。

3、非递归遍历：

       利用栈实现的非递归遍历，也分为三种：前序、中序、后序遍历。

       以中序遍历为例，按照“左孩子->根结点->右孩子”的顺序进行访问。

       从一棵二叉树的根节点开始，依次访问该根结点的左孩子、左孩子的左孩子……，并保存一路走过的根节点（依次入栈），直至左子树为空。

       左子树为空说明该左孩子遍历完成，接着根节点出栈，并访问出栈的根节点（该根节点为最后经过的根节点），然后借助出栈的根节点进入该根节点的右子树继续进行访问。利用栈后入先出的特点，实现了二叉树的非递归遍历。

4、层序遍历：

       从一棵树的根结点开始，按照从上到下、从左到右的顺序依次访问树中的每一个结点。

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。

#include<stdio.h>
#include<malloc.h>
#define MAX 20

typedef struct BTNode{         /*二叉树结点结构声明*/
	char data ;                /*节点数据*/
	struct BTNode *lchild;
	struct BTNode *rchild ;    /*孩子指针*/
}*BiTree;

void createBiTree(BiTree *t){  /*先序遍历创建二叉树*/
	char s;
	BiTree q;
	printf("\nplease input data:(exit for #)");
	s=getche();   //getche:输入后立即从控制台取字符,不以回车为结束(带回显)
	//输入#,说明该树为空
	if('#' == s)
    {
	    *t = NULL;
        return;
    }
    //输入非'#':为根结点分配空间
	q = (BiTree)malloc(sizeof(struct BTNode));
	/*分配失败*/
	if( !q )
    {
        printf("Memory alloc failure!");
        exit(0);
    }
    /*分配成功*/
	q->data = s;
	*t = q;
	createBiTree(&q->lchild);  /*递归建立左子树*/
	createBiTree(&q->rchild);  /*递归建立右子树*/
}

void PreOrder(BiTree p){  /*先序遍历二叉树*/
    if( p!= NULL )
    {
       	printf("%c",p->data);
       	PreOrder(p->lchild);
       	PreOrder(p->rchild);
    }
}

void InOrder(BiTree p){  /*中序遍历二叉树*/
    if( p!= NULL )
    {
 	    InOrder(p->lchild);
        printf("%c",p->data);
   	    InOrder(p->rchild);
    }
}

void PostOrder(BiTree p){  /*后序遍历二叉树*/
    if( p!= NULL )
    {
    	PostOrder(p->lchild);
       	PostOrder(p->rchild);
       	printf("%c",p->data);
    }
}

void Preorder_n(BiTree p){  /*先序遍历的非递归算法*/
    BiTree stack[MAX];  //准备一个顺序栈存储结点
    BiTree q;
    int top = 0;  //top=0:栈空
    int i;
    for(i=0;i<MAX;i++)    /*初始化栈*/
        stack[i] = NULL;
    q = p;  //设置q指向待遍历的二叉树
    while( q != NULL )
    {
        printf("%c",q->data);  //先访问根节点
        if(q->rchild != NULL)
            stack[top++] = q->rchild;

        if(q->lchild != NULL)
            q = q->lchild;
        //结点的左孩子为空,说明该结点的左子树访问结束,进入下一二叉树（出栈）
        else
        {
            if(top > 0)
               q = stack[--top];
            else
               q = NULL;
        }
    }
}

void release(BiTree t){ /*释放二叉树空间*/
  	if(t!=NULL)
    {
    	release(t->lchild);
    	release(t->rchild);
    	free(t);
  	}
}

int main(){
    BiTree t = NULL;
    createBiTree(&t);
    printf("\n\nPreOrder the tree is:");
    PreOrder(t);
    printf("\n\nInOrder the tree is:");
    InOrder(t);
    printf("\n\nPostOrder the tree is:");
    PostOrder(t);
    printf("\n\n先序遍历序列（非递归）:");
    Preorder_n(t);
    release(t);
    return 0;
}
  • 运行程序：

       输入：ABC##DE#G##F###

  • 运行结果：

  • 二叉树形态：

2、在上题中补充求二叉树中结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。

算法代码（递归算法）：

int Num_of_Nodes(BiTree t){  /*求二叉树t的结点总数,函数返回值即结点总数*/
    BiTree q;
    q = t;

    //二叉树为空，直接返回0
    if( !q )
        return 0;

    //二叉树非空，总结点数 = 1 + 左子树的总结点数 + 左子树的总结点数
    int num_l = Num_of_Nodes(q->lchild);
    int num_r = Num_of_Nodes(q->rchild);

    return (1 + num_l + num_r);
}

主函数补充代码：

int main(){
    BiTree t = NULL;
    createBiTree(&t);
    printf("\n\nPreOrder the tree is:");
    PreOrder(t);
    printf("\n\nInOrder the tree is:");
    InOrder(t);
    printf("\n\nPostOrder the tree is:");
    PostOrder(t);
    printf("\n\n先序遍历序列（非递归）:");
    Preorder_n(t);

    //主函数添加代码
    printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));

    release(t);
    return 0;
}

运行结果：

3、在上题中补充求二叉树中叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。

算法代码（递归算法）：

int Num_of_LeafNodes(BiTree t){  /*求二叉树t的叶子结点总数,函数返回值即叶子结点总数*/
    BiTree q;
    q = t;

    //二叉树为空，直接返回0
    if( !q )
        return 0;
    //结点的左右子树均为空，则该结点为叶子结点
    if( !(q->lchild) && !(q->rchild) )
        return 1;

    //二叉树非空，叶子结点总数 = 左子树的叶子结点总数 + 右子树的叶子结点总数
    int num_l = Num_of_LeafNodes(q->lchild);
    int num_r = Num_of_LeafNodes(q->rchild);

    return (num_l + num_r);
}

主函数补充代码：

int main(){
    BiTree t = NULL;
    createBiTree(&t);
    printf("\n\nPreOrder the tree is:");
    PreOrder(t);
    printf("\n\nInOrder the tree is:");
    InOrder(t);
    printf("\n\nPostOrder the tree is:");
    PostOrder(t);
    printf("\n\n先序遍历序列（非递归）:");
    Preorder_n(t);

    //主函数添加代码
    printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
    printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));

    release(t);
    return 0;
}

运行结果：

4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。

算法代码（递归算法）：

int Depth_of_BiTree(BiTree t){  /*求二叉树t的深度,函数返回值即二叉树深度*/
    BiTree q;
    q = t;

    //二叉树为空，直接返回0
    if( !q )
        return 0;

    //二叉树非空，深度 = 1 + Max（左子树深度，右子树深度）
    int dep_l = Depth_of_BiTree(q->lchild);
    int dep_r = Depth_of_BiTree(q->rchild);
    int dep = 1 + ( (dep_l > dep_r)?dep_l:dep_r );

    return dep;
}

主函数补充代码： 

int main(){
    BiTree t = NULL;
    createBiTree(&t);
    printf("\n\nPreOrder the tree is:");
    PreOrder(t);
    printf("\n\nInOrder the tree is:");
    InOrder(t);
    printf("\n\nPostOrder the tree is:");
    PostOrder(t);
    printf("\n\n先序遍历序列（非递归）:");
    Preorder_n(t);

    //主函数添加代码
    printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
    printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
    printf("\n\n此二叉树深度为:%d",Depth_of_BiTree(t));

    release(t);
    return 0;
}

运行结果：

5、补充二叉树中序非递归遍历算法，并给出运行结果。

算法代码：

void Inorder_n(BiTree p){  /*中序遍历的非递归算法*/
    BiTree stack[MAX];     //准备一个顺序栈存储结点
    BiTree q;
    int top = 0;           //top = 0:栈空
    int i;
    for(i=0;i<MAX;i++)     /*初始化栈*/
        stack[i] = NULL;

    q = p;  //q指向遍历的二叉树
    while( q || top > 0 )
    {
        //结点非空
        if( q )
        {
            stack[top++] = q;  //根节点入栈
            q = q->lchild;     //进入左子树
        }

        //结点为空，栈非空
        else
        {
            q = stack[--top];      //根结点出栈
            printf("%c",q->data);  //访问根节点
            q = q->rchild;         //进入右子树
        }
    }
}

 主函数补充代码：

int main(){
    BiTree t = NULL;
    createBiTree(&t);
    printf("\n\nPreOrder the tree is:");
    PreOrder(t);
    printf("\n\nInOrder the tree is:");
    InOrder(t);
    printf("\n\nPostOrder the tree is:");
    PostOrder(t);
    printf("\n\n先序遍历序列（非递归）:");
    Preorder_n(t);

    //主函数添加代码
    printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
    printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
    printf("\n\n此二叉树深度为:%d",Depth_of_BiTree(t));
    printf("\n\n中序遍历序列（非递归）:");
    Inorder_n(t);

    release(t);
    return 0;
}

运行结果：

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
乘风的头像乘风管理团队
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐