【数据结构】树

《【数据结构】树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树(6学时)树二叉树树和森林哈夫曼树及应用6.1树树形结构是一类重要的非线性结构，树形结构是结点之间有分支、分层关系的结构。树的定义：树是n(n≥0)个结点的有限集。它满足以下两个条件：（1）有且仅有一个特定的称为根的结点。（2）其余的结点可分为m个互不相交的有限集合T1,T2,…,Tm，其中，每个集合又都是一棵树（子树）。树的表示6.1树结点的度：一个结点的子树个数称为该结点的度。树的度：一棵树中结点度的最大值。叶子（终端结点）：度为0的结点。分支结点（非终端结点）：度不为0的结点。内部结点：除根结点之外的分支结点。孩子：树中某个结点的子树的根称为个结点的孩子。双亲：该结点则为孩子

2、的双亲。兄弟：同一个双亲的孩子。路径：若树中存在一个结点序列k1,k2,…,kj，使得ki是ki+1的双亲(1≤i

3、（4）求孩子结点函数。（5）求右兄弟函数。（6）建树函数。（7）插入子树操作。（8）删除子树操作。（9）遍历操作。（10）清除结构操作。6.2二叉树概念性质存储结构遍历线索化6.2二叉树概念定义：二叉树是个结点的有限集，它或者是空集，或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。二叉树的五种基本形态6.2二叉树二叉树的性质1、二叉树第i层上的结点数目最多为2i-1(i≥0)。归纳法证明：归纳基础：i=1时，有2i-1=20=1。归纳假设：假设对所有的j(1≤j

4、上至多有2i-2个结点，由于二叉树的每个结点至多有两个孩子，故第i层上的结点至多是第i层上的最大结点数的2倍，即j=i时该层上至多有2*2i-2=2i-1个结点，故命题成立。6.2二叉树2、深度为k的二叉树至多有2k-1个结点。证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时，其树中结点数最多。因此，利用性质1可得，深度为的二叉树中至多含有的结点数为：20+21+…+2k-1=2k-1故命题正确。3、在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。证明：因为二叉树中所有结点的度数均不大于2，所以结点总数应等于0度结点数、1度结点数和2度结点数之

5、和，即：n=n0+n1+n2①6.2二叉树另一方面，1度结点有一个孩子，2度结点有两个孩子。所以，二叉树中孩子结点总数是n1+2n2，二叉树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可以表示为：n=n1+2n2+1②由式①和式②得到：n0=n2+1两种特殊形式的二叉树：满二叉树：一棵深度为k且有2k-1个结点的二叉树。完全二叉树：若一棵二叉树至多只有最下面两层上结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。6.2二叉树4、具有n个结点的完全二叉树的深度为log2n+1证明：设所有完全二叉树的深度为k，由完全二叉树的定义可知，它

6、的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。由于完全二叉树深度为k，故第k层上还有若干个结点，因此，该完全二叉树的结点个数n>2k-1-1。另一方面，由性质2可知n≤2k-1，即：2k-1-11,则ki的双亲编号为int(i/2)。（2）若2i≤n，则ki的左孩子的编号是2i；2i>n,则无左孩子。（3）若2i+1

7、≤n,则ki右孩子的编号是2i+1;2i+1>n,则无右孩子。（4）若i为奇数且不为1，则ki的左兄弟的编号是i-1；否则ki无左兄弟。（5）若i为偶数且小于n，则ki的右兄弟的编号是i+1；否则ki无右兄弟。6.2二叉树二叉树的存储结构1）顺序存储结构:对完全二叉树而言，既简单又节省存储空间，但对非完全二叉树，必须按完全二叉树的形式来存储树中的结点，这将造成存储空间的浪费。A0B000C1234567A0B000C6.