AI 助理
备案控制台
开发者社区 人工智能 文章 正文

数据结构实验课：实验五、二叉树操作及应用

2022-11-30 163
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构实验课：实验五、二叉树操作及应用

实验五、二叉树操作及应用


一、 实验目的


掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。掌握前序或中序的非递归遍历算法。


二、 实验要求


有如下二叉树：


程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。


#include <stdlib.h>
#include <stdio.h>
typedef char DataType;
typedef struct Node
{
DataType data;/数据域/
struct Node *leftChild;/左子树指针/
struct Node *rightChild;/右子树指针/
}BiTreeNode;/结点的结构体定义/
/初始化创建二叉树的头结点/
void Initiate(BiTreeNode **root)
{
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftChild = NULL;
(*root)->rightChild = NULL;
}
void Destroy(BiTreeNode **root)
{
if((*root) != NULL && (*root)->leftChild != NULL)
Destroy(&(*root)->leftChild);
if((*root) != NULL && (*root)->rightChild != NULL)
Destroy(&(*root)->rightChild);
free(*root);
}
/若当前结点curr非空，在curr的左子树插入元素值为x的新结点/
/原curr所指结点的左子树成为新插入结点的左子树/
/若插入成功返回新插入结点的指针，否则返回空指针/
BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)
{
BiTreeNode *s, *t;
if(curr == NULL) return NULL;
t = curr->leftChild;/保存原curr所指结点的左子树指针/
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->leftChild = t;/新插入结点的左子树为原curr的左子树/
s->rightChild = NULL;
curr->leftChild = s;/新结点成为curr的左子树/
return curr->leftChild;/返回新插入结点的指针/
}
/若当前结点curr非空，在curr的右子树插入元素值为x的新结点/
/原curr所指结点的右子树成为新插入结点的右子树/
/若插入成功返回新插入结点的指针，否则返回空指针/
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x)
{
BiTreeNode *s, *t;
if(curr == NULL) return NULL;
t = curr->rightChild;/保存原curr所指结点的右子树指针/
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->rightChild = t;/新插入结点的右子树为原curr的右子树/
s->leftChild = NULL;
curr->rightChild = s;/新结点成为curr的右子树/
return curr->rightChild;/返回新插入结点的指针/
}
void PreOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数前序遍历二叉树t
{
if(t != NULL)
{//此小段有一处错误
visit(t->data);
PreOrder(t-> rightChild, visit);
PreOrder(t-> leftChild, visit);
}
}
void InOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数中序遍历二叉树t
{
if(t != NULL)
{//此小段有一处错误
InOrder(t->leftChild, visit);
InOrder(t->rightChild, visit);
visit(t->data);
}
}
void PostOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数后序遍历二叉树t
{
if(t != NULL)
{//此小段有一处错误
visit(t->data);
PostOrder(t->leftChild, visit);
PostOrder(t->rightChild, visit);
}
}
void Visit(DataType item)
{
printf("%c ", item);
}
BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中
{
BiTreeNode *find=NULL;
if(root!=NULL)
{
if(root->data == x)
find=root;
else
{
find=Search(root->leftChild,x);
if(find==NULL)
find=Search(root->rightChild,x);
}
}
return find;
}
void main(void)
{
BiTreeNode *root, *p, *pp,*find;
char x=‘E’;
Initiate(&root);
p = InsertLeftNode(root, ‘A’);
p = InsertLeftNode(p, ‘B’);
p = InsertLeftNode(p, ‘D’);
p = InsertRightNode(p, ‘G’);
p = InsertRightNode(root->leftChild, ‘C’);
pp = p;
InsertLeftNode(p, ‘E’);
InsertRightNode(pp, ‘F’);
printf(“前序遍历：”);
PreOrder(root->leftChild, Visit);
printf("\n中序遍历：");
InOrder(root->leftChild, Visit);
printf("\n后序遍历：");
PostOrder(root->leftChild, Visit);
find=Search(root,x);
if(find!=NULL)
printf("\n数据元素%c在二叉树中 \n",x);
else
printf("\n数据元素%c不在二叉树中 \n",x);
Destroy(&root);
}


三、 实验任务：


1.改正程序错误。

