Skip to main content
 首页 » 编程设计

java算法之二叉树的物理结构(存储结构)

2022年07月18日49txw1958

来源:  https://blog.csdn.net/qq_41587740/article/details/104215365

双亲表示法:

原理:
在这里插入图片描述在这里插入图片描述
   R为头节点,所以parent=-1;
   ABC的双亲节点数组下标为0,所以parent=0;
   DE的双亲节点数组下标为1,所以parent=1;

代码实现:

typedef struct{ 
	int data; //数据域 int parent; //伪指针 }PTNode; //节点类型 typedef struct{ PTNode nodes[MAX_TREE_SIZE]; //节点数据信息 int n; // 节点个数 }PTree; //树的类型 

孩子表示法:

原理:
在这里插入图片描述在这里插入图片描述
代码实现:

typedef struct CNode{ 
	int child; //孩子节点的下标 struct CNode *next; //下一个孩子节点的指针 }CNode; //单链表节点类型 typedef struct{ int data; //节点数据 struct CNode *firstchild; //孩子节点的第一个节点,即单链表的头节点 }PNode; //树的节点类型 typedef struct{ PNode nodes[MAX_TREE_SIZE]; //所有节点数据 int n; //节点个数 }CTree; //树的类型 

孩子兄弟表示法:

原理:
在这里插入图片描述在这里插入图片描述
代码实现:

typedef struct CSNode{ 
	int data; struct CSNode *fristchild,*nextsibling; }CSNode,*CSTree; 

三种存储结构的对比:

在这里插入图片描述


本文参考链接:https://www.cnblogs.com/maohuidong/p/14216720.html