如上图B、C、H、I...等节点为叶节点

双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点

堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点

节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先

子孙以某节点为根的子树中任一节点都称为该节点的子孙。

如上图所有节点都是A的子孙

1.2

树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间

的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法

typedef

满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。

也就是

完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。

对于深度为K

的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对

完全二叉树前n-1层都是满的最后一层可以不满但是从左到右是连续的结点范围[2^(h-1),

2^h-1]

若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1.

对任何一棵二叉树,

对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对

若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点

若2i1n否则无左孩子

普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。

而完全二叉树更适合使用顺序结

构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统

虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。

3.2

一个集合所有元素按完全二叉树的顺序存储方式存储在一个一维数组中堆中某个节点的值总是小于或等于其父节点的值是大堆堆中某个节点的值总是大于或等于其父节点的值是小堆。

3.3

(Datatype*)malloc(sizeof(Datatype)

4);if

(Datatype*)malloc(sizeof(Datatype)

n);if

sizeof(Datatype)*php-capacity*2);if

(tmp

{assert(php);assert(!PHEmpty(php));//和最后一个数据交换Swap(php-a[0],

php-a[php-size

1]);php-size--;AdjustDown(php-a,

php-size