2.编写二叉树的前序（或中序）的非递归遍历算法并进行测试。


20210519230440135.png


#include
using namespace std;
stack s;
BiTreeNode *p;
s.push§;
s.top();
s.pop();
s.empty()_


3.完成实验报告的撰写。


代码如下


#include <stdlib.h>
#include <stdio.h>
typedef char DataType;
typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode; /*结点的结构体定义*/
/*初始化创建二叉树的头结点*/
void Initiate(BiTreeNode **root)
{
    *root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*root)->leftChild = NULL;
    (*root)->rightChild = NULL;
}
void Destroy(BiTreeNode **root)
{
    if((*root) != NULL && (*root)->leftChild != NULL)
        Destroy(&(*root)->leftChild);
    if((*root) != NULL && (*root)->rightChild != NULL)
        Destroy(&(*root)->rightChild);
    free(*root);
}
/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/
/*原curr所指结点的左子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)
{
    BiTreeNode *s, *t;
    if(curr == NULL) return NULL;
    t = curr->leftChild;/*保存原curr所指结点的左子树指针*/
    s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data = x;
    s->leftChild = t;/*新插入结点的左子树为原curr的左子树*/
    s->rightChild = NULL;
    curr->leftChild = s;/*新结点成为curr的左子树*/
    return curr->leftChild;/*返回新插入结点的指针*/
}
/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/
/*原curr所指结点的右子树成为新插入结点的右子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x)
{
    BiTreeNode *s, *t;
    if(curr == NULL) return NULL;
    t = curr->rightChild;/*保存原curr所指结点的右子树指针*/
    s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data = x;
    s->rightChild = t;/*新插入结点的右子树为原curr的右子树*/
    s->leftChild = NULL;
    curr->rightChild = s;/*新结点成为curr的右子树*/
    return curr->rightChild;/*返回新插入结点的指针*/
}
void PreOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数前序遍历二叉树t
{
    if(t != NULL)
    {
        //此小段有一处错误  已改
        visit(t->data);
        PreOrder(t-> leftChild, visit);
        PreOrder(t-> rightChild, visit);
    }
}
void InOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数中序遍历二叉树t
{
    if(t != NULL)
    {
        //此小段有一处错误 已改
        InOrder(t->leftChild, visit);
        visit(t->data);
        InOrder(t->rightChild, visit);
    }
}
void PostOrder(BiTreeNode *t, void visit(DataType item))
//使用visit(item)函数后序遍历二叉树t
{
    if(t != NULL)
    {
        //此小段有一处错误  已改
        PostOrder(t->leftChild, visit);
        PostOrder(t->rightChild, visit);
        visit(t->data);
    }
}
void Visit(DataType item)
{
    printf("%c ", item);
}
BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中
{
    BiTreeNode *find=NULL;
    if(root!=NULL)
    {
        if(root->data==x)
            find=root;
        else
        {
            find=Search(root->leftChild,x);
            if(find==NULL)
                find=Search(root->rightChild,x);
        }
    }
    return find;
}
int main()
{
    BiTreeNode *root, *p, *pp,*find;
    char x='E';
    Initiate(&root);
    p = InsertLeftNode(root, 'A');
    p = InsertLeftNode(p, 'B');
    p = InsertLeftNode(p, 'D');
    p = InsertRightNode(p, 'G');
    p = InsertRightNode(root->leftChild, 'C');
    pp = p;
    InsertLeftNode(p, 'E');
    InsertRightNode(pp, 'F');
    printf("前序遍历：");
    PreOrder(root->leftChild, Visit);
    printf("\n中序遍历：");
    InOrder(root->leftChild, Visit);
    printf("\n后序遍历：");
    PostOrder(root->leftChild, Visit);
    find=Search(root,x);
    if(find!=NULL)
        printf("\n数据元素%c在二叉树中 \n",x);
    else
        printf("\n数据元素%c不在二叉树中 \n",x);
    Destroy(&root);
}


第二题


