树结构用什么存储结构

㈠ 二叉树的两种物理结构是什么

答：二叉树就物理结构来分可以分成：顺序存储结构和链式存储结构。
（1）顺序存储结构：
顺序存储结构，顾名思义就是二叉树的数据元素存放在一组连续的存储单元中。其主要有一下几个特点：
①逻辑上相邻的两个元素在物理位置上也是相邻的；
②操作删除和插入的时候，需要整体移动元素；
③需要预先分配空间，不能动态增长；
（2）链式存储结构：
链式存储结构中二叉树的每个结点至少包含三个域：数据域、左指针域和右指针域。其二叉树是通过指针实现，链式存储结构有以下几个特点：
①逻辑上相邻的两个元素在物理位置上不一定是相邻的；
②操作删除和插入的时候，不需要整体移动元素；只需要修改相应的指针即可；
③不需要预先分配空间；
④存储指针本身会消耗一定的存储的空间；

㈡ 树 - 二叉树 - 二叉树的存储结构（二）

链式存储结构

结点的结构

二叉树的每个结点最多有两个孩子 用链接方式存储二叉树时 每个结点除了存储结点本身的数据外 还应设置两个指针域

lchild和rchild 分别指向该结点的左孩子和右孩子 结点的结构为

结点的类型说明

typedef char DataType; //用户可根据具体应用定义DataType的实际类型

typedef struct node{

DataType data;

Struct node *lchild *rchild; //左右孩子指针

}BinTNode; //结点类型

typedef BinTNode *BinTree;//BinTree为指向BinTNode类型结点的指针类型

二叉链表(二叉树的常用链式存储结构)

在一棵二叉树中 所有类型为BinTNode的结点 再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root 就构

成了二叉树的链式存储结构 并将其称为二叉链表

【例】下面左图所示二叉树的二叉链表如下面中图所示

注意

① 一个二叉链表由根指针root惟一确定 若二叉树为空 则root=NULL;若结点的某个孩子不存在 则相应的指针为空

② 具有n个结点的二叉链表中 共有 n个指针域 其中只有n 个用来指示结点的左 右孩子 其余的n+ 个指针域为空

带双亲指针的二叉链表

经常要在二叉树中寻找某结点的双亲时 可在每个结点上再加一个指向其双亲的指针parent 形成一个带双亲指针的二叉链表

【例】上面右图是上面左图所示的二叉树的带双亲指针的二叉链表

注意

二叉树存储方法的选择 主要依赖于所要实施的各种运算的频度

㈢ 树的存储结构

树的存储结构与遍历

树的存储结构主要有三种方式：双亲表示法、孩子表示法和孩子兄弟表示法。

1. 双亲表示法通过数组结构存储，如PTree类型，每个结点包含数据和指向双亲的索引。例如，MAX-TREE-SIZE定义了最大结点数，每个结点如PTNode所示。

2. 孩子表示法通过链表结构存储，如CTree类型，每个结点包含指向孩子和下一个兄弟的指针。双亲与孩子链表头指针结合，如CTBox结构。

3. 孩子兄弟表示法，每个结点有firstchild和nextsibling，如CSNode和CSTree，用于表示二叉树或二叉链表。

对于树的遍历，先根序和后根序是两种基本方法，森林的遍历则是基于树的遍历，包括先序遍历和中序遍历。

森林与二叉树之间的转换有自然转换法，如将森林转换为二叉树时，连接兄弟节点并调整连线方向，反之，将二叉树转换为森林则需要连接相关节点并去掉多余的连线。