5.3二叉树的存储结构

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构与算法,For,软件学院,09,级本科生,2010-2011,秋,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,5,二叉树,5.1,二叉树的概念,5.2,二叉树的周游,5.3,二叉树的存储结构,5.4,二叉搜索树,5.5,堆与优先队列,5.6,Huffman,树及其应用,5.7,二叉树知识点总结,主要内容,5.3,二叉树的存储结构,二叉树的存储结构：,链式存储结构,顺序存储结构,5.3.1,二叉树的链式存储结构,所谓链式存储方式，是指二叉树的各结点随机的存储在,内存空间中，结点之间的关系用指针表示。,二叉树的链表的结点包含三个域：数据域和左、右指针域。用,info,域存储结点的数据元素，另外再设置两个指针域,left,和,right,，分别指向结点的左子结点和右子结点,当结点的某个子结点为空时，相应的指针为空指针。其结点结构如图,5.7(a),所示。有时候为了便于查找二叉树中某个结点的父结点，还可以在结点结构中加入一个指向其父结点的指针域，如图,5.7(b),所示,图,5.7,二叉树结点的存储结构,5.3.1,二叉树的链式存储结构,利用这两种结点结构所得到的二叉树的存储结构分别称为,二叉链表,（也称“,left-right,存储法”）和,三叉链表,在使用二叉链表存储的二叉树中，如果找某个结点的父结点，那么需要从根结点出发依次巡查,在三叉链表表示的二叉树中只需要顺着,parent,指针就能直接找到该结点的父结点,图 二叉链存储结构的二叉树,root,A,B,C,D,E,F,G,root,A,B,C,D,E,F,G,(a),不带头结点的二叉树,(b),带头结点的二叉树,二叉链存储结构的二叉树,二叉链存储结构的二叉树,A,B,C,D,E,F,G,A,B,C,D,E,F,G,在,n,个结点的二叉链表中，有,n+1,个空指针域,。,三叉链存储结构的二叉树,A,B,C,D,E,F,G,A,B,C,D,E,F,G,二叉树的顺序存储结构,二叉树的顺序存储,是指按照一定次序，用一组地址连续的存储单元存储二叉树上的各个结点元素。,完全二叉树的顺序表示法,：,对于一棵具有,n,个结点的完全二叉树，可以从根结点起自上而下，从左至右地把所有的结点编号，得到一个足以反映整个二叉树结构的线性序列。线性序列里存储的结点就是按照层次周游二叉树得到的排列。,复习：完全二叉树的主要性质,7,性质,7.,对于具有,n,个结点的完全二叉树，结点按层次由左到右编号，则对任一结点,i,（,0 i n - 1,）有,（,1,）如果,i = 0,，则结点,i,是二叉树的根结点；若,i,0,，则其父结点编号是,(i - 1)/2,。,（,2,）当,2i + 1 n - 1,时，结点,i,的左子结点是,2i + 1,，否则结点,i,没有左子结点。,当,2i + 2 n - 1,时，结点,i,的右子结点是,2i + 2,，否则结点,i,没有右子结点。,（,3,）当,i,为偶数且,0 i n,时，结点,i,的左兄弟是结点,i - 1,，否则结点,i,没有左兄弟。,当,i,为奇数且,i+1 n,时，结点,i,的右兄弟是结点,i + 1,，否则结点,i,没有右兄弟。,B,A,C,E,D,F,G,H,I,J,K,L,M,N,O,B,A,C,E,D,F,G,H,I,J,A,B,C,D,O,N,M,L,K,J,I,H,G,F,E,1,2,0,4,3,5,7,6,11,8,10,9,12,13,14,A,B,C,D,J,I,H,G,F,E,1,2,0,4,3,5,7,6,8,9,完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到。,顺序存储结构,对于一般的非完全二叉树,显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。,B,A,C,D,E,G,F,B,A,C,D,E,G,F,(a),一般二叉树,(b),完全二叉树形态,(c),在数组中的存储形式,A,B,C,G,F,E,D,1,2,0,4,3,5,7,6,11,8,10,9,12,数组,下标,高度为,4,，有,7,个结点的一般二叉树的顺序存储,a,b,c,d,e,f,g,g,f,0,0,0,0,e,d,c,b,a,1 2 3 4 5 6 7 8 9 10 11,浪费,4,个,高度为,4,，只有,4,个右孩子的二叉树的顺序存储,0,0,0,0,4,0,0,0,3,0,0,0,2,0,1,1,2,3,4,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,浪费,11,个,顺序存储结构适用于满二叉树和完全二叉树的存储。,