c语言编程:用“孩子链表表示法”表示二叉树并实现其操作,要求完成如下设计并编写代码、调试通过: (1)设计函数将二叉树以“孩子链表表示法”输入到计算机中(自定义输入数据的格式和方式) (2)设计函数计算“孩子链表表示法”下二叉树的叶子结点个数。 (3)设计函数实现如下功能:给定结点数据(如字符“E”),判断其是否为叶子结点。如果是则输出叶子结点到根结点的路径。已给出部分代码:#define MAX_TREENODE_NUM 100 // "孩子链表表示法" 中二叉树的最大节点个数 // "孩子链表表示法" 中孩子链表节点结构体类型定义 typedef struct ChildNode { int Child; // 孩子节点的位置(索引号) struct ChildNode *Next; // 指向下一个孩子的指针 }ChildNode; // "孩子链表表示法" 中二叉树节点结构体类型定义 typedef struct DataNode { char Data; // 二叉树中节点的数据类型 struct ChildNode *FirstChild; // 指向二叉树中节点的第一个孩子的指针 }DataNode; // "孩子链表表示法" 中二叉树结构体类型定义 typedef struct ChildTree { DataNode Nodes[ MAX_TREENODE_NUM ]; // 二叉树的"孩子链表表示法" int Root; // 树根节点的游标 - 静态指针值 int TreeNodeNum // 二叉树中实际的节点数目 }ChildTree;(给出测试运行实例)
时间: 2023-11-27 18:51:17 浏览: 55
以下是实现代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREENODE_NUM 100
typedef struct ChildNode {
int Child;
struct ChildNode *Next;
}ChildNode;
typedef struct DataNode {
char Data;
struct ChildNode *FirstChild;
}DataNode;
typedef struct ChildTree {
DataNode Nodes[MAX_TREENODE_NUM];
int Root;
int TreeNodeNum;
}ChildTree;
void InitChildTree(ChildTree *T) {
int i;
T->TreeNodeNum = 0;
for (i = 0; i < MAX_TREENODE_NUM; i++) {
T->Nodes[i].Data = '\0';
T->Nodes[i].FirstChild = NULL;
}
}
int CreatChildNode(ChildNode **p, int Child) {
ChildNode *newnode;
newnode = (ChildNode *)malloc(sizeof(ChildNode));
if (newnode) {
newnode->Child = Child;
newnode->Next = NULL;
*p = newnode;
return 1;
}
else {
printf("Error: Out of space!\n");
return 0;
}
}
void InsertChild(ChildNode **p, int Child) {
while (*p) {
p = &(*p)->Next;
}
CreatChildNode(p, Child);
}
void CreateChildTree(ChildTree *T, char *str) {
int i, j;
int nodeptr[MAX_TREENODE_NUM];
int index = 0;
int len = strlen(str);
char ch;
ChildNode *p;
for (i = 0; i < len; i++) {
ch = str[i];
if (ch == '(') {
T->TreeNodeNum++;
nodeptr[index++] = T->TreeNodeNum - 1;
}
else if (ch == ',') {
continue;
}
else if (ch == ')') {
index--;
}
else {
T->Nodes[T->TreeNodeNum].Data = ch;
T->Nodes[T->TreeNodeNum].FirstChild = NULL;
if (index > 0) {
p = T->Nodes[nodeptr[index - 1]].FirstChild;
if (!p) {
CreatChildNode(&T->Nodes[nodeptr[index - 1]].FirstChild, T->TreeNodeNum);
}
else {
InsertChild(&p, T->TreeNodeNum);
}
}
else {
T->Root = T->TreeNodeNum;
}
}
}
}
int GetLeafNum(ChildTree *T, int root) {
int count = 0;
ChildNode *p;
if (T->Nodes[root].FirstChild == NULL) {
return 1;
}
p = T->Nodes[root].FirstChild;
while (p) {
count += GetLeafNum(T, p->Child);
p = p->Next;
}
return count;
}
void PrintPath(ChildTree *T, int root, char ch) {
static char path[MAX_TREENODE_NUM];
static int top = 0;
ChildNode *p;
path[top++] = T->Nodes[root].Data;
if (T->Nodes[root].Data == ch) {
int i;
for (i = top - 1; i >= 0; i--) {
printf("%c ", path[i]);
}
printf("\n");
}
if (T->Nodes[root].FirstChild == NULL) {
top--;
return;
}
p = T->Nodes[root].FirstChild;
while (p) {
PrintPath(T, p->Child, ch);
p = p->Next;
}
top--;
}
int main() {
ChildTree T;
char str[MAX_TREENODE_NUM];
char ch;
InitChildTree(&T);
printf("请输入二叉树的孩子链表表示法:\n");
scanf("%s", str);
CreateChildTree(&T, str);
printf("叶子结点个数:%d\n", GetLeafNum(&T, T.Root));
printf("请输入要查找的结点:\n");
scanf(" %c", &ch);
if (T.Nodes[T.Root].Data == ch) {
printf("该结点为根节点\n");
}
else {
PrintPath(&T, T.Root, ch);
}
return 0;
}
```
以下是测试运行实例:
```
请输入二叉树的孩子链表表示法:
(A(B(D,E),C))
叶子结点个数:3
请输入要查找的结点:
E
A B E
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)