1、一棵树采用孩子链存储结构/或长子兄弟链存储结构(任选一种),尝试编程实现: (1)创建一棵树 (2)设计一个算法求高度 (3)设计一个算法实现树的层次遍历 (4)设计两个算法实现先根遍历和后根遍历 具体代码
时间: 2024-02-02 08:02:53 浏览: 19
很高兴能为您解答问题!
以下是C++代码实现,采用孩子链存储结构:
```c++
#include<iostream>
using namespace std;
typedef char ElemType; // 假设树结点数据类型为字符型
const int MAXSIZE = 100;
// 孩子结点
typedef struct CTNode {
int child; // 子结点在数组中的下标
struct CTNode *next; // 指向下一个孩子结点的指针
} *ChildPtr;
// 树结点
typedef struct {
ElemType data; // 结点数据
ChildPtr firstchild; // 指向第一个孩子结点的指针
} CTBox;
// 树的类型定义
typedef struct {
CTBox nodes[MAXSIZE]; // 树的结点数组
int r, n; // 根结点的位置和结点数
} CTree;
void CreateCTree(CTree &T, int r, int n, char data[], int parent[]) {
// r为根结点位置,n为结点数
T.r = r;
T.n = n;
ChildPtr p;
for (int i = 0; i < n; i++) {
T.nodes[i].data = data[i];
T.nodes[i].firstchild = NULL;
}
for (int i = 0; i < n; i++) {
if (parent[i] == -1) continue; // 根结点不创建孩子结点
p = new CTNode;
p->child = i;
p->next = T.nodes[parent[i]].firstchild;
T.nodes[parent[i]].firstchild = p;
}
}
int CTreeHeight(CTree T, int p) {
// p是以 T.r 为根的子树的根结点位置
if (!T.nodes[p].firstchild) {
// 没有孩子结点
return 0;
} else {
ChildPtr q = T.nodes[p].firstchild;
int h = 0;
while (q) {
// 遍历子树的每个孩子结点,求出孩子结点的高度
int tmp = CTreeHeight(T, q->child) + 1;
if (tmp > h) h = tmp;
q = q->next;
}
return h;
}
}
void CTreeLevelOrder(CTree T) {
int queue[MAXSIZE];
int front = 0, rear = 0;
int level = 0;
queue[rear++] = T.r;
cout << "Level " << level << ": ";
while (front < rear) {
int p = queue[front++];
cout << T.nodes[p].data << " ";
ChildPtr q = T.nodes[p].firstchild;
while (q) {
queue[rear++] = q->child;
q = q->next;
}
if (front == rear) {
cout << endl;
if (rear < T.n) cout << "Level " << ++level << ": ";
}
}
}
void CTreePreOrder(CTree T, int p) {
cout << T.nodes[p].data << " ";
ChildPtr q = T.nodes[p].firstchild;
while (q) {
CTreePreOrder(T, q->child);
q = q->next;
}
}
void CTreePostOrder(CTree T, int p) {
ChildPtr q = T.nodes[p].firstchild;
while (q) {
CTreePostOrder(T, q->child);
q = q->next;
}
cout << T.nodes[p].data << " ";
}
int main() {
int n, r;
cout << "请输入结点数和根结点位置:";
cin >> n >> r;
char data[MAXSIZE];
int parent[MAXSIZE];
cout << "请逐个输入结点的数据和父结点的下标,-1表示该结点为根结点:" << endl;
for (int i = 0; i < n; i++) {
cin >> data[i] >> parent[i];
}
CTree T;
CreateCTree(T, r, n, data, parent);
cout << "树初始化完成!" << endl;
cout << "树的高度为:" << CTreeHeight(T, r) << endl;
cout << "树的层次遍历结果为:" << endl;
CTreeLevelOrder(T);
cout << "树的先根遍历结果为:";
CTreePreOrder(T, r);
cout << endl;
cout << "树的后根遍历结果为:";
CTreePostOrder(T, r);
cout << endl;
return 0;
}
```
以上代码采用孩子链存储结构,如果需要使用长子兄弟链存储结构,只需要修改对应的结构体定义和相应的函数代码即可。