树的基本概念

                                                                              树

1.节点，根节点，父节点，子节点，兄弟节点               

2.一棵树可以没有任何节点，称为空树

3.一棵树可以只有1个节点，也就是只有根节点

4.子树，左子树，右子树

5.节点的度：子树的个数

6.树的度：所有节点度最大的值

7.叶子节点：度为0的节点

8.非叶子节点：度不为0的节点

9.层数：根节点在第1层，根节点的子节点在第2层，以此类推

10.节点的深度：从根节点到当前节点唯一径上的节点总数

11，节点的高度：从当前节点到最远叶子节点的路径上的节点总数

12.树的深度：所有节点深度中的最大值

13.树的高度等于树的深度

14.有序树，树中任意节点的子节点之间有顺序关系

15.无序数.树中任意子节点之间没有顺序关系

                                                        二叉树

二叉树的特点

1.每个节点的度最大为2（最多拥有两棵子树）

2.左子树和右子树是有顺序的

3.即使只有一棵子树，也区分左右

二叉数的性质

非空二叉树的第i层，最多2的(n-1)次方

在高度为h的二叉数最多有2的h次方-1个节点

对于任何一棵非空二叉数，如果叶子节点个数为n0，度为2的节点个数为n2，则有：n0=n2+1;

假设度为1的节点个数为n1,那么二叉树的节点总数n=n0+n1+n2;

二叉树的边数T=n1+n2*2=n-1=n0+n1+n2+1;

真二叉数：所有度要么为0，要么为2

满二叉树：所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层。所以，在同样高度的二叉树：满二叉树的叶子节点数量最多，总结点数量最多，满二叉树一定是真二叉树，真二叉树不一定是满二叉树。

完全二叉树：叶子节点只会出现最后2层，且最后一层的叶子节点都靠左对齐，完全二叉树的倒数第二层树满二叉树满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树，

1：度为1 的节点只有左子树， 

2：度为1的节点要么是1个，要么是0个，同样节点的二叉树，安全二叉树的高度最少，至少有2的h-1方的节点，最多有2的h方减1个节点（满二叉树），总结点数量为n