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

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

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


一、 实验目的


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


二、 实验要求


有如下二叉树:


程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法,同时也给出了查询“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);
}
相关文章
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
47 1
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
73 4
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
32 5
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
36 1
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
111 8
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
84 7
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
140 9
|
26天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
29天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。