Catalog
  1. 1. 问题描述
    1. 1.0.1. 1.二叉树的创建(顺序存储&链式存储)
    2. 1.0.2. 2.进行先序或中序或后序遍历
    3. 1.0.3. 运行界面
数据结构实验五

问题描述

1.二叉树的创建(顺序存储&链式存储)

2.进行先序或中序或后序遍历

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
#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;

//二叉树顺序存储
#define MAX_TREE_SIZE 100
typedef int TElemType;
TElemType Nil = 0;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
int SqBiTree_Len;

void InitSqBiTree(SqBiTree &bt)
{
for (int i = 0; i < MAX_TREE_SIZE; i++)
bt[i] = Nil;
printf("二叉树顺序初始化完毕\n");
return;
}

void CreateSqBiTree(SqBiTree &bt)
{

printf("请输入结点个数(小于%d)\n", MAX_TREE_SIZE);
scanf("%d", &SqBiTree_Len);
printf("请输入各结点的值(非零),空结点输入零,两结点之间用空格分开\n");
for (int i = 0; i < SqBiTree_Len; i++) {
scanf("%d", &bt[i]);
if (i != 0 && bt[(i + 1) / 2 - 1] == Nil && bt[i] != Nil) {
printf("无双亲的非根节点,顺序存储失败!\n");
return;
}
}
printf("二叉树顺序存储成功\n");
return;
}

void SqPreOrderTraverse(SqBiTree bt,int i)
{
if (bt[i - 1] != 0) {
printf("%d ", bt[i - 1]);
SqPreOrderTraverse(bt, i * 2);
SqPreOrderTraverse(bt, i * 2 + 1);
}
return;
}

//二叉树链式存储
typedef enum PointerTag { Link, Thread };
typedef struct BiThrNode {
TElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

void CreateThrBiTree(BiThrTree &T)
{
char ch;
cin >> ch;
//scanf("%c", &ch);
if (ch == '#')
T = NULL;
else {
T = (BiThrNode*)malloc(sizeof(BiThrNode));
T->data = ch - '0';
CreateThrBiTree(T->lchild);
CreateThrBiTree(T->rchild);
}
return;
}

void ThrPreOrderTraverse(BiThrNode* T)
{
if (T != NULL) {
printf("%d ", T->data);
ThrPreOrderTraverse(T->lchild);
ThrPreOrderTraverse(T->rchild);
}
return;
}

int main()
{
InitSqBiTree(bt);
CreateSqBiTree(bt);
printf("先序遍历顺序二叉树结果为:");
SqPreOrderTraverse(bt, 1);
printf("\n\n");

BiThrTree T;
printf("请输入结点内容,空结点则输入#\n");
CreateThrBiTree(T);
printf("先序遍历链式二叉树结果为:");
ThrPreOrderTraverse(T);
printf("\n");
return 0;
}

运行界面

sy

Author: Christopher Shen
Link: https://www.pasxsenger.com/2019/11/04/数据结构实验五/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