二叉树双亲表示法

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

#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;
}