数据结构学习记录-树和二叉树
1、树的概念
关于树的定义和基本术语
1、是一种非线性的数据结构，又叫做树型数据结构。
2、树是n(n >=0)个节点的有限集合,当n=0时，叫空树
3、非空树必须满足两个条件：
1、有且仅有一个特定的称为根的节点，
2、其余的节点可以分为m(m >=0)个互不相交的有限集合T1、T2、......、Tm,其中每一个集合又是一棵 树，并称其为根的子树
树的相关概念：
1、节点的度：树中一个节点的孩子个数称为该节点的度， 所有节点的度的最大值是树的度
2、分支节点：度大于0的节点称为分支节点
3、叶子结点：度为0的节点称为叶子结点
4、节点的层次（深度）：从上往下数，根节点为1层，依次往下加1
5、树的高度（深度）：树中节点的最大层次
6、若树中节点的各子树从左至又是有次序的，不能互换，则该树称为有序树，否则称为无序树
7、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
8、孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
9、兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
10、森林：森林是m（m >= 0 )棵互不相交的树的集合，
11、树去掉根节点就成为森林，森林加上根节点就是树
如下图：一棵树
节点A的度：3 节点B的度：2 节点M的度：0
分支节点：A B C D E H 叶子节点：K L F G M I J
E节点的层次：第3层 树的高度：4
节点A的子节点：B C D 节点E的子节点：K L
节点I的双亲节点：D 节点H I J 为兄弟节点
树的逻辑结构：树中任何节点都可以有0个或多个直接后继节点(子节点),但最多只有一个直接前驱节点(父节点),
根节点没有前驱节点，叶子节点没有后继节点
2、二叉树
1、二叉树的概念
二叉树Binary Tree是n个节点的有限集合，它或者是空集、或者是由一个根节点以及两颗互不相交、分别称为左子树和右子树的二叉树组成。
二叉树的特点：
1、二叉树与 普通的有序树不同，二叉树严格区分左子和右子，即使只有一个子节点，也要区分左右
2、二叉树的度数为2
2、二叉树的性质
1、二叉树的第k层上的节点最多有2k-1 个
2、深度为k的二叉树，最多有2k-1个节点
3、在任意一颗二叉树中，叶子结点的数目比度数为2的节点数目多1
证明：
N：结点的总数
N0：没有子结点的结点个数
N1：只有一个子结点的结点个数
N2：有两个子结点的结点个数
总结点 = 各节点数目之和 N = N0 + N1 + N2
总结点 = 所有子节点 + 根 N = 0 × N0 + 1 × N1 + 2 × N2 + 1
联立以上两式可得： N0 = N2 + 1
3、特殊的二叉树
两种比较特殊的二叉树：满二叉树和完全二叉树
1、满二叉树
深度为k(k>=1)时节点个数为2k-1
深度为k的满二叉树，总共有有2k-1个节点
2、完全二叉树
只有最下面两层可以有度数小于2的节点，且最下面一层的结点集中在最左边的若干位置上
满二叉树也是特殊的完全二叉树
3、二叉树的实现
二叉树的存储结构有两种：顺序存储和链式存储
1、顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以用顺序表存储。因此，如果我们想要顺序存储普通二叉树，就需要将其提前转换成完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些结点，将其"拼凑"成一个完全二叉树即可，但这时会造成一部分内存浪费，所以不建议使用顺序存储，实现二叉树。
顺序存储，浪费空间
2、链式存储
链式存储此二叉树，从根结点开始，将各个结点以及其左右子的地址使用链表进行存储。
typedef int data_t;
typedef struct node_t
{
data_t data ;
struct node t *lchild ,*rchild ;
}bitree_t;
bitree_t *root ;
//二叉树由根节点指针决定。3、二叉树的遍历
遍历此二叉树，有3种方法：