发送树和二叉树+1117三班

《发送树和二叉树+1117三班》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树与二叉树6.1树的基本概念和术语6.2二叉树6.3遍历二叉树6.4二叉树、树和森林6.5树的应用6.1树的基本概念和术语6.1.1树的定义树(tree)是由一个或多个结点组成的有限集合T。其中：(1)一个特定的结点称为该树的根(root)结点,而且有且仅有一个；(2)根结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，…，Tm，且其中每一个集合本身又是一棵树，称之为根的子树(subtree)。这是一个递归的定义，即在定义中又用到了树这个术语。它反应了树的固有特性。可以认为仅有一个根结点的树是最小树，树中结点较多时，每个结点都是某一棵子树的根。

2、在图6.1中是一棵由11个结点组成树T。其中A是根结点，其余结点分为三个互不相交的子集：T1={B，E，F}，T2={C，G}，T3={D，H，I，J，K}。T1，T2，T3都是树根A的子树，这三棵子树的根结点分别是B，C，D。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为三个互相交的子集T31={H}，T32={I，K}，T33={J}，而其中T31，T33可都认为是仅有一个根结点的子树。图6.1树T6.1.2树的常用术语树结构常常用到一些术语，如度、双亲、孩子、树深等。树的结点代表树中的一个数据元素，它带有数据信息，同时还带有若

3、干分支。结点的度是该结点的子树的个数。例如结点B有两棵子树，它的度是2。树的度是树中结点度的最大值。例如度为零的结点称为叶子或终结点，度不为零的结点称为非终端结点。图6.1中树T的度为3。结点E，F，G，H，K，J度为零，它们是叶子结点。某结点的各子树的根结点称为该结点的孩子，而该结点又称为孩子们的双亲结点。具有相同双亲的结点互称为兄弟。图6.1中根结点A有三棵子树，这三棵子树的根结点分别是B，C，D，因此说结点A是结点B，C，D的双亲，而结点B，C，D又都是结点A的孩子，B，C，D之间互为兄弟。一棵树上除根结点以外的其他结点称为根结点的子孙。对于树中某结点，从根结点

4、开始到该结点的双亲是该结点的祖先。结点的层次值从根算起，根的层次值为1，其余结点的层次值为双亲结点层次值加1。一棵树的深度是该树中结点最大层次值，例如图6.1中的树T的深度为4。结点A，B，E，K的层次值分别为1，2，3，4。6.1.3树的表示形式树的表示形式有多种，常见的三种形式是：(1)倒悬树法，如图6.1所示；(2)集合包含关系文氏图法，如图6.2(a)所示；(3)凹入法，如图6.2(b)所示。图6.2树结构的不同表示方法(a)文氏图法；(b)凹入法6.2二叉树6.2.1二叉树的定义二叉树(binarytree)是n(n≥0)个结点的有限集合。它或为空树(n=0

5、)，或为非空树。对于非空树有：(1)有一个特定的称之为根的结点。(2)除根结点以外的其余结点分为两个互不相交的称之为左子树和右子树的二叉树。这个定义是递归的。由于左、右子树也是二叉树，因此子树也可为空树。图6.3中展现了五种不同基本形态的二叉树。图6.3二叉树的五种基本形态其中(a)为空树，(b)为仅有一个结点的二叉树，(c)是仅有左子树而右子树为空的二叉树，(d)是仅有右子树而左子树为空的二叉树，(e)是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图6.3(c)与图6.3(d)就是两棵不同的二叉树。6.2.2二叉

6、树的重要性质性质1二叉树第i(i≥1)层上至多有2i-1个结点。证明：根据图6.4(a)可知，根结点在二叉树的第一层上，这层结点数最多为1个，即20个；显然第二层上最多有2个结点，即21个；…假设第i-1层的结点最多有2i-2个，且每个结点最多有两个孩子，那么第i层上结点最多有2*2i-2=2i-1个。性质1证明完毕。性质2深度为k(k≥1)的二叉树至多有2k-1个结点。证明：由性质(1)可知各层结点最多数目之和为：20+21+22+…..+2k-1；由二进制换算关系可知：20+21+22+…+2k-1=2k–1，因此二叉树树中结点的最大数目为2k-1。性质2证明完毕

7、。性质3在任意二叉树中，若叶子结点(即度为零的结点)个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，那么n0=n2+1。证明：设n代表二叉树结点的总数，那么n=n0+n1+n2(6.1)由于有n个结点的二叉树总边数为n-1条，于是得n-1=0*n0+1*n1+2*n2(6.2)将(6.1)式代入(6.2)式得n0=n2+1性质3证明完毕。现在介绍两种特殊形态的二叉树，它们是满二叉树和完全二叉树。深度为k并且含有2k-1个结点的二叉树称为满二叉树，如图6.4(a)所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图6.4(a