#include <stdlib.h>
#include <stdio.h>
#define MAX 100
typedef char DataType;
typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode; /*结点的结构体定义*/
/*初始化创建二叉树的头结点*/
void Initiate(BiTreeNode **root)
{
    *root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*root)->leftChild = NULL;
    (*root)->rightChild = NULL;
}
void Destroy(BiTreeNode **root)
{
    if((*root) != NULL && (*root)->leftChild != NULL)
        Destroy(&(*root)->leftChild);
    if((*root) != NULL && (*root)->rightChild != NULL)
        Destroy(&(*root)->rightChild);
    free(*root);
}
/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/
/*原curr所指结点的左子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)
{
    BiTreeNode *s, *t;
    if(curr == NULL) return NULL;
    t = curr->leftChild;/*保存原curr所指结点的左子树指针*/
    s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data = x;
    s->leftChild = t;/*新插入结点的左子树为原curr的左子树*/
    s->rightChild = NULL;
    curr->leftChild = s;/*新结点成为curr的左子树*/
    return curr->leftChild;/*返回新插入结点的指针*/
}
/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/
/*原curr所指结点的右子树成为新插入结点的右子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x)
{
    BiTreeNode *s, *t;
    if(curr == NULL) return NULL;
    t = curr->rightChild;/*保存原curr所指结点的右子树指针*/
    s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data = x;
    s->rightChild = t;/*新插入结点的右子树为原curr的右子树*/
    s->leftChild = NULL;
    curr->rightChild = s;/*新结点成为curr的右子树*/
    return curr->rightChild;/*返回新插入结点的指针*/
}
//前序遍历非递归算法
void Prev(Node *root)
{
    Node *p,*node[MAX];
    int top=0;
    p=root;
    do
    {
        while(p!=NULL)
        {
            printf("%c",p->data);
            node[top]=p;
            top++;
            p=p->leftChild;
        }
        if(top>0)
        {
            top--;
            p=node[top];
            p=p->rightChild;
        }
    }
    while(top>0||p!=NULL);
}
//中序遍历非递归算法
void min(Node *root)
{
    Node *p,*node[MAX];
    int top=0;
    p=root;
    do
    {
        while(p!=NULL)
        {
            node[top]=p;
            top++;
            p=p->leftChild;
        }
        if(top>0)
        {
            top--;
            p=node[top];
            printf("%c",p->data);
            p=p->rightChild;
        }
    }
    while(top>0||p!=NULL);
}
BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中
{
    BiTreeNode *find=NULL;
    if(root!=NULL)
    {
        if(root->data==x)
            find=root;
        else
        {
            find=Search(root->leftChild,x);
            if(find==NULL)
                find=Search(root->rightChild,x);
        }
    }
    return find;
}
int main(void)
{
    BiTreeNode *root, *p, *pp,*find;
    char x='E';
    Initiate(&root);
    p = InsertLeftNode(root, 'A');
    p = InsertLeftNode(p, 'B');
    p = InsertLeftNode(p, 'D');
    p = InsertRightNode(p, 'G');
    p = InsertRightNode(root->leftChild, 'C');
    pp = p;
    InsertLeftNode(p, 'E');
    InsertRightNode(pp, 'F');
    printf("前序遍历：");
    Prev(root->leftChild);
    printf("\n中序遍历：");
    min(root->leftChild);
    find=Search(root,x);
    if(find!=NULL)
        printf("\n数据元素%c在二叉树中 \n",x);
    else
        printf("\n数据元素%c不在二叉树中 \n",x);
    Destroy(&root);
}
文章标签：
算法
存储
关键词：
数据结构应用
数据结构二叉树
数据结构实验二叉树
数据结构实验
数据结构二叉树应用
superlistboy
目录
相关文章
龙大吉
|
2月前
|
存储 Java
Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称，而TreeMap则擅长于保持元素的自然排序或自定义排序，两者各具优势，适用于不同的开发场景。
龙大吉
47 1
XIAZHI
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
XIAZHI
73 4
龙大吉
|
13天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
32 5
土木林森
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
36 1
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
111 8
那年春天
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础，它们贯穿于各种应用场景中，为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势，开发者需要根据具体需求选择合适的数据结构，以实现高效、可靠的程序设计。
那年春天
84 7
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
26 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
140 9
那年春天
|
26天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
24 1
德国都芳最好
|
29天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
78 21