数据结构上机实践第九周项目3 - 利用二叉树遍历思想解决问题

简介: 数据结构上机实践第九周项目3 - 利用二叉树遍历思想解决问题

利用二叉树遍历思想解决问题

学以致用,知行合一,学了知识就要会运用,否则跟背课文没什么区别,上次实践,做了二叉树递归遍历的算法实现,本次实践,将利用遍历思想解决问题,将遍历思想真正的运用到实际问题需求中。(编译环境:VC++6.0)

本次实践所用到的二叉树算法库点击此处参考

注:用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的用于测试的二叉树如下——  

image.png

项目要求如下:

假设二叉树采用二叉链存储结构存储,分别实现以下算法,并在程序中完成测试:

 (1)计算二叉树节点个数;

 (2)输出所有叶子节点;

 (3)求二叉树b的叶子节点个数

 (4)设计一个算法Level(b,x,h),返回二叉链b中data值为x的节点的层数。

 (5)判断二叉树是否相似(关于二叉树t1和t2相似的判断:①t1和t2都是空的二叉树,相似;②t1和t2之一为空,另一不为空,则不相似;③t1的左子树和t2的左子树是相似的,且t1的右子树与t2的右子树是相似的,则t1和t2相似。)

实现源代码如下:

(1)计算二叉树节点个数;  

//*Copyright  (c)2017,烟台大学计算机与控制工程学院*               
//*All rights reservrd.*               
//*文件名称 :main.cpp*               
//*作者:田长航*            
//*完成时间:2017年10月26日*                
//*版本号:v1.0*            
//*问题描述:测试函数*               
//*输入描述:无*               
//*程序输出:无* 
#include <stdio.h>
#include "btree.h"
int Nodes(BTNode *b)
{
    if (b==NULL)
        return 0;
    else
        return Nodes(b->lchild)+Nodes(b->rchild)+1;
}
int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("二叉树节点个数: %d\n", Nodes(b));
    DestroyBTNode(b);
    return 0;
}

测试结果截图如下:

2018122814580746.png

(2)输出所有叶子节点;

//*Copyright  (c)2017,烟台大学计算机与控制工程学院*               
//*All rights reservrd.*               
//*文件名称 :main.cpp*               
//*作者:田长航*            
//*完成时间:2017年10月26日*                
//*版本号:v1.0*            
//*问题描述:测试函数*               
//*输入描述:无*               
//*程序输出:无* 
#include <stdio.h>
#include "btree.h"
void DispLeaf(BTNode *b)
{
    if (b!=NULL)
    {
        if (b->lchild==NULL && b->rchild==NULL)
            printf("%c ",b->data);
        else
        {
            DispLeaf(b->lchild);
            DispLeaf(b->rchild);
        }
    }
}
int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("二叉树中所有的叶子节点是: ");
    DispLeaf(b);
    printf("\n");
    DestroyBTNode(b);
    return 0;
}

测试结果截图如下:

2018122814580746.png

(3)求二叉树b的叶子节点个数

//*Copyright  (c)2017,烟台大学计算机与控制工程学院*               
//*All rights reservrd.*               
//*文件名称 :main.cpp*               
//*作者:田长航*            
//*完成时间:2017年10月26日*                
//*版本号:v1.0*            
//*问题描述:测试函数*               
//*输入描述:无*               
//*程序输出:无* 
#include <stdio.h>
#include "btree.h"
int LeafNodes(BTNode *b)    //求二叉树b的叶子节点个数
{
    int num1,num2;
    if (b==NULL)
        return 0;
    else if (b->lchild==NULL && b->rchild==NULL)
        return 1;
    else
    {
        num1=LeafNodes(b->lchild);
        num2=LeafNodes(b->rchild);
        return (num1+num2);
    }
}
int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("二叉树b的叶子节点个数: %d\n",LeafNodes(b));
    DestroyBTNode(b);
    return 0;
}

测试结果截图如下:

2018122814580746.png

(4)设计一个算法Level(b,x,h),返回二叉链b中data值为x的节点的层数。

//*Copyright  (c)2017,烟台大学计算机与控制工程学院*               
//*All rights reservrd.*               
//*文件名称 :main.cpp*               
//*作者:田长航*            
//*完成时间:2017年10月26日*                
//*版本号:v1.0*            
//*问题描述:测试函数*               
//*输入描述:无*               
//*程序输出:无* 
#include <stdio.h>
#include "btree.h"
int Level(BTNode *b,ElemType x,int h)
{
    int l;
    if (b==NULL)
        return 0;
    else if (b->data==x)
        return h;
    else
    {
        l=Level(b->lchild,x,h+1);
        if (l==0)
            return Level(b->rchild,x,h+1);
        else
            return l;
    }
}
int main()
{
    BTNode *b;
    CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("值为\'K\'的节点在二叉树中出现在第 %d 层上n",Level(b,'K',1));
    DestroyBTNode(b);
    return 0;
}

测试结果截图如下:

2018122814580746.png

(5)判断二叉树是否相似(关于二叉树t1和t2相似的判断:①t1和t2都是空的二叉树,相似;②t1和t2之一为空,另一不为空,则不相似;③t1的左子树和t2的左子树是相似的,且t1的右子树与t2的右子树是相似的,则t1和t2相似。)

//*Copyright  (c)2017,烟台大学计算机与控制工程学院*               
//*All rights reservrd.*               
//*文件名称 :main.cpp*               
//*作者:田长航*            
//*完成时间:2017年10月26日*                
//*版本号:v1.0*            
//*问题描述:测试函数*               
//*输入描述:无*               
//*程序输出:无* 
#include <stdio.h>
#include "btree.h"
int Like(BTNode *b1,BTNode *b2)
{
    int like1,like2;
    if (b1==NULL && b2==NULL)
        return 1;
    else if (b1==NULL || b2==NULL)
        return 0;
    else
    {
        like1=Like(b1->lchild,b2->lchild);
        like2=Like(b1->rchild,b2->rchild);
        return (like1 & like2);
    }
}
int main()
{
    BTNode *b1, *b2, *b3;
    CreateBTNode(b1,"B(D,E(H(J,K(L,M(,N)))))");
    CreateBTNode(b2,"A(B(D(,G)),C(E,F))");
    CreateBTNode(b3,"u(v(w(,x)),y(z,p))");
    if(Like(b1, b2))
        printf("b1和b2相似\n");
    else
        printf("b1和b2不相似\n");
    if(Like(b2, b3))
        printf("b2和b3相似\n");
    else
        printf("b2和b3不相似\n");
    DestroyBTNode(b1);
    DestroyBTNode(b2);
    DestroyBTNode(b3);
    return 0;
}

测试结果截图如下:

2018122814580746.png

相关文章
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
70 4
|
26天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
86 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
27 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1