树、⼆叉树、满⼆叉树、完全⼆叉树概念分清
⾃由树
⾃由树是⼀个连通的，⽆回路的⽆向图。
令G=(V，E)为⼀个⽆向图。下⾯的表述是等价的。
1)        G是⾃由树。
2)        G中任意两个顶点由唯⼀⼀条简单路径得到。
3)        G是连通的，但从E中去掉任何边后得到的图都是⾮连通的。
4)        G是⽆回路的，且|E|=|V|-1。
5)        G是连通的，且|E|=|V|-1。
6)        G是⽆回路的，但添加任何边到E中得到的图包含回路。
⼆叉树
在计算机科学中，⼆叉树是每个节点最多有两个⼦树的树结构。通常⼦树被称作“左⼦树”（left subtree）和“右⼦树”（right subtree）。
⼆叉树的每个结点⾄多只有⼆棵⼦树(不存在度⼤于2的结点)，⼆叉树的⼦树有左右之分，次序不能颠倒。
⼆叉树的第i层⾄多有2^(i-1)个结点；
深度为k的⼆叉树⾄多有2^k-1个结点；（等⽐数列1+2+4+…+2^(k-1) = 2^k-1）。
对任何⼀棵⼆叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
树和⼆叉树的三个主要差别：
1)  树的结点个数⾄少为1，⽽⼆叉树的结点个数可以为0；
2)  树中结点的最⼤度数没有限制，⽽⼆叉树结点的最⼤度数为2；
3)  树的结点⽆左、右之分，⽽⼆叉树的结点有左、右之分。
满⼆叉树
⼀棵深度为k，且有2^k-1个节点的树是满⼆叉树。
另⼀种定义：除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最底层的⼆叉树。
这两种定义是等价的。
从树的外形来看，满⼆叉树是严格三⾓形的，⼤家记住下⾯的图，它就是满⼆叉树的标准形态：
所有内部节点都有两个⼦节点，最底⼀层是叶⼦节点。
性质：
1)        如果⼀颗树深度为h，最⼤层数为k，且深度与最⼤层数相同，即k=h;
2)        它的叶⼦数是： 2^(h-1)
3)        第k层的结点数是： 2^(k-1)
4)        总结点数是： 2^k-1 (2的k次⽅减⼀)
5)        总节点数⼀定是奇数。
二叉树定义6)        树⾼：h=log2(n+1)。
完全⼆叉树
完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n 的结点⼀⼀对应时称之为完全⼆叉树。
若设⼆叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最⼤个数，第h 层所有的结点都连续集中在最左边，这就是完全⼆
叉树。
（⼤家好好理解⼀下上⾯两个定义，是等价的~~）
满⼆叉树⼀定是完全⼆叉树，完全⼆叉树不⼀定是满⼆叉树。
下⾯是完全⼆叉树的基本形态：
完全⼆叉树的性质：
1)        深度为k的完全⼆叉树，⾄少有2^(k-1)个节点，⾄多有2^k-1个节点。
2)        树⾼h=log2n + 1。
对满⼆叉树、完全⼆叉树总结点及树⾼的总结：

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