二叉树双亲表示法

前面我们介绍过二叉树的单向表示和双向表示发，分别是借用了几个指针来实现。双亲表示法则是用了一个非常详细的结构体描述了一个节点，然后将节点串联到另外一个结构体中（这个结构体包含一个数组），具体的代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/////////// 双亲表示法 ///////////
typedef struct tag_BPTNode
{
	//节点数据
	char data;
	//指向父节点的变量(数组下标)
	int parentPosition;
	//左右孩子标志域
	char LRTag;
}BPTNode;

//定义树的数据结构
typedef struct tag_BPTree
{
	//一个代表整个树的数组
	BPTNode nodes[100];
	//树中已经存入节点的个数
	int num_node;
	//根节点的位置(***注意此域存储的是父亲节点在数组中的下标***)
	int root;
}BPTree;


int main()
{
	//定义一个变量, 最多可容纳100个节点
	BPTree tree;
	//初始化
	memset(&tree, 0, sizeof(BPTNode));
	tree.root = 0;	//0号位置元素为根节点
	//根节点
	tree.nodes[0].data = 'a';
	tree.num_node++;	//节点数加1
	//B
	tree.nodes[1].data = 'b';
	tree.nodes[1].parentPosition = 0;	//父亲是a
	tree.nodes[1].LRTag = 1;	//a的左孩子
	tree.num_node++;	//节点数加1
	//c
	tree.nodes[2].data = 'c';
	tree.nodes[2].parentPosition = 0;	//父亲是a
	tree.nodes[2].LRTag = 2;	//a的右孩子
	tree.num_node++;	//节点数加1
	//d
	tree.nodes[3].data = 'd';
	tree.nodes[3].parentPosition = 1;	//父亲是b
	tree.nodes[3].LRTag = 1;	//b的左孩子
	tree.num_node++;	//节点数加1
	//e
	tree.nodes[4].data = 'e';
	tree.nodes[4].parentPosition = 1;	//父亲是b
	tree.nodes[4].LRTag = 2;	//b的右孩子
	tree.num_node++;	//节点数加1
	//f
	tree.nodes[5].data = 'f';
	tree.nodes[5].parentPosition = 2;	//父亲是c
	tree.nodes[5].LRTag = 1;	//c的左孩子
	tree.num_node++;	//节点数加1
	//g
	tree.nodes[6].data = 'g';
	tree.nodes[6].parentPosition = 2;	//父亲是c
	tree.nodes[6].LRTag = 2;	//a的左孩子
	tree.num_node++;	//节点数加1

	return 0;
}