树和二叉树1(定义和性质)

1、6.1 树树的定的定义义和基本和基本概概念念6.2 二叉二叉树树6.3 遍遍历历二叉二叉树树6.4 树树和森林和森林6.5 哈夫曼哈夫曼树树及其及其应应用用6.1 树的定义和基本概念树的定义和基本概念 一、树的概念一、树的概念：是：是n个结点的有限集合。个结点的有限集合。 根结点根结点 m个互不相交的有限集：个互不相交的有限集： T1，T2，Tm 其中每一个集合本身又是一棵树，并且称其中每一个集合本身又是一棵树，并且称为根的为根的子树子树。 树的定义是递归的。树的定义是递归的。非空树非空树: A A B C D B C D E F G H E F G H I J I J 二、树的表示二、树的表

2、示(1) 结点连线结点连线。隐含：上方结点是下方结点的前驱。隐含：上方结点是下方结点的前驱。(2)二元组表示二元组表示 如上面的如上面的T2可表示为：可表示为：K=C,G,I,JR=, C GI J 关系关系r应满足以下关系：应满足以下关系：根结点没有前驱；根结点没有前驱；其余每个结点只有一个前驱结点其余每个结点只有一个前驱结点任何结点可以有多个后继任何结点可以有多个后继A( )T1T3T2树根(3) 广义表表示广义表表示B(E, F), C(G( I, J), D(H) A A B C D B C D E F G H E F G H I J I J 三、基本术语三、基本术语(1)树的结点树的

3、结点:包含一个数据元素包含一个数据元素及若干指向其子树的分支及若干指向其子树的分支(2)结点的度（结点的度（degree）：结点：结点拥有的子树数。拥有的子树数。(3)树的度树的度:树内各结点的度的最树内各结点的度的最大值。大值。 (4)根结点根结点：无前驱。：无前驱。(5)叶子（终端结点）叶子（终端结点）：度为零：度为零的结点。无后继。的结点。无后继。(6)分支结点（非终端结点）分支结点（非终端结点）：度不为零的结点。除根结点外度不为零的结点。除根结点外，分支结点也称，分支结点也称内部结点内部结点（一（一个前驱，多个后继）个前驱，多个后继） A B C D E F G H I J (8) 孩

4、子结点、双亲结点、和孩子结点、双亲结点、和兄弟结点：兄弟结点：(9) 堂兄弟：堂兄弟：(10)祖先：祖先：结点的祖先是从根结点的祖先是从根到该结点所经分支上的所有到该结点所经分支上的所有结点。结点。(11)子孙：子孙：以某结点为根的子以某结点为根的子树中的任一结点都称为该结树中的任一结点都称为该结点的子孙。点的子孙。(12)结点的层次：结点的层次：根为第一层根为第一层，根的孩子为第二层。，根的孩子为第二层。(13)树的深度（高度）树的深度（高度）：树中：树中结点的最大层次。结点的最大层次。 A B C D E F G H I J (14)(14)有序树及无序树有序树及无序树 B FE B E

5、FT1T2家族树、机构树家族树、机构树（15）森林）森林：M棵互不相交的树的集合。棵互不相交的树的集合。线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )树结构与线性结构的比较树结构与线性结构的比较6.2 二叉树二叉树 6.2.1 二叉树的定义和性质二叉树的定义和性质 6.2

6、.2 二叉树的存储结构二叉树的存储结构 6.2.3 二叉树的运算二叉树的运算一 、定义定义：二叉树是n(n0)个结点的有限集合。它或为空树(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。6.2.1 二叉树的定义及其性质二叉树的定义及其性质ABCDEFGHK根结点左子树右子树EF特点特点：每个结点至多只有两棵子树，子树有左：每个结点至多只有两棵子树，子树有左右之分，其次序不能任意颠倒，分别称为左右右之分，其次序不能任意颠倒，分别称为左右子树。子树。ab两棵不同的二叉树两棵不同的二叉树ab二

7、叉树的五种基本形态二叉树的五种基本形态 空二叉树空二叉树 仅有仅有根结点根结点 右子右子树为空树为空 左子左子树为空树为空左右子树左右子树均非空均非空二、特殊的二叉树二、特殊的二叉树（1）满二叉树）满二叉树423167891011121314155特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。深度为k k且含有2 -1个结点的二叉树k（2）完全二叉树）完全二叉树4231678910 11125 完全二叉树完全二叉树满二叉树是完全二叉树的特例满二叉树是完全二叉树的特例树中所含的 n n 个结点和满二叉树中编号编号为为 1 1 至至 n n 的结点的结点一一对应。42316789

8、1011121314155满二叉树满二叉树4231678910 11125 非完全二叉树非完全二叉树4231678910 11125 完全二叉树完全二叉树（3）理想平衡树）理想平衡树 在一棵二叉树中，若除最后一层外，其余层都是在一棵二叉树中，若除最后一层外，其余层都是满的，则称此树是理想平衡树。满的，则称此树是理想平衡树。 理想平衡树包括满二叉树和完全二叉树。但并不一理想平衡树包括满二叉树和完全二叉树。但并不一定是完全二叉树。定是完全二叉树。4231678910 11125 理想平衡树理想平衡树三、三、 二叉树的基本性质二叉树的基本性质 性质性质1:在二叉树的第在二叉树的第k层上至多有层上至多

9、有2k-1个结点个结点(k1) 用归纳法证明：用归纳法证明： (1)k=1时时, 2k-1=1，即只有一个根结点。，即只有一个根结点。 (2)设对设对1jk-1,命题成立，则可以证明命题成立，则可以证明j=k时时命题也成立。命题也成立。 由于第由于第k-1层上至多有层上至多有2k-2个结点个结点，由于二叉，由于二叉树中每个结点的度至多为树中每个结点的度至多为2，故第，故第k层上的结层上的结点数最多为点数最多为 2k-2 2= 2k-1。 性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1) k （第（第i层上的最大结点数）层上的最大结点数） i=1 k = 2i

