数据结构复习-树与⼆叉树（1）
树的概念与基本术语
树是若⼲结点的集合，是由唯⼀的根和若⼲棵互不相交的⼦树组成的。树的概念是递归的，即在树的定义中⼜⽤到了树的定义。
结点的度：结点拥有的⼦树个数或者分⽀的个数。
树的度：树中各结点度的最⼤值。
层次：从根开始，根为第⼀层，根的孩⼦为第⼆层。
树的⾼度（或者深度）：树中结点的最⼤层次。
结点的深度：从根结点到该结点路径上的结点个数
结点的⾼度：从某结点往下⾛可能到达多个叶⼦结点，对应了多条通往这些叶⼦结点的路径，其中最长的那条路径的长度即为该结点在树中的⾼度。根结点的⾼度为树的⾼度。
兄弟：同⼀个双亲的孩⼦之间互为兄弟。
堂兄弟：双亲在同⼀层的结点互为堂兄弟。
有序树与⽆序树：树中的结点的⼦树从左到右是有次序的，不能交换，这样的树叫做有序树。可以随便交换的叫做⽆序树。
丰满树：丰满树即理想平衡树，要求除最底层外，其他层都是满的。
森林：若⼲棵互不相交的树的集合。
树的存储结构：
1.顺序存储结构：
树的顺序存储结构中最简单直观的是双亲存储结构。⽤⼀个整数数组来存储，下标就是该结点，数组元素的内容表⽰该结点的双亲结点。例如3的双亲是1，则tree[3]=1.
树的双亲存储结构在克鲁斯卡尔算法中有重要应⽤。
2.链式存储结构：
1）孩⼦存储结构：孩⼦存储结构实质上就是图的邻接表存储结构。树就是⼀种特殊的图。
2）孩⼦兄弟存储结构：孩⼦兄弟存储结构与树和森林与⼆叉树的相互转换关系密切。
⼆叉树
⼆叉树满⾜以下定义：
1. 每个结点最多只有两棵⼦树，即⼆叉树中结点的度只能为0、1、2
2. ⼦树有左右顺序之分，不能颠倒
二叉树公式满⼆叉树：如果所有的分⽀结点都有左孩⼦和右孩⼦结点，并且叶⼦结点都集中在⼆叉树的最下⼀层，则这样的⼆叉树成为满⼆叉树。
完全⼆叉树：如果对⼀棵深度为k，有n个结点的⼆叉树进⾏编号后，各结点的编号与深度为k的满⼆叉树中相对位置上的结点的编号均相同，那么这棵树就是⼀棵完全⼆叉树。
⼀棵完全⼆叉树⼀定是由⼀棵满⼆叉树从右到左，从下到上，挨个删除结点所得到的。如果跳着删除，则得到的不是完全⼆叉树。
⼆叉树的主要性质：
性质1. ⾮空⼆叉树上叶⼦结点数等于双分⽀结点数加1.
证明：假设叶⼦结点数为n0，单分⽀结点数为n1，双分⽀结点数为n2，则总结点数为n0+n1+n2。总分⽀数为n1+2n2。由于除了根结点外，其它结点都有⼀个分⽀指向它，所以总分⽀数=总结点数-1。得到n1+2n2 = n0 + n1 + n2 - 1。得到：n2 = n0 - 1。
⼀个变形：问⼆叉树中总的结点数为n，则树中空指针数为多少？可以将空指针数看成是叶⼦结点，则每个结点都是双分⽀结点。根据性质1，叶⼦结点数等于双分⽀结点数加1，则空指针数=n+1.
性质2. ⼆叉树的第i层最多有2^(i-1)个结点（i>=1）.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。