树的存储结构

一、双亲表示法:

       树中每个结点都有唯一一个父结点(根结点无),因此可定义一个包含两个成员的结构体:其一记录结点值,另一记录父节点(值或编号……),以此可建立一棵树:

      

#define SIZE 20
type struct{
       char data;
       int par;
}node;
type struct{
       node treelist[SIZE];
       node root,num;//root记录树根,num记录结点数
}tree;


树的存储结构树的存储结构

data parent
A -1
B 0
C 0
D 0
E 1
F 1
G 3
H 3
I 6
J 6
K 6

二、孩子表示法:

      1.指针方式的孩子表示法:每个结点包括改结点值和指向其孩子结点的指针数组,可见图如下:

树的存储结构

     2.数组方式的孩子表示方法:

data child[0] child[1] child[2]
A 1 2 3
B 4 5 -1
C -1 -1 -1
D 6 7 -1
E -1 -1 -1
F -1 -1 -1
G 8 9 10
H -1 -1 -1
I -1 -1 -1
J -1 -1 -1
K -1 -1 -1

    3.链表方式表示法:

树的存储结构

三、孩子兄弟表示法:

      每个结点设置节点值、指向第一个子女的指针、指向右兄弟的指针域:

树的存储结构

 

说明:本文大部分内容来自《数据结构(C语言版)》(李云清、杨庆红、揭安全编著),写此文只为备忘,转载请留此说明,谢谢。

另外可参考一下链接一起看:树的储存方式

;