首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


5. 如果一棵树有 n1 个度数为 1 的结点,n2 个度数为 2 的结点,?,nm 个度数为 m 的结点,则终端结点数 n0= n2+n3+?+nm+1。 二、 二叉树的基本性质 二叉树是另外一种树型结构,其特点是每个结点至多两棵子树,并且子树有左右之分,不能随意颠倒顺序。 二叉树有如下基本性质: 1. 二叉树中第 i 层至多有 个结点(i≥1)。 。 ,度为 2 的结点数为 ,则 。

2. 在深度为 k 的二叉树中结点总数最多为

3. 对任意一棵二叉树 T,如果其终端结点数为

4. 对任何一棵有 n 个结点的完全二叉树或满二叉树中编号为 i 的结点(1≤i≤n,n≥1)有: (1) n/2」,即 2i≤n,则编号为 i 的结点为分支结点,否则为终端结点?若 i≤ (2) 若 n 为奇数,则每个分支结点都既有左孩子,也有右孩子;若 n 为偶数,则编号最大的分支结点(编 号为 n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有。 (3) 若编号为 i 的结点有左孩子,则左孩子结点的编号为 2i;若编号为 i 的结点有右孩子,则右孩子结 点的编号为 2i+1。 (4) i/2」,换句话说,当 i 为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子,当 i 为奇数 时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子。?除树根结点外,若一个结点的编号为 i,则 它的双亲结点的编号为 (5) 具有 n(n>og 2 n」+1。? 或 ?0)个结点的完全二叉树的深度为「log 2(n+1)

四、 二叉树的存储结构及线索二叉树 1. 顺序存储结构 采用顺序存储结构存储一棵二叉树时,必须首先对该树中每个结点进行编号,树中各结点的编号应与等深 度的满二叉树中对应位置上结点的编号相同,然后以各结点的编号为下标,将各结点的值存储到一维数组 的对应下标单元中。如图 6-2 所示。

存储图 6-2 中实线部分所示二叉树,则存储结构示意图如图 6-3 所示。 1 9 A B C D E F G H 图 6-3 二叉树顺序存储示意图 10 11 2 3 4 5 6 7 8

显然 4、8、9 存储分量被浪费掉。特别地,当二叉树是一单支树时(即树中无度为 2 的结点),则采用顺 序存储结构存储有 n 个结点的二叉树需要 2k-1 个存储分量。空间浪费十分巨大。所以,通常采用链式存储 结构存储二叉树。 2. 链式存储结构 根据二叉树的特点,每个结点有一个双亲(根结点除外)和至多两个称为左、右孩子的结点,因此可设计 第个结点的结构如图 6-4。

lchild Data rchild lchild data parent rchild (a)不带父结点指针的 的 二叉树链式存储结构 构 图 6-4 二叉树链式存储结构示意图 二叉树链式存储结 (b)带父结点指针

其中 lchild 为指向结点左孩子的指针,rchild 为指向结点右孩子的指针,parent 为指向结点双亲的指针, data 为数据域,不同的运算可选择不同的存储结构。图 6-2 对应的链式存储结构示意图如 6-5 所示。

(a)不带父指针二叉树链 式存储结构 图 6-5 二叉树链式存储结构示意图

(b)带父指针二叉树链 式存储结构

3. 线索二叉树 在二叉树中按某种遍历顺序,求某给定结点的前驱或后继较难,必须对二叉树进行遍历,这将浪费大量的 运算时间。由于在二叉链表表示的二叉树中大量的终端结点的左右指针域都为空,浪费较大,将这些域用

来指向结点的前驱或后继,就形成了线索二叉树。将二叉树转化为线索二叉树的过程,叫线索化。 4. 二叉树的运算 根据对二叉树的定义以及对二叉树采用链式存储结构,有关二叉树的运算如下 (1) (2) (3) (4) (5) (6) (7) (8) (9) InitBiTree(&T) 构造空二叉树 T。

CreateBiTree(&T,definition) 按 definition 构造二叉树 T。 ClearBiTree(&T) 将二叉树 T 清为空树。 BiTreeEmpty(T) 判定二叉树 T 是否为空二叉树。 BiTreeDepth(T) 求二叉树 T 的深度。 Root(T) 取二叉树 T 的根。 Parent(T,e):求二叉树 T 中结点 e 的双亲结点。 LeftChild(T,e):求二叉树 T 中结点 e 的左孩子结点。若 e 无左孩子,则返回“空”。 RightChild(T,e):求二叉树 T 中结点 e 的右孩子结点。若 e 无右孩子,则返回“空”。

(10) DeleteChild(T,p,LR):根据 LR 为 0 或 1,删除二叉树 T 中 p 所指结点的左或右子树。 (11) PreOrderTraverse(T,Visit()):先序遍历二叉树 T (12) InOrderTraverse(T,Visit()):中序遍历二叉树 T (13) PostOrderTraverse(T,Visit()):中序遍历二叉树 T (14) LevelOrderTraverse(T,Visit()):层序遍历二叉树 T 二叉树的运算较多,我们在将第二节实验中讨论有关二叉树运算的算法。其它运算的算法及 C 语言源程序 由读者自行设计,并上机调试。 五、 树的存储结构及运算 1. 树的存储结构 (1) 定长结点的多重链表 (2) 取树的度数作为每个结点的指针域数。由于树中可能很多结点的度都小于甚至有的远远小于树的度, 这些结点的部分指针域为空,造成存储空间的极大浪费,存储密度较小。 (3) 不定长结点的多重链表 (4) 按每个结点的度数来确定指针域数,另加一个度数域。其存储密度较定长结点多重链表有很大提高, 但运算和操作不方便。 (5) 二叉链表表示法(又称子女兄弟表示法) (6) 每个结点均设两个指针域,第一个指针域指向该结点的最左孩子结点,第二个指针域指向该结点的 右兄弟。利用这种存储结构便于实现各种树的运算,

2. 树的运算 根据对树的定义以及对树采用二叉链表存储结构,有关树的运算如下: (1) (2) (3) (4) (5) (6) (7) (8) (9) InitBiTree(&T) 构造一棵空树 T DestroyBiTree(&T) 销毁树 T CreateBiTree(&T,definition) 按 definition 构造树 T ClearBiTree(&T) 将树 T 清为空树 TreeEmpty(T) 判定 T 是否为空树 TreeDepth(T) 求树 T 的深度 Root(T) 取树 T 的根。若 T 为空树,则返回“空” Parent(T,cur_e) 取树 T 中结点 cur_e 的双亲结点 LeftChild(T,cur_e) 取树 T 中结点 cur_e 的最左孩子,无,则返回“空”

(10) RightSibling(T,cur_e) 取树 T 中结点 cur_e 的右兄弟,无,则返回“空” (11) InsertChild(&T,&p,i,c) 在树 T 中插入 c 为 p 指结点的第 i 棵子树 (12) DeleteChild(&T,&p,i) 删除树 T 中 p 指结点的第 i 棵子树 (13) TraverseTree(T,Visit()) 按某种次序访问树 T 的每个结点一次且仅一次 六、 赫夫曼树 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称为路径长度。 树的路径长度是指从树根到每一结点的路径长度之和;树的带权路径长度是指树中所有终端结点的带权路 径长度之和,记为 为 wi,则其中 。给定一组权值{w1,w2,??,wn},构造一棵有 n 个叶结点的二叉树,每个叶结点的权

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