数据结构实验五:二叉树的基本操作
二叉树的基本操作
1 实验目的
- 掌握二叉树的存储实现;
- 掌握二叉树的遍历思想;
- 掌握二叉树的常见算法的程序实现。
2 实验内容
- 建立一棵含有n个结点的二叉树,采用二叉链表存储。按照教材p247中图7.33进行创建;
- 输出二叉树;
- 输出’H’结点的左右孩子结点值;
- 输出二叉树b的高度;
- 释放二叉树。
3 软件程序
btree.cpp:
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
#include <malloc.h>
#include <stdio.h>
#define MaxSize 100
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node* lchild;
struct node* rchild;
} BTNode;
void CreateBTree(BTNode * &b,char * str) // 创建二叉树
{
BTNode* St[MaxSize], * p=NULL;
int top = -1, k, j = 0;
char ch;
b = NULL;
ch = str[j];
while (ch != '\0') {
switch (ch)
{
case '(':top++; St[top]=p; k = 1; break;
case ')':top--; break;
case ',':k = 2; break;
default:p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b == NULL)
b = p;
else
{
switch (k)
{
case 1:St[top]->lchild = p; break;
case 2:St[top]->rchild = p; break;
}
}
}
j++;
ch = str[j];
}
}
void DestroyBTree(BTNode*& b)// 销毁二叉树
{
if (b != NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
BTNode * FindNode(BTNode * b, ElemType x)
{
BTNode * p;
if (b == NULL)
return NULL;
else if (b->data == x)
return b;
else
{
p = FindNode(b->lchild, x);
if (p != NULL)
return p;
else
return FindNode(b->rchild, x);
}
}
BTNode* LchildNode(BTNode* p)// 找孩子节点(左)
{
return p->lchild;
}
BTNode* RchildNode(BTNode* p) // 找孩子节点(右)
{
return p->rchild;
}
int BTHeight(BTNode* b)// 求高度
{
int lchildh, rchildh;
if (b == NULL)return(0);
else {
lchildh = BTHeight(b->lchild);
rchildh = BTHeight(b->rchild);
return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
}
}
void DispBTree(BTNode* b) // 输出二叉树
{
if (b != NULL)
{
printf("%c", b->data);
if (b->lchild != NULL || b->rchild != NULL)
{
printf("(");
DispBTree(b->lchild);
if (b->rchild != NULL)printf(",");
DispBTree(b->rchild);
printf(")");
}
}
}
main.cpp:
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
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*将二叉链表结构定义和其基本运算函数定义放到这里*/
#include "btree.cpp"
/* */
int main()
{
BTNode* b, * p, * lp, * rp;;
printf("二叉树的基本运算如下:\n");
printf(" (1)创建二叉树\n");
CreateBTree(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf(" (2)输出二叉树:"); DispBTree(b); printf("\n");
printf(" (3)H结点:");
p = FindNode(b, 'H');
if (p != NULL)
{
lp = LchildNode(p);
if (lp != NULL)
printf("左孩子为%c ", lp->data);
else
printf("无左孩子 ");
rp = RchildNode(p);
if (rp != NULL)
printf("右孩子为%c", rp->data);
else
printf("无右孩子 ");
}
printf("\n");
printf(" (4)二叉树b的高度:%d\n", BTHeight(b));
printf(" (5)释放二叉树b\n");
DestroyBTree(b);
return 1;
}
4 实验结果
本文由作者按照 CC BY 4.0 进行授权