数据结构实验三 二叉树的基本操作_按纵向树形显示二叉树

★观前提示：本篇内容为数据结构实验，代码内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。

一、实验目的

1.掌握二叉树的建立算法
2.掌握二叉树的前序、中序和后序遍历算法。

二、实验要求

要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。

★温馨提示：以下代码均为改正过的代码，皆已经过测试。

三、源码实现

#include<stdio.h>
#include<stdlib.h>//定义头文件 
#include<string.h>
#include<math.h>

typedef char DataType;//定义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);
}
//主函数 
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);

    Destroy(&root);

}
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
127
128
129
130
131
132
133
134
135
136
137
138
139

四、实验总结

① 通过本次实验，了解和掌握了二叉树的建立算法，对二叉树有了进步的认识和了解。
② 通过多次尝试对二叉树的代码实现，理解了二叉树如何生成及其实现原理。
③ 明白了二叉树的代码实现逻辑，掌握了二叉树的三种遍历算法如：前序、中序和后序遍历算法等。

2022.5.21记录：Code_流苏(CSDN)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。