实验5：树（二叉树）（采用二叉链表存储）
一、实验项目名称
二叉树及其应用
二、实验目的
熟悉二叉树的存储结构的特性以及二叉树的基本操作。
三、实验基本原理
之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。
四、主要仪器设备及耗材
Window 11、Dev-C++5.11
五、实验步骤
1.导入库和预定义
2.创建二叉树
3.前序遍历
4.中序遍历
5.后序遍历
6.总结点数
7.叶子节点数
8.树的深度
9.树根到叶子的最长路径
10.交换所有节点的左右子女
11.顺序存储
12.显示顺序存储
13.测试函数和主函数
对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。
实验完整代码：
#include <bits/stdc++.h>
using namespace std;
#define MAX_TREE_SIZE 100
typedef char ElemType;
ElemType SqBiTree[MAX_TREE_SIZE];
struct BiTNode
{
    ElemType data;
    BiTNode *l,*r;
}*T;
void createBiTree(BiTNode *&T)
{
    ElemType e;
    e = getchar();
       
    if(e == '\n')
        return;
    else if(e == ' ')
        T = NULL;
    else
    {
        if(!(T = (BiTNode *)malloc(sizeof (BiTNode))))   
        {
            cout << "内存分配错误!" << endl;
            exit(0);
        }
       
        T->data = e;
        createBiTree(T->l);
        createBiTree(T->r);   
    }   
}
void createBiTree2(BiTNode *T,int u)
{
    if(T)
    {
        SqBiTree[u] = T->data;
        createBiTree2(T->l,2 * u + 1);
        createBiTree2(T->r,2 * u + 2);
    }
}
void outputBiTree2(int n)
{
    int cnt = 0;
    for(int i = 0;cnt <= n;i++)
    {
        cout << SqBiTree[i];
        if(SqBiTree[i] != ' ')
            cnt ++;
    }
    cout << endl;
}
void preOrderTraverse(BiTNode *T)
{
    if(T)
    {
        cout << T->data;
        preOrderTraverse(T->l);
        preOrderTraverse(T->r);
    }
}
void inOrderTraverse(BiTNode *T)
{
    if(T)
    {
        inOrderTraverse(T->l);
        cout << T->data;
        inOrderTraverse(T->r);   
    }   
}
void beOrderTraverse(BiTNode *T)
{
    if(T)
    {
        beOrderTraverse(T->l);
二叉树的基本性质
        beOrderTraverse(T->r);
        cout << T->data;
    }
}
int sumOfVer(BiTNode *T)
{
    if(!T)
        return 0;
       
    return sumOfVer(T->l) + sumOfVer(T->r) + 1;
}
int sumOfLeaf(BiTNode *T)
{
    if(!T)
        return 0;
    if(T->l == NULL && T->r == NULL)
        return 1;
    return sumOfLeaf(T->l) + sumOfLeaf(T->r);
}
int depth(BiTNode *T)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。