欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

自上而下输入边来建立树的孩子兄弟链表存储结构(例如#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;
}

相关标签: 数据结构