Broot(t) (4)leftchild(t) (S)rightchild(t) (6)locate(t,x) (7)parent(t x) (8)isempty(t) (9)depth(t) 10)numofnode(t) (11)addchild(t,x, tl,b) 12)deletechild(t,x, b) (13)setnull(t) (14)isequal(t1, t2) (15)preorder(t) (16)inorder(t) (17)postorder(t) 18)transform(t1, t2) 3 ADT bintree
(3)root(t) (4)leftchild(t) (5)rightchild(t) (6)locate(t,x) (7)parent(t,x) (8)isempty(t) (9)depth(t) (10)numofnode(t) (11)addchild(t,x,t1,b) (12)deletechild(t,x,b) (13)setnull(t) (14)isequal(t1,t2) (15)preorder(t) (16)inorder(t) (17)postorder(t) (18)transform(t1,t2) } ADT bintree
7.3二叉树的存储结构 二叉树常用的存储结构有两种:顺序存储结构 和链式存储结构。 7.3顺序存储结构 顺序存储结构是使用一组连续的空间存储二叉树 的数据元素和数据元素之间的关系。因此必须将二叉 树中所有的结点排成一个适当的线性序列,在这个线 性序列中应采用有效的方式体现结点之间的逻辑关系
7.3 二叉树的存储结构 二叉树常用的存储结构有两种：顺序存储结构 和链式存储结构。 7.3.1 顺序存储结构 顺序存储结构是使用一组连续的空间存储二叉树 的数据元素和数据元素之间的关系。因此必须将二叉 树中所有的结点排成一个适当的线性序列，在这个线 性序列中应采用有效的方式体现结点之间的逻辑关系
1、完全二叉树的顺序存储 对于一棵具有n个结点的完全二叉树,我们可以 按从上到下、同一层次按从左到右的顺序依次将结点 存入一个一维数组中。根据上述性质4,无须附加任何 其它信息就能根据每个结点的下标找到它的子女结点 和双亲结点。 a 01234567 a b c d e f (a)完全二叉树 (b)完全二叉树的顺序存储
1 、完全二叉树的顺序存储 对于一棵具有n个结点的完全二叉树，我们可以 按从上到下、同一层次按从左到右的顺序依次将结点 存入一个一维数组中。根据上述性质4，无须附加任何 其它信息就能根据每个结点的下标找到它的子女结点 和双亲结点。 a b d e c f a b c d e f 0 1 2 3 4 5 6 7 (a) 完全二叉树 (b)完全二叉树的顺序存储
2一般二叉树的顺序存储 由于二叉树中每个结点最多只有两个子女,于是 存储一个结点时,除了包含结点本身的属性值外,另 外增加两个域,分别用来指向该结点的两个子女在数 组中的下标。 Child data 3-b-4 d d rchild 2 root=0 n=7 (a)一棵二叉树 (b)二叉树的顺序存储
2 一般二叉树的顺序存储 由于二叉树中每个结点最多只有两个子女，于是 存储一个结点时，除了包含结点本身的属性值外，另 外增加两个域，分别用来指向该结点的两个子女在数 组中的下标。 a b d c f g e (a) 一棵二叉树 (b) 二叉树的顺序存储 1 3 -1 -1 5 -1 -1 a b c d e f g 2 4 -1 -1 6 -1 -1 0 1 2 3 4 5 6 lchild data rchild root=0 n=7
一般二叉树顺序存储数据结构的定义如下: #define maXsize 20 typedef char datatype;/结点值的类型*/ typedef struct datatype data int child rchild: node;/二叉树结点的类型 node tree [MAXsIze] intn;/树中实际所含结点的个数* int root/*存放根结点的下标*
一般二叉树顺序存储数据结构的定义如下： #define MAXSIZE 20 typedef char datatype; /*结点值的类型*/ typedef struct { datatype data; int lchild,rchild; } node; /*二叉树结点的类型*/ node tree[MAXSIZE]; int n; /*树中实际所含结点的个数*/ int root; /*存放根结点的下标*/