数据结构-树

非线性，一对多。（定义是递归形式的）
根（根结点的层为1）、根的子树、结点的度（结点的子树数目）、叶子结点（也叫终端节点）、分支节点、双亲（虽然叫双亲但是parent只有一个）、树的深度（又称高度，叶子结点的层数）、兄弟、堂兄弟（同层不同双亲的结点）、祖先、子孙（所有子树的结点）、有序树（子树的顺序从左到右有限定，更换则不是同一颗树）、无序树。
森林：m棵互不相交的数的集合，如F={T₁,T₂,T₃}，任何一棵非空树可表示为Tree=(root,F)，F是子树森林。

因为root根结点被拆掉了之后剩下的子树就散了互不相交可以看作森林）

递归定义：根节点，左子树右子树。每个结点的孩子是不会重复的。
每个结点至多两个子树，是有序树。
叶子结点的个数n₀=度为2的结点数n₂+1。（不直观，需要记）

总数n=n₀+n₁+n₂，孩子的个数=n-1=2n₂+n₁。
含有n个结点的二叉链表中，有n+1个空链域。

利用n₀=n₂+1，空链域数=2n₀+n₁。
满二叉树：深度为k且有2^k-1个结点的二叉树。
完全二叉树
每个结点都和同深度的满二叉树中的编号从1至n的结点一一对应。其叶结点只可能出现在层次最大或者第二大的层上。结点数2^k-1-1<n<=2^k。
对于完全二叉树的第i个结点，若2i>n，则该结点没有左孩子结点；若2i+1>n，则该结点没有右孩子结点。若结点有双亲结点，则双亲结点的编号必然是i/2向下取整。
存储结构
采用链式存储结构比较方便。
三叉链表比二叉链表多一个指向双亲结点的指针。
静态链表也可以用来描述二叉树，此时的左孩子右孩子指针只要是孩子结点对应的标号（当然也可以是指针，但没必要）就可以了，整体看起来是一个结构数组。

D—-访问根节点，输出根节点
L—-递归遍历左子树
R—-递归遍历右子树