数据结构--树、⼆叉树、满⼆叉树、完全⼆叉树的性质
树
树（英语：tree）是⼀种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，⽤来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成⼀个具有层次关系的集合。把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
树的性质：
1. 树可以没有结点，这种情况把树称为空树。
2. 树的层次从根结点开始算起，即根结点为第⼀层，根结点⼦树的根结点为第⼆层，以此类推。
3. 把结点的⼦树棵数称为结点的度，树中结点的最⼤的度称为树的度。
4. 由于⼀条边连接两个结点，且树中不存在环，因此对有n个结点的树，边数⼀定是n-1.
满⾜连通、边数等于顶点数-1的结构⼀定是⼀棵树。
5. 叶⼦结点被定义为度为0的结点，因此当树中只有⼀个结点（即只有根结点）时，根结点也算作叶⼦结
点。
6. 结点的深度是指从根结点（深度为1）开始⾃顶向下逐层累加⾄该结点的深度值。
结点的⾼度是指从最底层叶⼦结点开始⾃底向上逐层累加⾄该结点时的⾼度值。
树的深度是指树中结点的最⼤深度，树的⾼度是指树中结点的最⼤⾼度。对树⽽⾔，深度与⾼度相等。
7. 多棵树组合在⼀起称为森林，即森林是若⼲树的集合。
把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：
(01) 每个节点有零个或多个⼦节点；
(02) 没有⽗节点的节点称为根节点；
(03) 每⼀个⾮根节点有且只有⼀个⽗节点；
(04) 除了根节点外，每个⼦节点可以分为多个不相交的⼦树。
⼆叉树
⼆叉树是每个节点最多有两个⼦树的树结构。它有五种基本形态：⼆叉树可以是空集；根可以有空的左⼦树或右⼦树；或者左、右⼦树皆为空。
  ⼆叉树的性质
⼆叉树有以下⼏个性质：TODO(上标和下标)
性质1：⼆叉树第i层上的结点数⽬最多为 2{i-1} (i≥1)。
性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的⼆叉树的⾼度⾄少为log2 (n+1)。
性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
性质1：⼆叉树第i层上的结点数⽬最多为 2{i-1} (i≥1)
证明：下⾯⽤"数学归纳法"进⾏证明。
(01) 当i=1时，第i层的节点数⽬为2{i-1}=2{0}=1。因为第1层上只有⼀个根结点，所以命题成⽴。
(02) 假设当i>1，第i层的节点数⽬为2{i-1}。这个是根据(01)推断出来的！
下⾯根据这个假设，推断出"第(i+1)层的节点数⽬为2{i}“即可。
由于⼆叉树的每个结点⾄多有两个孩⼦，故"第(i+1)层上的结点数⽬” 最多是 “第i层的结点数⽬的2倍”。即，第(i+1)层上的结点数⽬最⼤值=2×2{i-1}=2{i}。
故假设成⽴，原命题得证！
性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)
证明：在具有相同深度的⼆叉树中，当每⼀层都含有最⼤结点数时，其树中结点数最多。利⽤"性质1"可知，深度为k的⼆叉树的结点数⾄多为：
20+21+…+2k-1=2k-1
故原命题得证！
性质3：包含n个结点的⼆叉树的⾼度⾄少为log2 (n+1)
证明：根据"性质2"可知，⾼度为h的⼆叉树最多有2{h}–1个结点。反之，对于包含n个节点的⼆叉树的⾼度⾄少为log2(n+1)。
性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
证明：因为⼆叉树中所有结点的度数均不⼤于2，所以结点总数(记为n)=“0度结点数(n0)” + “1度结点数(n1)” + “2度结点数
(n2)”。由此，得到等式⼀。
(等式⼀) n=n0+n1+n2
  另⼀⽅⾯，0度结点没有孩⼦，1度结点有⼀个孩⼦，2度结点有两个孩⼦，故⼆叉树中孩⼦结点总数是：n1+2n2。此外，只有根不是任何结点的孩⼦。故⼆叉树中的结点总数⼜可表⽰为等式⼆。
(等式⼆) n=n1+2n2+1
由(等式⼀)和(等式⼆)计算得到：n0=n2+1。原命题得证！
满⼆叉树
定义：⾼度为h，并且由2{h} –1个结点的⼆叉树，被称为满⼆叉树。二叉树的基本性质
完全⼆叉树
定义：⼀棵⼆叉树中，只有最下⾯两层结点的度可以⼩于2，并且最下⼀层的叶结点集中在靠左的若⼲位置上。这样的⼆叉树称为完全⼆叉树。
特点：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。显然，⼀棵满⼆叉树必定是⼀棵完全⼆叉树，⽽完全⼆叉树未必是满⼆叉树。

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