10、-1 i=1 =( 1 + 2 + 22 + + 2k-1)=2k-1性质性质3：对任何一棵二叉树：对任何一棵二叉树T，如果其终端结点，如果其终端结点数为数为n0，度为，度为2的结点数为的结点数为n2，则有，则有n0=n2+1。证明：设度为证明：设度为1的结点数为的结点数为n1, 总结点数为总结点数为n，则有则有 n = n0 + n1 + n2设分支数为设分支数为B， n = B + 1（除根结点外，每一（除根结点外，每一个结点都有一个分支到达）又由于这些分支数个结点都有一个分支到达）又由于这些分支数是由度为是由度为1和度为和度为2的结点发出的，因此，的结点发出的，因此，B = n1 + 2

11、n2。 n0 + n1 + n2 = n1 + 2n2 + 1 n0 = n2 + 1 假设深度为k，由性质2，最大结点数为2k-1, 深度为k-1的最大结点数为2k-1-1。 2k-1-1 n 2k-1 或 2k-1 n 2k 2k-1 n+1 2k k-1 log2(n+1) klog2(n+1) k log2(n+1) +1 k = log2(n+1) 性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n+1) 或或 log2n + 1。k-1 log2 n 1, 则其双亲则其双亲parent(i)是结点是结点 i/2 (2)如果如果2in，则结点，

12、则结点 i 为叶子，否则其左孩子为叶子，否则其左孩子Lchild(i)是结点是结点2i。(3)如果如果2i+1n, 则结点则结点i无右孩子，否则其右无右孩子，否则其右孩子是结点孩子是结点2i+1。4231678910 11125 完全二叉树完全二叉树对于对于i=1,对于对于i1,可分两种情况讨可分两种情况讨论：论：证明证明(2),(3):对于对于i=1,左孩子是左孩子是2, 右孩子是右孩子是3。对于对于i1,可分两种情况讨论：可分两种情况讨论：第一种情况第一种情况：设第：设第j层的第层的第1个结点的编号为个结点的编号为i(i=2j-1),则其左孩子必为第则其左孩子必为第j+1层的第层的第1个结

13、点，个结点，其编号为其编号为 2j =2* 2j-1 =2i。若若2in，则，则i无左孩子。右孩子编号为无左孩子。右孩子编号为2i+1，若若2i+1n，则无右孩子。，则无右孩子。第二种情况：第二种情况：假设第假设第j层上某个结点的编号层上某个结点的编号为为i, 且且2i+1n，则其左孩子为，则其左孩子为2i，右孩子为，右孩子为2i+1。则编号为则编号为i+1的结点是编号为的结点是编号为i的结点的右兄的结点的右兄弟或堂兄弟，若它有左孩子，其编号必为弟或堂兄弟，若它有左孩子，其编号必为2i+2=2(i+1),若它有右孩子，其编号必为若它有右孩子，其编号必为2i+3=2(i+1)+1。例例1：具有：

14、具有n个结点的满二叉树，其叶结点的个结点的满二叉树，其叶结点的个数为多少？个数为多少？n = 2k-1n0 = 2k-1n0 = (n+1)/2例例2：设高为：设高为h的二叉树只有度为的二叉树只有度为0和和2的结点的结点，则此类二叉树的结点数至少为？至多为？，则此类二叉树的结点数至少为？至多为？四、树与二叉树的区别四、树与二叉树的区别A树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。B 无明确指出，树没有左、右子树之分，二叉树有明确的左、无明确指出，树没有左、右子树之分，二叉树有明确的左、右子树之分。右子树之分。 二叉树二叉树树树6.2.2

15、二叉树的存储结构二叉树的存储结构 (1) 顺序存储结构顺序存储结构 用一组连续的存储单元存放二叉树的数据元素。用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。结点在数组中的相对位置蕴含着结点之间的关系。#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE+1; / 1号单元存储根结点SqBiTree bt;完全二叉树完全二叉树ABCDEFGHIJKLA13LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12若父结点在数组中若父结点在

16、数组中i i下标处，其左孩子在下标处，其左孩子在2 2* *i i，右孩子在，右孩子在2 2* *i+1i+1ABCDEFG 表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树一般二叉树1 2 3 4 5 6 7 8 9 10 11若父结点在数组中若父结点在数组中i i下标处，其左孩子在下标处，其左孩子在2 2* *i i，右孩子在，右孩子在2 2* *i+1i+1一般二叉树必须按完全二叉树的形式存储，一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。将造成存储的浪费。v一个深度为一个深度为H且只有且只有H个结点的右单支树需个结点的右单支树需要要2h-1个结点存储空间个结点存储空间根据结点结构不同根据结点结构不同 二叉链表二叉链表 三叉链表三叉链表(2) 链式存储结构链式存储结构ADEBCF rootlchild data rchild结点结构结点结构: :1. 1. 二叉链表二叉链表typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言