大连理工大学数据结构课件二叉树的概念-储存

数据结构与算法3.2二叉树主要内容•二叉树的概念、性质•二叉树的存储结构•二叉树的遍历•线索二叉树•二叉搜索树•平衡二叉树•堆与优先队列•Huffman树及其应用•二叉树的定义及基本术语•满二叉树、完全二叉树、扩充二叉树•二叉树的主要性质二叉树的概念、性质二叉树•二叉树的定义二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。ABCDEIJGH根结点左子树右子树二叉树•基本特征:•①每个结点最多只有两棵子树（不存在度大于2的结点）•②左子树和右子树次序不能颠倒。下面是两棵不同的树:BACEDFGBACEDFG二叉树•基本形态AABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空问：具有3个结点的二叉树可能有几种不同形态？有5种二叉树一般的树有几种？满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。BACEDFGHIJKLMNO满二叉树特点•高度为k且有2k-1个结点的二叉树。–每一层上的结点数都是最大结点数；–所有的分支结点的度数都为2；–叶子结点都在同一层次上。123114589121367101415完全二叉树如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。（只有最下两层结点可以度小于2）BACEDFGHIJ完全二叉树特点•叶子结点只可能在层次最大的两层上出现；•前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。123114589126710判断是否为完全二叉树1234567123456思考：满二叉树与完全二叉树的关系？扩充二叉树•当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶–对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶–对于原来二叉树的树叶，在它下面增加两个空树叶扩充二叉树63124971058扩充二叉树•外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和•内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和•E和I两个量之间的关系为E=I+2n（证明见课本）扩充二叉树63124971058例如，在图5.3这个有10个内部结点的扩充二叉树里E=3+4+4+3+4+4+3+4+4+3+3=39I=0+1+2+3+2+3+1+2+3+2=19E和I两个量之间的关系为E=I+2n。二叉树的主要性质•任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为二叉树中度为1的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即n=n0+n1+n2(3.1)除根结点外，其余结点都有一条边进入，设边数为e，有n=e+1。由于这些边是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得n=e+1=n1+2n2+1(3.2)由公式3.1和3.2得n0+n1+n2=n1+2n2+1，即n0=n2+1二叉树的主要性质•在二叉树的第i层上至多有2i个结点(根为第0层，i≥0)。•高度为h(深度为h-1)的二叉树至多有2h-1个结点。•非空满二叉树树叶数等于其分支结点数加1。•有n个结点（n0）的完全二叉树的高度为log2(n+1)二叉树性质•对完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数)有：ABCDEHIJKFG1234567891011完全二叉树（1）若i=1,则结点i是二叉树的根，无双亲。（2）若i1,则它的双亲结点的编号为i/2。当i为偶数时,其双亲结点的编号为i/2,它是左孩子结点,当i为奇数时,其双亲结点的编号为（i-1）/2,它是右孩子结点。二叉树性质ABCDEHIJKFG1234567891011完全二叉树(3)若编号为i的结点有左孩子结点,则左孩子结点的编号为2i；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+1)。二叉树性质ABCDEHIJKFG1234567891011完全二叉树(4)若n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点。二叉树性质ABCDEHIJKFG1234567891011完全二叉树二叉树的存储结构•顺序存储结构•链式存储结构BACEDFGHIJKLMNOBACEDFGHIJABCDONMLKJIHGFE12043576118109121314ABCDJIHGFE1204357689完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到。顺序存储结构对于一般的非完全二叉树：增加空结点，以便顺序存储。BACDEGFBACDEGF(a)一般二叉树(b)完全二叉树形态(c)在数组中的存储形式ABC∧G∧∧F∧∧∧ED1204357611810912数组下标高度为4，有7个结点的一般二叉树的顺序存储abcdefggf0000edcba1234567891011浪费4个高度为4，只有4个右孩子的二叉树的顺序存储0000400030002011234123456789101112131415浪费11个•顺序存储结构适用于满二叉树和完全二叉树的存储。二叉树的链式存储结构•链式存储方式，是指二叉树的各结点随机的存储在内存空间中，结点之间的关系用指针表示。•二叉树的链表的结点包含三个域：数据域和左、右指针域。leftChilddatarightChild二叉链存储结构的二叉树ABCDEFGABCDEFG^^^^^^^^在n个结点的二叉链表中，有n+1个空指针域。二叉树的链式存储结构•三叉链表:•在使用二叉链表存储的二叉树中，如果找某个结点的父结点，那么需要从根结点出发依次巡查•在三叉链表表示的二叉树中只需要顺着parent指针就能直接找到该结点的父结点leftChilddatarightChildparent三叉链存储结构的二叉树ABCDEFG^^^^^^^^^ABCDEFG