看数据结构写代码（30） 树的双亲孩子表示法的实现

树的 实现 方法 有三种：1.双亲 表示法  2. 孩子 表示 方法 3 结合 双亲 孩子 表示法 4. 二叉链表法

其中 前三种  都是 顺序 表示法， 都是 用 一组 顺序的 内存 空间 来表示 树。其中 在每个节点 上 加上 双亲 索引 位置的 叫做 双亲 表示法，在 每个节点上 加上 一个 孩子 链表的叫做 孩子 表示法。 这个链表 存储着  这个节点的 所有 子树 根 位置的 索引。把 双亲 表示法 和 孩子 表示 方法 结合 起来 就是 第三种。

简单的 介绍 完了，下面 上代码：

源代码网盘路径：点击打开链接

// ParentTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <cstdlib>
#include "queue.h"
#include "linkList.h"
#include <cstring>
#include "stack.h"


#define TREE_INIT_SIZE 100//树的初识空间
#define TREE_ADD_SIZE  20 //当空间不足时，增加的空间
typedef char ElementType;

//树的双亲 孩子 表示法
struct PTreeNode
{
	ElementType data;
	int parentIndex;//父亲节点 在 数组中的 索引
	//比双亲表示法增加了 一个 指向 孩子的后继.
	LinkList childList;//指向子树的第一个根节点..
};

struct PTree
{
	PTreeNode * base;//节点的基址
	int rootIndex;//节点 在数组中的索引
	int len;//长度
	int size;//base 地址 空间的 大小
};

//初始化成一颗空树.
void treeInit(PTree  * tree){
	tree->base = NULL;
	tree->len = 0;
	tree->rootIndex = 0;
	tree->size = 0;//
}
//初始化 第 index 节点 孩子链表
void treeInitChildList(PTree  tree,int index){
	LinkList list;
	listInit(&list);
	tree.base[index].childList = list;
}


//创建树 
E_State treeCreate(PTree * tree){
	treeInit(tree);
	tree->base = (PTreeNode *) malloc(sizeof(PTreeNode) * TREE_INIT_SIZE);
	tree->size = TREE_INIT_SIZE;//一定要记得加...
	if (tree->base == NULL)
	{
		return E_State_Error;
	}
	char data = ' ';
	printf("------------层序创建树（输入根节点数据，#代表空树)-------------\n");
	scanf("%c%*c",&data);
	if (data != '#')
	{
		tree->base[0].data = data;
		tree->base[0].parentIndex = -1;//根节点 无 双亲..
		tree->rootIndex = 0;
		tree->len = 1;
		treeInitChildList(*tree,0);
		LinkQueue queue;
		queueInit(&queue);
		//将 数据 和 数据的 索引 入队
		qElementType qData;
		qData.data = data;
		qData.index = 0;
		enqueue(&queue,qData);
		while (!queueEmpty(queue))
		{
			qElementType father;
			dequeue(&queue,&father);
			printf("--------请输入%c节点的 所有 孩子节点（输入exit 表示创建完毕）-------\n",father.data);
			char childArray[100];
			scanf("%s",childArray);
			if (strcmp(childArray,"exit") == 0)
			{
				break;
			}
			char * p = childArray;
			while (*p != '\0')
			{
				if (tree->len >= tree->size)//空间不足了
				{
					int newSize = tree->size + TREE_INIT_SIZE;
					tree->base = (PTreeNode *) realloc(tree->base,newSize);
					if (tree->base == NULL)
					{
						return E_State_Error;
					}
					tree->size = newSize;
				}
				int index = tree->len;
				tree->base[index].data = *p;
				tree->base[index].parentIndex = father.index;
				tree->len++;
				treeInitChildList(*tree,index);
				//将节点 插入到 父亲的 childList 链表里
				listInsertTail(&(tree->base[father.index].childList),index);
				//将节点信息入队
				qData.data = *p;
				qData.index = index;
				enqueue(&queue,qData);
				p ++;
			}

		}
		queueDestory(&queue);
	}
	return E_State_Ok;
}

void treeClear(PTree * tree){
	//首先得释放 孩子链表
	for (int i = 0; i < tree->len; i++)
	{
		PTreeNode node = tree->base[i];
		listDestory(&node.childList);
	}
	free(tree->base);
	tree->base = NULL;
	tree->len = 0;
	tree->rootIndex = 0;
	tree->size = 0;
}

void treeDestory(PTree * tree){
	treeClear(tree);
}


void treeTraverse(PTree tree){
	printf("---------遍历 树---------------\n");
	for (int i = 0; i < tree.len; i++)
	{
		printf("%c\t",tree.base[i]);
	}
	printf("\n");
}

int treeLen(PTree tree){
	return tree.len;
}

bool treeIsEmpty(PTree tree){
	return tree.len == 0 ? true : false;
}

//获取 值 等于 data 节点的 索引
int treeGetDataIndex(PTree tree,ElementType data){
	for (int i = 0; i < tree.len; i++)
	{
		if (tree.base[i].data == data)
		{
			return i;
		}
	}
	printf("%c 节点不存在\n",data);
	return -1;//-1 表示没找到
}
//打印 值 等于 childData的 父节点
void treeGetFather(PTree tree,ElementType childData){
	int index = treeGetDataIndex(tree,childData);
	if (index != -1)
	{
		int fatherIndex = tree.base[index].parentIndex;//找父亲在数组中的 索引..
		if (fatherIndex != -1)
		{
			printf("%c 节点 的 父亲是 ：%c\n",childData,tree.base[fatherIndex].data);
		}
		else
		{
			printf("根节点无父亲\n");
		}
	}
}
//打印值 等于 fatherData 的 孩子节点
void treeGetAllChild(PTree tree,ElementType fatherData){
	int fatherIndex = treeGetDataIndex(tree,fatherData);
	if (fatherIndex != -1)
	{
		printf("%c孩子节点是：",fatherData);
		PTreeNode node = tree.base[fatherIndex];
		LinkNode * next = node.childList.head->next;//指向 孩子链表的 第一个节点
		while (next)
		{
			int childIndex = next->data;
			printf("%c\t",tree.base[childIndex].data);
			next = next->next;
		}
		printf("\n");
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	PTree tree;
	treeCreate(&tree);
	treeTraverse(tree);
	int len = treeLen(tree);
	char * isEmpty = treeIsEmpty(tree) ? "是" : "不是";
	treeGetFather(tree,'i');
	treeGetAllChild(tree,'b');
	treeDestory(&tree);
	return 0;
}

运行截图：