数据结构之二叉树实验_数据结构二叉树实验报告

实验目的

1. 通过实验掌握二叉树的基本存储结构；
2. 掌握二叉树的建立与遍历的基本算法，并加以应用；

实验环境

CodeBlocks

实验要求

1. 熟悉c语言的语法知识；
2. 掌握二叉树的链式存储结构—二叉链表的定义、构造、遍历等基本操作；

实验内容

完成二叉树的二叉链表的存储结构的定义、创建、前序遍历、中序遍历、后序遍历、求叶子数和求深度等函数的编写。完成以下函数的编写：
(1) 编写一个函数输出结点的值。visit( BiTree T)
(2)编写一个函数，用递归算法求二叉树的结点总数，函数原型为：int node(BiTree T)。
(3)要求在主函数中实现对以上操作的调用，实现以下功能：
①定义一棵二叉树T，并调用创建函数创建一棵如下图所示的二叉树：

②分别输出二叉树的前序序列、中序序列和后序序列。
③分别输出二叉树的叶子结点数、深度和结点总数。

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1024

typedef char ElemType; /*二叉链表的定义*/
typedef struct BiTreeNode
{
    ElemType data;
    struct BiTreeNode *lchild,*rchild;
}BiTreeNode, *BiTree;

BiTree CreateBiTree(char str[]) /*创建二叉树*/
{
    BiTree bt;
    char ch;
    static int i=0;
    ch=str[i++];
    if(ch=='.')bt=NULL;
    else
    {
        bt=(BiTree)malloc(sizeof(BiTreeNode));
        bt->data=ch;
        bt->lchild=CreateBiTree(str);
        bt->rchild=CreateBiTree(str);
    }
    return bt;
}

void PreOrder(BiTree bt) /*先序遍历*/
{
    if(bt!=NULL)
    {
        visit (bt);
        PreOrder (bt->lchild);
        PreOrder (bt->rchild);
    }
}

void InOrder(BiTree bt) /*中序遍历*/
{
    if(bt!=NULL)
    {
        InOrder (bt->lchild);
        visit (bt);
        InOrder (bt->rchild);
    }
}

void PostOrder(BiTree bt) /*后序遍历*/
{

    if(bt!=NULL)
        {PostOrder (bt->lchild);
        PostOrder (bt->rchild);
        visit (bt);}
}

void visit(BiTree bt) /*输出结点的值*/
{
    if(bt)
        printf("%c",bt->data);
}

int BitreeLeaf (BiTree bt) /*统计二叉树的叶子节点数*/
{
    if (bt==NULL) return 0;
    if (bt->lchild==NULL&&bt->rchild==NULL)
        return 1;
    return (BitreeLeaf (bt->lchild)+BitreeLeaf (bt->rchild));
}

int BitreeDepth (BiTree bt) /*求二叉树的深度*/
{
    int d=0,depthL,depthR;
    if (bt==NULL) return 0;
    depthL=BitreeDepth (bt->lchild);
    depthR=BitreeDepth (bt->rchild);
    d=max (depthL , depthR);
    return d+1;
}

int max(int a,int b) /*判断大小*/
{
  if(a>=b)

        return a;
  else
    return b;
}

int SumNode(BiTree T) /*递归算法求二叉树的结点总数*/
{

    int n;
    if(T==NULL)
        return 0;
    else
    {
        n=SumNode (T->lchild)+SumNode (T->rchild);
        return n+1;
    }
}

void main() /*主函数*/
{
    BiTree T;
    int n;
    char str[MAXSIZE];
    printf("创建一棵二叉树，以.代表空子树：\n");
    gets(str);
    T=CreateBiTree(str);
    printf("\n二叉树的先序遍历得到的序列是：\n");
    PreOrder(T);
    printf("\n二叉树的中序遍历得到的序列是：\n");
    InOrder(T);
    printf("\n二叉树的后序遍历得到的序列是：\n");
    PostOrder(T);
    n=BitreeLeaf(T);
    printf("\n二叉树的叶子节点数为：%d\n",n);
    n=BitreeDepth(T);
    printf("\n二叉树的深度为：%d\n",n);
    n=SumNode(T);
    printf("\n而产生的节点数为：%d\n",n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

运行结果

//小声bb：内容整理不易，各位客官老爷点个赞再走吧~
1