前面我们介绍过二叉树的单向表示和双向表示发,分别是借用了几个指针来实现。双亲表示法则是用了一个非常详细的结构体描述了一个节点,然后将节点串联到另外一个结构体中(这个结构体包含一个数组),具体的代码如下:
#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; }