自上而下输入边来建立树的孩子兄弟链表存储结构(例如#A,AB,AC,BD,##),求树的深度。要求:在一个程序里完成。
程序员文章站
2022-03-24 15:58:09
...
1、 自上而下输入边来建立树的孩子兄弟链表存储结构(例如#A,AB,AC,BD,##),求树的深度。
要求:在一个程序里完成。
#include <stdio.h>
#include <stdlib.h>
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType; // 元素数据类型
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点
SqBiTree bt;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXLEN 100
//树的二叉链表储存结构
typedef struct CSNode //结点结构
{
TElemType Data;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
//队列存储结构及操作
typedef struct QNode
{
CSTree Data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//构造空队列
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
//销毁队列
Status DestoryQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
//入队
Status EnQueue(LinkQueue &Q, CSTree e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
exit(OVERFLOW);
p->Data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
//出队
Status DeQueue(LinkQueue &Q, CSTree &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->Data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
free(p);
return OK;
}
//读队头
Status GetHead(LinkQueue &Q, CSTree &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->Data;
return OK;
}
//建立树的孩子——兄弟链表节点
CSTree GetTreeNode(TElemType e)
{
CSTree p;
p = (CSTree)malloc(sizeof(CSNode));
if (!p)
exit(OVERFLOW);
p->Data = e;
p->firstchild = NULL;
p->nextsibling = NULL;
return p;
}
//建立树的孩子——兄弟链表
Status CreateTree(CSTree &T)
{
char first = ' ', second = ' ';
int result = 0;
LinkQueue Q;
CSTree p, s, r;
InitQueue(Q);
T = NULL;
for (scanf("%c%c", &first, &second);
second != '#'; result = scanf("%c%c", &first, &second))
{
p = GetTreeNode(second);
EnQueue(Q, p);
if (first == '#')
T = p;
else
{
GetHead(Q, s);
while (s->Data != first)
{
DeQueue(Q, s);
GetHead(Q, s);
}
if (!(s->firstchild))
{
s->firstchild = p;
r = p;
}
else
{
r->nextsibling = p;
r = p;
}
}
}
return OK;
}
//求树的深度
int TreeDepth(CSTree T)
{
int h1, h2;
if (!T)
return 0;
else
{
h1 = TreeDepth(T->firstchild);
h2 = TreeDepth(T->nextsibling);
return(((h1 + 1) > h2) ? (h1 + 1) : h2);
}
}
int main(int argc, char const *argv[])
{
CSTree T;
printf("\n树\n");
printf("自上而下自左至右输入树的各条边(如 #AABACADCECFEG##):\n");
CreateTree(T);
printf("树的深度是:%d\n", TreeDepth(T));
system("pause");
return 0;
}
上一篇: 树 - 树的同构
下一篇: ubuntu多版本php切换