数据结构--数tree
开场白： 树(Tree)：有且仅有有个特定的结点 成为 根root
其余的结点互不相交的有限集，并且本身也是一棵树称为跟人root的子树SubTree
定义：之前都是一对一的线性结构，另一种一对多的数据结构–树Tree
注意：子树是互不相交的
结点拥有的子树数量称为结点的度(degree)，度为0的称为叶子结点
除了根结点之外，其他的分支结点；一棵树的度是内部各分支结点的度的最大值！
节点之间的关系：父节点 子节点 兄弟节点
树的深度Depth或高度：树中结点的最大层次
线性结构：有顺序存储和链式存储两种结构
对于树来说 主要介绍三种结构：双亲表示法，孩子表示法，孩子兄弟表示法
这里主要介绍一下双亲表示法：data是数据域 parent是指针域，存储该结点的双亲在数组当中的下标
因为除了根结点，其他结点一定有且仅有一个双亲
这样存储结构，可以根据结点的parent指针很容易找到他的双亲结点(父节点)，时间复杂度是,直到parent是-1；表示找到了树的根结点
如果想知道结点的子节点是啥，对不起请遍历整个结构才行！！
这时候可以设置一个结点最左边的孩子结点的域 叫做长子域，这样就能得到该结点的孩子结点；如果没有孩子就设置-1；
二叉树的定义
首先想到二分查找法：每次都会排除一半的情况
对于某个阶段都是两种结果的情形 都适合用树状结构来建模；而这种树是一种很特殊结构–二叉树（Binary Tree）
二叉树特点：
- 每个节点最多有两棵子树，所以二叉树结点当中最大度是2，树的度最大也是2
- 左子树和右子树是有顺序的，次序不能颠倒
- 即使树中的某个结点只有一颗子树，也要区分左右
其实这样想 我们的线性结构是树的一种能特殊变现形式！！！
满二叉树：所有分支节点都在左右子树，并且所有叶子结点都在一层上，这样的二叉树称为 满二叉树
总而言之 不能缺胳膊少腿的 叶子结点还得在一层上
完全二叉树：连续 而却 跟满二叉树中位置一样 同样的二叉树 完全二叉树的深度最小